# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

__Mittagsseminar Talk Information__ | |

**Date and Time**: Tuesday, October 12, 2004, 12:15 pm

**Duration**: This information is not available in the database

**Location**: This information is not available in the database

**Speaker**: Alex Souza-Oftermatt

## Recent Progress in Stochastic Knapsack

In this talk we consider the following stochastic variant of the
Knapsack problem.
We are given a finite set *N = {1, 2, ..., n}* of objects, where each
object *j* yields a profit *p*_{j} and has a weight *w*_{j}.
Profits are drawn from a probability distribution and weights are
specified by an adversary. In addition, the adversary also
chooses the capacity of a knapsack. The problem is to choose objects as
to maximise total profit while not violating the capacity constraint.
In the recent work of Beier and Vöcking 'Random Knapsack in Expected
Polynomial Time' [STOC '03] and 'Probabilistic Analysis of
Knapsack Core Algorithms' [SODA '04] substantial progress on this problem
was made.

The conclusion is that the above problem can be solved to optimality in
expected time *O(n polylog(n))*. The key ingredients are two
algorithms; an enumeration algorithm and a so-called core algorithm.
Combination of these yields the claimed bound.
In this talk we will present the main ideas behind these algorithms,
their combination and sketch their analysis.

Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)

Previous talks by year: 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