1 citations · 2 across the 20 of their papers we have counts for
Showing 2016Show all
3 papers · 1 filter
cs.DS2016
Timing Matters: Online Dynamics in Broadcast Games
Shuchi Chawla, Joseph, Naor +3
A central question in algorithmic game theory is to measure the inefficiency (ratio of costs) of Nash equilibria (NE) with respect to socially optimal solutions. The two establishe…
cs.DS2016
LAST but not Least: Online Spanners for Buy-at-Bulk
Anupam Gupta, R. Ravi, Kunal Talwar +1
The online (uniform) buy-at-bulk network design problem asks us to design a network, where the edge-costs exhibit economy-of-scale. Previous approaches to this problem used tree- e…
cs.DS2016
LP-Based Robust Algorithms for Noisy Minor-Free and Bounded Treewidth Graphs
Nikhil Bansal, Daniel Reichman, Seeun William Umboh
We give a general approach for solving optimization problems on noisy minor free graphs, where a δ-fraction of edges and vertices are adversarially corrupted. The noisy setting was…