Seminars

View all Seminars  |  Download ICal for this event

Robust Secretary Algorithms for Packing Integer Programs

Series: IISc MSR Theory Seminar Talk - ONLINE

Speaker: Sahil Singla, Assistant Professor, School of Computer Science, Georgia Tech

Date/Time: Sep 01 18:00:00

Location: Microsoft Teams - ON-LINE

Abstract:
We study the problem of solving Packing Integer Programs (PIPs) in the online setting, where columns in [0,1]^d of the constraint matrix are revealed sequentially, and the goal is to pick a subset of the columns that sum to at most B in each coordinate while maximizing the objective. E.g., this problem captures the Online Knapsack problem when d=1. Excellent results are known for PIPs in the secretary model, where the columns are adversarially chosen but presented in a uniformly random order. However, these existing algorithms are susceptible to adversarial attacks: they try to

Host Faculty: Rahul Madhavan and Rameesh Paul