Seminars

View all Seminars  |  Download ICal for this event

Single-Sample Prophet Inequalities for Knapsack Problems

Series: Bangalore Theory Seminars

Speaker: Alice Sayutina, University of Amsterdam

Date/Time: Aug 21 16:00:00

Location: Online Talk (See Teams link below)

Abstract:
Prophet inequalities is a major topic in online algorithms, where an online decision maker seeks to achieve a comparable performance to an omniscient prophet, who knows the input in advance. However, the common assumption is that the decision-maker has to be given an advance knowledge of the input distribution. Recently, this assumption was successfully weakened in certain scenarios, obtaining similar approximations with the decision maker having access to only a constant number of samples from the input distribution.


In this work, we investigate single-sample prophet inequalities for knapsack problems. Here, the decision-maker chooses a set of online rewards, subject to a weight constraint.


We present a 2-competitive mechanism for fractional knapsack (which matches the full-knowledge setting), a 4-competitive mechanism for integer knapsack, and some other constant-competitive mechanisms for knapsack-adjacent problems.


This talk is based on a joint work with Pranav Nuti, Rebecca Reiffenhäuser. (Preprint link.)


Microsoft Teams link:

Link


Hosts: KVN Sreenivas, Sreeramji K S, Ritabrata Barat, Venkata Sai Nikhil Srivatsava Ayyadevara