23 citations · 24 across the 2 of their papers we have counts for
4 papers · 1 filter
Structured Robust Submodular Maximization: Offline and Online Algorithms
Alfredo Torrico, Mohit Singh, Sebastian Pokutta +4
Constrained submodular function maximization has been used in subset selection problems such as selection of most informative sensor locations. While these models have been quite p…
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…
Min-Max Graph Partitioning and Small Set Expansion
Nikhil Bansal, Uriel Feige, Robert Krauthgamer +5
We study graph partitioning problems from a min-max perspective, in which an input graph on n vertices should be partitioned into k parts, and the objective is to minimize the maxi…
A Polylogarithmic-Competitive Algorithm for the k-Server Problem
Nikhil Bansal, Niv Buchbinder, Aleksander Madry +2
We give the first polylogarithmic-competitive randomized online algorithm for the -server problem on an arbitrary finite metric space. In particular, our algorithm achieves a co…