Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Prof. Emo Welzl and Prof. Bernd Gärtner
Mittagsseminar Talk Information |
Date and Time: Tuesday, February 26, 2013, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Yann Disser (TU Berlin)
We consider the classical knapsack problem with the twist that we do not know the capacity of the knapsack a priori. We are given a set of items, each with a size and a value. Once an item is put into the knapsack, it cannot be taken out again, and whenever an item doesn't fit, we may discard the item and continue to fill the knapsack with the remaining items. Our goal is to put the items into a universal order, such that trying to pack the items in this order gives a good solution for every capacity. We give an algorithm that always produces an ordering that achieves a 2-approximation of the optimum solution for every capacity. The algorithm does this by emulating the classical greedy 2-approximation algorithm for the standard knapsack problem. We also show that this algorithm is best-possible in the sense that for some instances no ordering can achieve a better ratio for all capacities.
Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)
Previous talks by year: 2025 2024 2023 2022 2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996
Information for students and suggested topics for student talks
Automatic MiSe System Software Version 1.4803M | admin login