12 citations · 55 across the 25 of their papers we have counts for
10 papers · 1 filter
Online Vector Balancing and Geometric Discrepancy
Nikhil Bansal, Haotian Jiang, Sahil Singla +1
We consider an online vector balancing question where vectors, chosen from an arbitrary distribution over , arrive one-by-one and must be immediately given a si…
Robust Algorithms for the Secretary Problem
Domagoj Bradac, Anupam Gupta, Sahil Singla +1
In classical secretary problems, a sequence of elements arrive in a uniformly random order, and we want to choose a single item, or a set of size . The random order model al…
Faster Matroid Intersection
Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford +2
In this paper we consider the classic matroid intersection problem: given two matroids $\M_{1}=(V,\I_{1})$ and $\M_{2}=(V,\I_{2})$ defined over a common ground set , compute a s…
Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders
Sepehr Assadi, Sahil Singla
A longstanding open problem in Algorithmic Mechanism Design is to design computationally-efficient truthful mechanisms for (approximately) maximizing welfare in combinatorial aucti…
Algorithms and Adaptivity Gaps for Stochastic -TSP
Haotian Jiang, Jian Li, Daogao Liu +1
Given a metric and a , the classic $\textsf{$k$-TSP}$ problem is to find a tour originating at the of minimum length that visits at lea…
Online Geometric Discrepancy for Stochastic Arrivals with Applications to Envy Minimization
Haotian Jiang, Janardhan Kulkarni, Sahil Singla
Consider a unit interval in which points arrive one-by-one independently and uniformly at random. On arrival of a point, the problem is to immediately and irrevocably c…
Non-clairvoyant Precedence Constrained Scheduling
Naveen Garg, Anupam Gupta, Amit Kumar +1
We consider the online problem of scheduling jobs on identical machines, where jobs have precedence constraints. We are interested in the demanding setting where the jobs sizes are…
Approximation Schemes for a Unit-Demand Buyer with Independent Items via Symmetries
Pravesh Kothari, Divyarthi Mohan, Ariel Schvartzman +2
We consider a revenue-maximizing seller with items facing a single buyer. We introduce the notion of symmetric menu complexity of a mechanism, which counts the number of distin…
The Markovian Price of Information
Anupam Gupta, Haotian Jiang, Ziv Scully +1
Suppose there are Markov chains and we need to pay a per-step \emph{price} to advance them. The "destination" states of the Markov chains contain rewards; however, we can only…
(Near) Optimal Adaptivity Gaps for Stochastic Multi-Value Probing
Domagoj Bradac, Sahil Singla, Goran Zuzic
Consider a kidney-exchange application where we want to find a max-matching in a random graph. To find whether an edge exists, we need to perform an expensive test, in which ca…