Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

Date and Time: Tuesday, November 11, 2025, 12:15 pm

Duration: 30 minutes

Location: CAB G51

Speaker: Moritz Stocker

Packing Peas and Stealing Gold — Online Unbounded Knapsack Problems

Imagine, if you will, a hobbit creeping through a dragon's lair. Having found the dragon, it now swiftly makes its escape. Surrounding it on its way out are piles of coins, heaps of rubies, mountains of diamonds, each containing far more than the hobbit could possibly carry. Grinning, the hobbit opens its trusty knapsack and fills it to the brim with silver coins. Around a corner, it almost stumbles over a number of large gold bars. It empties its knapsack of silver and packs two of these gold bars instead, which completely fill its knapsack. Around the next bend, gleaming in the light of the hobbit's candle, lies an enormous jewel. Greedily, the hobbit removes the two gold bars and packs the jewel instead. It silently curses, wishing it had kept the silver coins, some of which would have nicely filled up the remaining space in the knapsack. But it dares not go back, deeper into the lair, towards the dormant dragon. And thus, the hobbit shoulders its knapsack and presses on... In the online knapsack problem and its many variants, items arrive one-by-one, each with a value and weight. These items may be packed into a knapsack of fixed weight capacity, where the goal is to maximize the combined value of the items packed. Here, we focus on unbounded variants, where any item may be packed arbitrarily many times. This includes some recent results for the Unbounded Knapsack Problem with Removal, which is one of the first natural variants to admit competitive deterministic algorithms for general items.

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