Convergence of Local Dynamics to Balanced Outcomes in Exchange Networks (2009)
Azar, Yossi, Birnbaum, Benjamin, Celis, L. Elisa, Devanur, Nikhil R., Peres, Yuval
Bargaining games on exchange networks have been studied by both economists and sociologists. A Balanced Outcome for such a game is an equilibrium concept that combines notions of stability and...
New Geometry-Inspired Relaxations and Algorithms for the Metric Steiner Tree Problem ⋆ (2009)
Deeparnab Chakrabarty, Nikhil R. Devanur, Vijay V. Vazirani
Abstract. Determining the integrality gap of the bidirected cut relaxation for the metric Steiner tree problem, and exploiting it algorithmically, is a long-standing open problem. We use geometry to...
Deeparnab Chakrabarty, Nikhil R. Devanur, Vijay V. Vazirani
We study the structure of EG[2], the class of Eisenberg-Gale markets with two agents. We prove that all markets in this class are rational and they admit strongly polynomial algorithms whenever the...
New Geometry-Inspired Relaxations and Algorithms for the Metric Steiner Tree Problem ∗ (2008)
Deeparnab Chakrabarty, Nikhil R. Devanur, Vijay V. Vazirani
Determining the integrality gap of the bi-directed cut relaxation for the metric Steiner tree problem, and exploiting it algorithmically, is a long-standing open problem. We use geometry to define an...
On the Complexity of Hilbert’s 17th Problem (2008)
Nikhil R. Devanur, Richard J. Lipton, Nisheeth K. Vishnoi
Abstract. Hilbert posed the following problem as the 17th in the list of 23 problems in his famous 1900 lecture: Given a multivariate polynomial that takes only non-negative values over the reals,...
Nikhil R. Devanur, Christos H. Papadimitriou, Amin Saberi, Vijay V. Vazirani
We provide the first polynomial time algorithm for the linear version of a market equilibrium model defined by Irving Fisher in 1891, thereby partially answering an open question of [3]. Our...
Nikhil R. Devanur, Deeparnab Chakrabarty
• New Geometric Relaxations for the Steiner Tree Problem and their Algorithmic Consequences,
On Computing the Distinguishing Numbers of Planar Graphs and Beyond: a Counting Approach ∗ (2008)
V. Arvind, Christine T. Cheng, Nikhil R. Devanur
A vertex k-labeling of graph G is distinguishing if the only automorphism that preserves the labels of G is the identity map. The distinguishing number of G, D(G), is the smallest integer k for which...
On Computing the Distinguishing Numbers of Planar Graphs and Beyond: a Counting Approach (2007)
Arvind, V., Cheng, Christine T., Devanur, Nikhil R.
A vertex k-labeling of graph G is distinguishing if the only automorphism that preserves the labels of G is the identity map. The distinguishing number of G, D(G), is the smallest integer k for which...
Price of Anarchy, Locality Gap, and a Network Service Provider Game (2005)
Nikhil R. Devanur, Naveen Garg, Rohit Khandekar, Vinayaka Pandit, Rohit Kh, Vinayaka P, ...
A crucial difference between... In this paper, we define a network service provider game that is natural in the context of the Internet and we raise the question of upper bounding the price of...
Price of anarchy, locality gap, and a network service provider game (2005)
Nikhil R. Devanur, Naveen Garg, Rohit Kh, Vinayaka P, Amin Saberi, Vijay V. Vazirani
Symmetry breaking in trees and planar graphs by vertex coloring (2004)
An undirected graph G is said to be d-distinguishable if there is a d-coloring of its vertex set V (G) such that no nontrivial automorphism of G preserves the coloring. The distinguishing number of a...
The traditional model of market equilibrium supports impressive existence results, including the celebrated Arrow-Debreu Theorem. However, in this model, polynomial time algorithms for computing (or...
Nikhil R. Devanur, Vijay V. Vazirani
Nikhil R. Devanur nikhil@cc.gatech.edu Vijay V. Vazirani vazirani@cc.gatech.edu College of Computing, Georgia Institute of Technology.
An improved approximation scheme for computing Arrow-Debreu prices for the linear case (2003)
Nikhil R. Devanur, Vijay V. Vazirani
Abstract. Recently, Jain, Mahdian and Saberi [5] had given a FPTAS for the problem of computing a market equilibrium in the Arrow-Debreu setting, when the utilities are linear functions. Their...
Strategyproof cost-sharing Mechanisms for Set Cover and Facility Location Games (2003)
Nikhil R. Devanur, Milena Mihail, Vijay V. Vazirani
Strategyproof cost-sharing mechanisms, lying in the core, that recover 1/α fraction of the cost, are presented for the set cover and facility location games; α = O(log n) for the former and 1.861...
Although the study of market equilibria has occupied a central place within mathematical economics for over a century, polynomial time algorithms for such issues have started emerging only recently...
Market equilibrium via a primal-dual-type algorithm (2002)
Nikhil R. Devanur, Christos H. Papadimitriou, Amin Saberi, Vijay V. Vazirani
Although the study of market equilibria has occupied center stage within Mathematical Economics for over a century, polynomial time algorithms for such questions have so far evaded researchers. We...
Market equilibrium via a primal-dual-type algorithm (2002)
Nikhil R. Devanur, Christos H. Papadimitriou, Amin Saberi, Vijay V. Vazirani
We provide the first polynomial time algorithm for the linear version of a market equilibrium model defined by Irving Fisher in 1891, thereby partially answering an open question of [3]. Our...
Market equilibrium via a primal-dual-type algorithm (2002)
Nikhil R. Devanur, Christos H. Papadimitriou, Amin Saberi, Vijay V. Vazirani
Although the study of market equilibria has occupied center stage within Mathematical Economics for over a century, polynomial time algorithms for such questions have so far evaded researchers. We...
Market equilibrium via a primal-dual-type algorithm (2002)
Nikhil R. Devanur, Christos H. Papadimitriou, Amin Saberi, Vijay V. Vazirani
Although the study of market equilibria has occupied center stage within Mathematical Economics for over a century, polynomial time algorithms for such questions have so far evaded researchers. We...
Strategyproof cost-sharing Mechanisms for Set Cover and Facility Location Problems (2002)
Nikhil R. Devanur, Milena Mihail, Vijay V. Vazirani
this paper, we obtain strategyproof cost allocations for two fundamental games whose underlying optimization problems are NP-hard, the set cover game and the facility location game. For the latter...
Market equilibrium via a primal-dual-type algorithm (2002)
Nikhil R. Devanur, Christos H. Papadimitriou, Amin Saberi, Vijay V. Vazirani
We give the first polynomial time algorithm for exactly computing an equilibrium for the linear utilities case of the market model defined by Fisher. Our algorithm uses the primal-dual paradigm in...