60 citations · 269 across the 42 of their papers we have counts for
4 papers · 1 filter
Succinct Coverage Oracles
Ioannis Antonellis, Anish Das Sarma, Shaddin Dughmi
In this paper, we identify a fundamental algorithmic problem that we term succinct dynamic covering (SDC), arising in many modern-day web applications, including ad-serving and onl…
Submodular Functions: Extensions, Distributions, and Algorithms. A Survey
Shaddin Dughmi
Submodularity is a fundamental phenomenon in combinatorial optimization. Submodular functions occur in a variety of combinatorial settings such as coverage problems, cut problems,…
Amplified Hardness of Approximation for VCG-Based Mechanisms
Shaddin Dughmi, Hu Fu, Robert Kleinberg
If a two-player social welfare maximization problem does not admit a PTAS, we prove that any maximal-in-range truthful mechanism that runs in polynomial time cannot achieve an appr…
On the Power of Randomization in Algorithmic Mechanism Design
Shahar Dobzinski, Shaddin Dughmi
In many settings the power of truthful mechanisms is severely bounded. In this paper we use randomization to overcome this problem. In particular, we construct an FPTAS for multi-u…