From the 1 of 8 linked papers with an AI index.
8 papers
Online Algorithms via Minimax and Posterior Matching
Thomas Kesselheim, Marco Molinaro, Kalen Patton +1
Competitive analysis is central to the study of online algorithms, but upper bounds are often highly problem-specific. We develop a more unifying methodology via the minimax viewpo…
Philosopher and Prophet Inequalities for Divisible Items
Thiago Oliveira, Mohit Singh, Sahil Singla
The paper studies online allocation of divisible resources to arriving players with concave valuations, providing a 2/3‑approximation to the optimal online (philosopher) benchmark…
Online Graph Balancing and the Power of Two Choices
Nikhil Bansal, Milind Prabhu, Sahil Singla +1
In the classic online graph balancing problem, edges arrive sequentially and must be oriented immediately upon arrival, to minimize the maximum in-degree. For adversarial arrivals,…
Secretary, Prophet, and Stochastic Probing via Big-Decisions-First
Aviad Rubinstein, Sahil Singla
We revisit three fundamental problems in algorithms under uncertainty: the Secretary Problem, Prophet Inequality, and Stochastic Probing, each subject to general downward-closed co…
Integral Online Algorithms for Set Cover and Load Balancing with Convex Objectives
Thomas Kesselheim, Marco Molinaro, Kalen Patton +1
Online Set Cover and Load Balancing are central problems in online optimization, and there is a long line of work on developing algorithms for these problems with convex objectives…
Improved and Oracle-Efficient Online -Multicalibration
Rohan Ghuge, Vidya Muthukumar, Sahil Singla
We study \emph{online multicalibration}, a framework for ensuring calibrated predictions across multiple groups in adversarial settings, across rounds. Although online calibrat…