15 citations · 36 across the 12 of their papers we have counts for
12 papers
Improved Truthful Mechanisms for Subadditive Combinatorial Auctions: Breaking the Logarithmic Barrier
Sepehr Assadi, Thomas Kesselheim, Sahil Singla
We present a computationally-efficient truthful mechanism for combinatorial auctions with subadditive bidders that achieves an -approximation to the maximum w…
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…