- Series
- ACO Student Seminar
- Time
- Friday, March 16, 2012 - 1:00pm for 1 hour (actually 50 minutes)
- Location
- Executive classroom, ISyE Main Building
- Speaker
- László Vegh – CoC, Georgia Tech – lvegh@cc.gatech.edu – http://www.cc.gatech.edu/~lvegh/
- Organizer
- Cristóbal Guzmán
I present a new class of vertex cover and set cover games, with the price of anarchy bounds matching the best known
constant factor approximation guarantees for the centralized optimization problems for linear and also for submodular
costs. In particular, the price of anarchy is 2 for vertex cover. The
basic intuition is that the members of the vertex cover form a Mafia
that has to "protect" the graph, and may ask ransoms from their
neighbors in exchange for the protection. These ransoms turn out to
capture a good dual solution to the linear programming relaxation. For linear costs we also exhibit
linear time best response dynamics that converge that mimic the classical greedy approximation algorithm of Bar-Yehuda
and Even. This is a joint work with Georgios Piliouras and Tomas Valla.