4 citations · 5 across the 7 of their papers we have counts for
6 papers · 1 filter
Online and Bandit Algorithms Beyond Norms
Thomas Kesselheim, Marco Molinaro, Sahil Singla
Vector norms play a fundamental role in computer science and optimization, so there is an ongoing effort to generalize existing algorithms to settings beyond and $\el…
Submodular Dominance and Applications
Frederick Qiu, Sahil Singla
In submodular optimization we often deal with the expected value of a submodular function on a distribution over sets of elements. In this work we study such subm…
Robust Secretary and Prophet Algorithms for Packing Integer Programs
C. J. Argue, Anupam Gupta, Marco Molinaro +1
We study the problem of solving Packing Integer Programs (PIPs) in the online setting, where columns in of the constraint matrix are revealed sequentially, and the goal i…
Combinatorial Prophet Inequalities
Aviad Rubinstein, Sahil Singla
We introduce a novel framework of Prophet Inequalities for combinatorial valuation functions. For a (non-monotone) submodular objective function over an arbitrary matroid feasibili…
Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions
Anupam Gupta, Viswanath Nagarajan, Sahil Singla
Suppose we are given a submodular function over a set of elements, and we want to maximize its value subject to certain constraints. Good approximation algorithms are known for…
On Integrality Ratios for Asymmetric TSP in the Sherali-Adams Hierarchy
Joseph Cheriyan, Zhihan Gao, Konstantinos Georgiou +1
We study the ATSP (Asymmetric Traveling Salesman Problem), and our focus is on negative results in the framework of the Sherali-Adams (SA) Lift and Project method. Our main result…