Uriel Feige
A Direct Reduction from k-Player to 2-Player Approximate Nash Equilibrium.
Fri, 07/23/2010 - 15:01 — SomNambulAuthors: Uriel Feige, Inbal Talgam-Cohen
Subjects: Computer Science and Game Theory
AbstractWe present a direct reduction from k-player games to 2-player games that
preserves approximate Nash equilibrium. Previously, the computational
equivalence of computing approximate Nash equilibrium in k-player and 2-player
games was established via an indirect reduction. This included a sequence of
works defining the complexity class PPAD, identifying complete problems for
this class, showing that computing approximate Nash equilibrium for k-player
games is in PPAD, and reducing a PPAD-complete problem to computing approximate
Nash equilibrium for 2-player games.Detecting High Log-Densities -- an O(n^1/4) Approximation for Densest k-Subgraph.
Tue, 01/19/2010 - 16:01 — SomNambulAuthors: Uriel Feige, Aditya Bhaskara, Aravindan Vijayaraghavan, Moses Charikar, Eden Chlamtac
Subjects: Data Structures and Algorithms
AbstractIn the Densest k-Subgraph problem, given a graph G and a parameter k, one
needs to find a subgraph of G induced on k vertices that contains the largest
number of edges. There is a significant gap between the best known upper and
lower bounds for this problem. It is NP-hard, and does not have a PTAS unless
NP has subexponential time algorithms. On the other hand, the current best
known algorithm of Feige, Kortsarz and Peleg, gives an approximation ratio of
n^(1/3-epsilon) for some specific epsilon > 0 (estimated at around 1/60).Faster FAST(Feedback Arc Set in Tournaments).
Mon, 11/30/2009 - 16:01 — SomNambulAuthors: Uriel Feige
Subjects: Data Structures and Algorithms
AbstractWe present an algorithm that finds a feedback arc set of size $k$ in a
tournament in time $n^{O(1)}2^{O(\sqrt{k})}$. This is asymptotically faster
than the running time of previously known algorithms for this problem.Deterministic approximation for the cover time of trees.
Fri, 09/11/2009 - 19:13 — SomNambulAuthors: Uriel Feige, Ofer Zeitouni
Subjects: Data Structures and Algorithms
AbstractWe present a deterministic algorithm that given a tree T with n vertices, a
starting vertex v and a slackness parameter epsilon > 0, estimates within an
additive error of epsilon the cover and return time, namely, the expected time
it takes a simple random walk that starts at v to visit all vertices of T and
return to v. The running time of our algorithm is polynomial in n/epsilon, and
hence remains polynomial in n also for epsilon = 1/n^{O(1)}. We also show how
the algorithm can be extended to estimate the expected cover (without return)
time on trees.
User login
