2 citations · 5 across the 4 of their papers we have counts for
4 papers
Optimal non-adaptive solutions for the counterfeit coin problem
C. Thach Nguyen
We give optimal solutions to all versions of the popular counterfeit coin problem obtained by varying whether (i) we know if the counterfeit coin is heavier or lighter than the gen…
Integrality Gaps of Linear and Semi-definite Programming Relaxations for Knapsack
Anna R. Karlin, Claire Mathieu, C. Thach Nguyen
In this paper, we study the integrality gap of the Knapsack linear program in the Sherali- Adams and Lasserre hierarchies. First, we show that an integrality gap of 2 - ε persists…
On Revenue Maximization in Second-Price Ad Auctions
Yossi Azar, Benjamin Birnbaum, Anna R. Karlin +1
Most recent papers addressing the algorithmic problem of allocating advertisement space for keywords in sponsored search auctions assume that pricing is done via a first-price auct…
Thinking Twice about Second-Price Ad Auctions
Yossi Azar, Benjamin Birnbaum, Anna R. Karlin +1
Recent work has addressed the algorithmic problem of allocating advertisement space for keywords in sponsored search auctions so as to maximize revenue, most of which assume that p…