×

zbMATH — the first resource for mathematics

Vazirani, Vijay V.

Compute Distance To:
Author ID: vazirani.vijay-v Recent zbMATH articles by "Vazirani, Vijay V."
Published as: Vazirani, V. V.; Vazirani, Vijay; Vazirani, Vijay V.
External Links: MGP · Wikidata · GND
Documents Indexed: 123 Publications since 1982, including 4 Books
all top 5

Co-Authors

16 single-authored
13 Mehta, Ruta
10 Yannakakis, Mihalis
9 Garg, Jugal
9 Garg, Naveen Kumar
8 Jain, Kamal Kumar
7 Chakrabarty, Deeparnab
7 Jain, Kamal C.
7 Vazirani, Umesh V.
6 Devanur, Nikhil R.
6 Saran, Huzur
5 Mehta, Aranyak
4 Goel, Gagan
4 Khuller, Samir
4 Măndoiu, Ion I.
4 Saberi, Amin
4 Schulman, Leonard J.
4 Vigoda, Eric
4 Williamson, David P.
4 Yazdanbod, Sadra
3 Mai, Tung
3 Mitchell, Stephen G.
2 Anari, Nima
2 Arkin, Adam P.
2 Bezáková, Ivona
2 Bhatnagar, Nayantara
2 Goemans, Michel X.
2 Kapoor, Sanjiv
2 Karp, Richard Manning
2 Lawler, Eugene L.
2 Mahdian, Mohammad
2 Markakis, Evangelos
2 Mihail, Milena
2 Narayanan, Harish
2 Panageas, Ioannis
2 Pearson, David William
2 Rajagopalan, Sridhar
2 Randall, Dana J.
2 Štefankovič, Daniel
2 Tardos, Éva
2 Valiant, Leslie Gabriel
2 Wang, Lei
2 Wolf, Denise M.
2 Yu, Changyuan
1 Adler, Micah
1 Arora, Vivek
1 Balcan, Maria-Florina
1 Berger, Noam
1 Daniely, Amit
1 Garg, Dinesh
1 Garg, Rahul
1 Gupta, Anupam
1 Hajiaghayi, Mohammad Taghi
1 Halperin, Eran
1 Jain, Karan
1 Jam, Kamal
1 Jansen, Klaus
1 Jerrum, Mark R.
1 Kapur, Nevin
1 Kozen, Dexter C.
1 Lau, Lap Chi
1 Leighton, Frank Thomson
1 Leonardi, Stefano
1 Luby, Michael G.
1 Mulmuley, Ketan D.
1 Nagarajan, Viswanath
1 Naor, Dalit
1 Nisan, Noam
1 Oveis Gharan, Shayan
1 Papadimitriou, Christos Harilaos
1 Piliouras, Georgios
1 Rabin, Michael O.
1 Rajan, Bikash Sundar
1 Rivest, Ronald Linn
1 Roughgarden, Tim
1 Russell, Adrian R.
1 Santosh, Vempala S.
1 Shenker, Scott J.
1 Sinha, Saurabh
1 Sohoni, Milind A.
1 Sohoni, Milind G.
1 Stockmeyer, Larry J.
1 Talwar, Kunal
1 Tetali, Prasad
1 Thompson, Clark D.
1 Tong, Po
1 Urner, Ruth
1 Venkatesan, Ramarathnam
1 Ye, Yinyu
1 Yuval, Gideon

Publications by Year

Citations contained in zbMATH Open

99 Publications have been cited 2,151 times in 1,778 Documents Cited by Year
Approximation algorithms for metric facility location and \(k\)-median problems using the primal-dual schema and Lagrangian relaxation. Zbl 1138.90417
Jain, Kamal; Vazirani, Vijay V.
307
2001
Algorithmic game theory. Foreword by Christos H. Papadimitriou. Zbl 1130.91005
Nisan, Noam (ed.); Roughgarden, Tim (ed.); Tardos, Éva (ed.); Vazirani, Vijay V. (ed.)
216
2007
Random generation of combinatorial structures from a uniform distribution. Zbl 0597.68056
Jerrum, Mark R.; Valiant, Leslie G.; Vazirani, Vijay V.
169
1986
Matching is as easy as matrix inversion. Zbl 0632.68041
Mulmuley, Ketan; Vazirani, Umesh V.; Vazirani, Vijay V.
135
1987
NP is as easy as detecting unique solutions. Zbl 0621.68030
Valiant, L. G.; Vazirani, V. V.
126
1986
Primal-dual approximation algorithms for integral flow and multicut in trees. Zbl 0873.68075
Garg, N.; Vazirani, V. V.; Yannakakis, M.
103
1997
Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. Zbl 1325.90060
Jain, Kamal; Mahdian, Mohammad; Markakis, Evangelos; Saberi, Amin; Vazirani, Vijay V.
85
2003
NP-completeness of some generalizations of the maximum matching problem. Zbl 0493.68039
Stockmeyer, Larry J.; Vazirani, Vijay V.
76
1982
Approximation algorithms. Zbl 1005.68002
Vazirani, Vijay V.
67
1999
Approximate max-flow min-(multi)cut theorems and their applications. Zbl 0844.68061
Garg, Naveen; Vazirani, Vijay V.; Yannakakis, Mihalis
62
1996
AdWords and generalized online matching. Zbl 1312.68239
Mehta, Aranyak; Saberi, Amin; Vazirani, Umesh V.; Vazirani, Vijay V.
59
2007
Multiway cuts in node weighted graphs. Zbl 1068.68178
Garg, Naveen; Vazirani, Vijay V.; Yannakakis, Mihalis
55
2004
Applications of approximation algorithms to cooperative games. Zbl 1323.68570
Jain, Kamal; Vazirani, Vijay
49
2001
Finding \(k\) cuts within twice the optimal. Zbl 0828.68082
Saran, Huzur; Vazirani, Vijay V.
39
1995
Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs. Zbl 0696.68076
Vazirani, Vijay V.; Yannakakis, Milhalis
31
1989
Market equilibrium via a primal-dual algorithm for a convex program. Zbl 1325.91024
Devanur, Nikhil R.; Papadimitriou, Christos H.; Saberi, Amin; Vazirani, Vijay V.
29
2008
A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm. Zbl 0806.05058
Vazirani, Vijay V.
28
1994
On-line algorithms for weighted bipartite matching and stable marriages. Zbl 0938.68934
Khuller, Samir; Mitchell, Stephen G.; Vazirani, Vijay V.
25
1994
Approximate MAX-flow MIN-(multi)cut theorems and their applications. Zbl 1310.05198
Garg, Naveen; Vazirani, Vijay V.; Yannakakis, Mihalis
22
1993
Primal-dual RNC approximation algorithms for set cover and covering integer programs. Zbl 0914.68096
Rajagopalan, Sridhar; Vazirani, Vijay V.
21
1998
A primal-dual approximation algorithm for generalized Steiner network problems. Zbl 0838.90133
Williamson, David P.; Goemans, Michel X.; Mihail, Milena; Vazirani, Vijay V.
19
1995
NC algorithms for comparability graphs, interval graphs, and testing for unique perfect matching. Zbl 0598.68050
Kozen, Dexter; Vazirani, Umesh V.; Vazirani, Vijay V.
19
1985
Global wire routing in two-dimensional arrays. Zbl 0634.94024
Karp, R. M.; Leighton, F. T.; Rivest, R. L.; Thompson, C. D.; Vazirani, U. V.; Vazirani, V. V.
17
1987
Maximum matchings in general graphs through randomization. Zbl 0689.68092
Rabin, Michael O.; Vazirani, Vijay V.
16
1989
NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems. Zbl 0673.05075
Vazirani, Vijay V.
16
1989
On the bidirected cut relaxation for the metric Steiner tree problem (extended abstract). Zbl 0938.68072
Rajagopalan, Sridhar; Vazirani, Vijay V.
14
1999
Solving the weighted parity problem for gammoids by reduction to graphic matching. Zbl 0566.05017
Tong, Po; Lawler, E. L.; Vazirani, V. V.
13
1984
Accelerating simulated annealing for the permanent and combinatorial counting problems. Zbl 1225.68270
Bezáková, Ivona; Štefankovič, Daniel; Vazirani, Vijay V.; Vigoda, Eric
12
2008
Market equilibria for homothetic, quasi-concave utilities and economies of scale in production. Zbl 1297.91107
Jain, Kamal; Vazirani, Vijay V.; Ye, Yinyu
12
2005
Multiway cuts in directed and node weighted graphs (extended abstract). Zbl 1418.68168
Garg, Naveen; Vazirani, Vijay V.; Yannakakis, Mihalis
12
1994
Eisenberg-Gale markets: algorithms and structural properties. Zbl 1232.91452
Jam, Kamal; Vazirani, Vijay V.
11
2007
An approximation algorithm for the fault tolerant metric facility location problem. Zbl 1138.90416
Jain, Kamal; Vazirani, Vijay V.
11
2004
An efficient algorithm for constructing minimal trellises for codes over finite abelian groups. Zbl 0874.94038
Vazirani, Vijay V.; Saran, Huzur; Rajan, B. Sundar
11
1996
Market equilibrium under separable, piecewise-linear, concave utilities. Zbl 1327.91042
Vazirani, Vijay V.; Yannakakis, Mihalis
10
2011
Spending constraint utilities with applications to the Adwords market. Zbl 1216.91011
Vazirani, Vijay V.
10
2010
A stochastic process on the hypercube with applications to peer-to-peer networks. Zbl 1192.68018
Adler, Micah; Halperin, Eran; Karp, Richard M.; Vazirani, Vijay V.
10
2003
A primal-dual approximation algorithm for generalized Steiner network problems. Zbl 1310.90116
Williamson, David P.; Goemans, Michel X.; Mihail, Milena; Vazirani, Vijay V.
9
1993
Improved bounds for the max-flow min-multicut ratio for planar and \(K_{r,r}\)-free graphs. Zbl 0803.90056
Tardos, Éva; Vazirani, Vijay V.
9
1993
Efficient and secure pseudo-random number generation. Zbl 0579.65005
Vazirani, Umesh V.; Vazirani, Vijay V.
9
1985
Scheduling open shops with parallel machines. Zbl 0489.90053
Lawler, E. L.; Luby, M. G.; Vazirani, V. V.
9
1982
ETR-completeness for decision versions of multi-player (symmetric) Nash equilibria. Zbl 1441.68072
Garg, Jugal; Mehta, Ruta; Vazirani, Vijay V.; Yazdanbod, Sadra
8
2015
A greedy facility location algorithm analyzed using dual fitting. Zbl 0998.68701
Mahdian, Mohammad; Markakis, Evangelos; Saberi, Amin; Vazirani, Vijay
8
2001
Representing and enumerating edge connectivity cuts in \(\mathcal {RNC}\). Zbl 0765.68041
Naor, Dalit; Vazirani, Vijay V.
8
1991
A natural encoding scheme proved probabilistic polynomial complete. Zbl 0525.68025
Vazirani, Umesh V.; Vazirani, Vijay V.
8
1983
Allocation of divisible goods under lexicographic preferences. Zbl 1369.91109
Schulman, Leonard J.; Vazirani, Vijay V.
7
2015
Eisenberg-Gale markets: algorithms and game-theoretic properties. Zbl 1201.91110
Jain, Kamal; Vazirani, Vijay V.
7
2010
Combinatorial algorithms for market equilibria. Zbl 1151.91616
Vazirani, Vijay V.
7
2007
Minimum multicolored subgraph problem in multiplex PCR primer set selection and population haplotyping. Zbl 1155.92338
Hajiaghayi, M. T.; Jain, K.; Lau, L. C.; Măndoiu, I. I.; Russell, A.; Vazirani, V. V.
7
2006
Randomized parallel algorithms for matroid union and intersection, with applications to arborescences and edge-disjoint spanning trees. Zbl 0796.05021
Narayanan, H.; Saran, Huzur; Vazirani, Vijay V.
7
1994
The two-processor scheduling problem is in random NC. Zbl 0692.68043
Vazirani, Umesh V.; Vazirani, Vijay V.
6
1989
The notion of a rational convex program, and an algorithm for the Arrow-Debreu Nash bargaining game. Zbl 1281.91095
Vazirani, Vijay V.
5
2012
Equitable cost allocations via primal-dual-type algorithms. Zbl 1192.90107
Jain, Kamal; Vazirani, Vijay V.
5
2002
A graph theoretic approach to software watermarking. Zbl 1008.68663
Venkatesan, Ramarathnam; Vazirani, Vijay; Sinha, Saurabh
5
2001
Processor efficient parallel algorithms for the two disjoint paths problem and for finding a Kuratowski homeomorph. Zbl 0761.68074
Khuller, Samir; Mitchell, Stephen G.; Vazirani, Vijay V.
5
1992
Planar graph coloring is not self-reducible, assuming P\(\neq NP\). Zbl 0729.05019
Khuller, Samir; Vazirani, Vijay V.
5
1991
Pfaffian orientations, 0/1 permanents, and even cycles in directed graphs. Zbl 0648.68060
Vazirani, Vijay V.; Yannakakis, Mihalis
5
1988
A complementary pivot algorithm for market equilibrium under separable, piecewise-linear concave utilities. Zbl 1410.91325
Garg, Jugal; Mehta, Ruta; Sohoni, Milind; Vazirani, Vijay V.
4
2015
Accelerating simulated annealing for the permanent and combinatorial counting problems. Zbl 1192.90160
Bezáková, Ivona; Štefankovič, Daniel; Vazirani, Vijay V.; Vigoda, Eric
4
2006
An auction-based market equilibrium algorithm for the separable gross substitutability case. Zbl 1105.91303
Garg, Rahul; Kapoor, Sanjiv; Vazirani, Vijay
4
2004
An improved approximation scheme for computing Arrow-Debreu prices for the linear case. Zbl 1205.91109
Devanur, Nikhil R.; Vazirani, Vijay V.
4
2003
An approximation algorithm for the fault tolerant metric facility location problem. Zbl 0976.90056
Jain, Kamal; Vazirani, Vijay V.
4
2000
Recent results on approximating the Steiner tree problem and its generalizations. Zbl 0953.68120
Vazirani, Vijay V.
4
2000
Finding separator cuts in planar graphs within twice the optimal. Zbl 0943.68077
Garg, Naveen; Saran, Huzur; Vazirani, Vijay V.
4
1999
A primal-dual schema based approximation algorithm for the element connectivity problem. Zbl 0934.68110
Jain, Kamal; Măndoiu, Ion; Vazirani, Vijay V.; Williamson, David P.
4
1999
On-line algorithms for weighted bipartite matching and stable marriages. Zbl 0768.68154
Khuller, Samir; Mitchell, Stephen G.; Vazirani, Vijay V.
4
1991
Rationality and strongly polynomial solvability of Eisenberg-Gale markets with two agents. Zbl 1229.91125
Chakrabarty, Deeparnab; Devanur, Nikhil R.; Vazirani, Vijay V.
3
2010
2-player Nash and nonsymmetric bargaining games: algorithms and structural properties. Zbl 1310.91008
Vazirani, Vijay V.
3
2010
Solvency games. Zbl 1248.91021
Berger, Noam; Kapur, Nevin; Schulman, Leonard J.; Vazirani, Vijay V.
3
2008
Nash bargaining via flexible budget markets. (Abstract). Zbl 1143.91326
Vazirani, Vijay V.
3
2008
New geometry-inspired relaxations and algorithms for the metric Steiner tree problem. Zbl 1143.90376
Chakrabarty, Deeparnab; Devanur, Nikhil R.; Vazirani, Vijay V.
3
2008
Efficient sequential and parallel algorithms for maximal bipartite sets. Zbl 0764.68130
Pearson, David; Vazirani, Vijay V.
3
1993
Nash social welfare for indivisible items under separable, piecewise-linear concave utilities. Zbl 1403.91204
Anari, Nima; Mai, Tung; Oveis Gharan, Shayan; Vazirani, Vijay V.
2
2018
Mutation, sexual reproduction and survival in dynamic environments. Zbl 1402.92318
Mehta, Ruta; Panageas, Ioannis; Piliouras, Georgios; Tetali, Prasad; Vazirani, Vijay V.
2
2017
Settling the complexity of Leontief and PLC exchange markets under exact and approximate equilibria. Zbl 1371.91126
Garg, Jugal; Mehta, Ruta; Vazirani, Vijay V.; Yazdanbod, Sadra
2
2017
Settling some open problems on 2-player symmetric Nash equilibria. Zbl 1358.91004
Mehta, Ruta; Vazirani, Vijay V.; Yazdanbod, Sadra
2
2015
Dichotomies in equilibrium computation, and complementary pivot algorithms for a new class of non-separable utility functions. Zbl 1315.91040
Garg, Jugal; Mehta, Ruta; Vazirani, Vijay V.
2
2014
Learning economic parameters from revealed preferences. Zbl 1406.91095
Balcan, Maria-Florina; Daniely, Amit; Mehta, Ruta; Urner, Ruth; Vazirani, Vijay V.
2
2014
A complementary pivot algorithm for markets under separable, piecewise-linear concave utilities. Zbl 1286.90091
Garg, Jugal; Mehta, Ruta; Sohoni, Milind; Vazirani, Vijay V.
2
2012
Rational convex programs and efficient algorithms for 2-player Nash and nonsymmetric bargaining games. Zbl 1258.68189
Vazirani, Vijay V.
2
2012
A perfect price discrimination market model with production, and a rational convex program for it. Zbl 1238.91095
Goel, Gagan; Vazirani, Vijay V.
2
2011
New geometry-inspired relaxations and algorithms for the metric Steiner tree problem. Zbl 1231.90364
Chakrabarty, Deeparnab; Devanur, Nikhil R.; Vazirani, Vijay V.
2
2011
A primal-dual schema based approximation algorithm for the element connectivity problem. Zbl 1122.90351
Jain, Kamal; Măndoiu, Ion; Vazirani, Vijay V.; Williamson, David P.
2
2002
A polyhedron with all \(s-t\) cuts as vertices, and adjacency of cuts. Zbl 0845.90047
Garg, Naveen; Vazirani, Vijay V.
2
1995
NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems. Zbl 0651.68086
Vazirani, Vijay V.
2
1988
Dichotomies in equilibrium computation and membership of PLC markets in FIXP. Zbl 1415.91191
Garg, Jugal; Mehta, Ruta; Vazirani, Vijay V.
1
2016
On computability of equilibria in markets with production. Zbl 1425.91273
Garg, Jugal; Vazirani, Vijay V.
1
2014
Nonseparable, concave utilities are easy – in a perfect price discrimination market model. Zbl 1274.91239
Vazirani, Vijay V.
1
2013
Thrifty algorithms for multistage robust optimization. Zbl 1372.90092
Gupta, Anupam; Nagarajan, Viswanath; Vazirani, Vijay V.
1
2013
A perfect price discrimination market model with production, and a (rational) convex program for it. Zbl 1310.91072
Goel, Gagan; Vazirani, Vijay
1
2010
Equitable cost allocations via primal-dual-type algorithms. Zbl 1165.91014
Jain, Kamal; Vazirani, Vijay V.
1
2008
A primal-dual algorithm for computing Fisher equilibrium in the absence of gross substitutability property. Zbl 1294.91062
Garg, Dinesh; Jain, Kamal; Talwar, Kunal; Vazirani, Vijay V.
1
2007
On the capacity of multiple unicast sessions in undirected graphs. Zbl 1315.94118
Jain, Kamal; Vazirani, Vijay V.; Yuval, Gideon
1
2006
A computationally motivated definition of parametric estimation and its applications to the Gaussian distribution. Zbl 1095.68033
Schulman, Leonard J.; Vazirani, Vijay V.
1
2005
Primal-dual schema based approximation algorithms. Zbl 1054.68170
Vazirani, Vijay V.
1
2002
The “Art of trellis decoding” is computationally hard – for large fields. Zbl 0906.94024
Jain, Kamal; Măndoiu, Ion; Vazirani, Vijay V.
1
1998
Primal-dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover. Zbl 1418.68244
Garg, Naveen; Vazirani, Vijay V.; Yannakakis, Mihalis
1
1993
A polyhedron with all \(s-t\) cuts as vertices, and adjacency of cuts. Zbl 0923.90059
Garg, Naveen; Vazirani, Vijay V.
1
1993
Suboptimal cuts: their enumeration, weight and number (extended abstract). Zbl 1427.68254
Vazirani, Vijay V.; Yannakakis, Mihalis
1
1992
Randomized parallel algorithms for matroid union and intersection, with applications to arboresences and edge-disjoint spanning trees. Zbl 0815.05021
Narayanan, H.; Saran, Huzur; Vazirani, Vijay V.
1
1992
Nash social welfare for indivisible items under separable, piecewise-linear concave utilities. Zbl 1403.91204
Anari, Nima; Mai, Tung; Oveis Gharan, Shayan; Vazirani, Vijay V.
2
2018
Mutation, sexual reproduction and survival in dynamic environments. Zbl 1402.92318
Mehta, Ruta; Panageas, Ioannis; Piliouras, Georgios; Tetali, Prasad; Vazirani, Vijay V.
2
2017
Settling the complexity of Leontief and PLC exchange markets under exact and approximate equilibria. Zbl 1371.91126
Garg, Jugal; Mehta, Ruta; Vazirani, Vijay V.; Yazdanbod, Sadra
2
2017
Dichotomies in equilibrium computation and membership of PLC markets in FIXP. Zbl 1415.91191
Garg, Jugal; Mehta, Ruta; Vazirani, Vijay V.
1
2016
ETR-completeness for decision versions of multi-player (symmetric) Nash equilibria. Zbl 1441.68072
Garg, Jugal; Mehta, Ruta; Vazirani, Vijay V.; Yazdanbod, Sadra
8
2015
Allocation of divisible goods under lexicographic preferences. Zbl 1369.91109
Schulman, Leonard J.; Vazirani, Vijay V.
7
2015
A complementary pivot algorithm for market equilibrium under separable, piecewise-linear concave utilities. Zbl 1410.91325
Garg, Jugal; Mehta, Ruta; Sohoni, Milind; Vazirani, Vijay V.
4
2015
Settling some open problems on 2-player symmetric Nash equilibria. Zbl 1358.91004
Mehta, Ruta; Vazirani, Vijay V.; Yazdanbod, Sadra
2
2015
Dichotomies in equilibrium computation, and complementary pivot algorithms for a new class of non-separable utility functions. Zbl 1315.91040
Garg, Jugal; Mehta, Ruta; Vazirani, Vijay V.
2
2014
Learning economic parameters from revealed preferences. Zbl 1406.91095
Balcan, Maria-Florina; Daniely, Amit; Mehta, Ruta; Urner, Ruth; Vazirani, Vijay V.
2
2014
On computability of equilibria in markets with production. Zbl 1425.91273
Garg, Jugal; Vazirani, Vijay V.
1
2014
Nonseparable, concave utilities are easy – in a perfect price discrimination market model. Zbl 1274.91239
Vazirani, Vijay V.
1
2013
Thrifty algorithms for multistage robust optimization. Zbl 1372.90092
Gupta, Anupam; Nagarajan, Viswanath; Vazirani, Vijay V.
1
2013
The notion of a rational convex program, and an algorithm for the Arrow-Debreu Nash bargaining game. Zbl 1281.91095
Vazirani, Vijay V.
5
2012
A complementary pivot algorithm for markets under separable, piecewise-linear concave utilities. Zbl 1286.90091
Garg, Jugal; Mehta, Ruta; Sohoni, Milind; Vazirani, Vijay V.
2
2012
Rational convex programs and efficient algorithms for 2-player Nash and nonsymmetric bargaining games. Zbl 1258.68189
Vazirani, Vijay V.
2
2012
Market equilibrium under separable, piecewise-linear, concave utilities. Zbl 1327.91042
Vazirani, Vijay V.; Yannakakis, Mihalis
10
2011
A perfect price discrimination market model with production, and a rational convex program for it. Zbl 1238.91095
Goel, Gagan; Vazirani, Vijay V.
2
2011
New geometry-inspired relaxations and algorithms for the metric Steiner tree problem. Zbl 1231.90364
Chakrabarty, Deeparnab; Devanur, Nikhil R.; Vazirani, Vijay V.
2
2011
Spending constraint utilities with applications to the Adwords market. Zbl 1216.91011
Vazirani, Vijay V.
10
2010
Eisenberg-Gale markets: algorithms and game-theoretic properties. Zbl 1201.91110
Jain, Kamal; Vazirani, Vijay V.
7
2010
Rationality and strongly polynomial solvability of Eisenberg-Gale markets with two agents. Zbl 1229.91125
Chakrabarty, Deeparnab; Devanur, Nikhil R.; Vazirani, Vijay V.
3
2010
2-player Nash and nonsymmetric bargaining games: algorithms and structural properties. Zbl 1310.91008
Vazirani, Vijay V.
3
2010
A perfect price discrimination market model with production, and a (rational) convex program for it. Zbl 1310.91072
Goel, Gagan; Vazirani, Vijay
1
2010
Market equilibrium via a primal-dual algorithm for a convex program. Zbl 1325.91024
Devanur, Nikhil R.; Papadimitriou, Christos H.; Saberi, Amin; Vazirani, Vijay V.
29
2008
Accelerating simulated annealing for the permanent and combinatorial counting problems. Zbl 1225.68270
Bezáková, Ivona; Štefankovič, Daniel; Vazirani, Vijay V.; Vigoda, Eric
12
2008
Solvency games. Zbl 1248.91021
Berger, Noam; Kapur, Nevin; Schulman, Leonard J.; Vazirani, Vijay V.
3
2008
Nash bargaining via flexible budget markets. (Abstract). Zbl 1143.91326
Vazirani, Vijay V.
3
2008
New geometry-inspired relaxations and algorithms for the metric Steiner tree problem. Zbl 1143.90376
Chakrabarty, Deeparnab; Devanur, Nikhil R.; Vazirani, Vijay V.
3
2008
Equitable cost allocations via primal-dual-type algorithms. Zbl 1165.91014
Jain, Kamal; Vazirani, Vijay V.
1
2008
Algorithmic game theory. Foreword by Christos H. Papadimitriou. Zbl 1130.91005
Nisan, Noam (ed.); Roughgarden, Tim (ed.); Tardos, Éva (ed.); Vazirani, Vijay V. (ed.)
216
2007
AdWords and generalized online matching. Zbl 1312.68239
Mehta, Aranyak; Saberi, Amin; Vazirani, Umesh V.; Vazirani, Vijay V.
59
2007
Eisenberg-Gale markets: algorithms and structural properties. Zbl 1232.91452
Jam, Kamal; Vazirani, Vijay V.
11
2007
Combinatorial algorithms for market equilibria. Zbl 1151.91616
Vazirani, Vijay V.
7
2007
A primal-dual algorithm for computing Fisher equilibrium in the absence of gross substitutability property. Zbl 1294.91062
Garg, Dinesh; Jain, Kamal; Talwar, Kunal; Vazirani, Vijay V.
1
2007
Minimum multicolored subgraph problem in multiplex PCR primer set selection and population haplotyping. Zbl 1155.92338
Hajiaghayi, M. T.; Jain, K.; Lau, L. C.; Măndoiu, I. I.; Russell, A.; Vazirani, V. V.
7
2006
Accelerating simulated annealing for the permanent and combinatorial counting problems. Zbl 1192.90160
Bezáková, Ivona; Štefankovič, Daniel; Vazirani, Vijay V.; Vigoda, Eric
4
2006
On the capacity of multiple unicast sessions in undirected graphs. Zbl 1315.94118
Jain, Kamal; Vazirani, Vijay V.; Yuval, Gideon
1
2006
Market equilibria for homothetic, quasi-concave utilities and economies of scale in production. Zbl 1297.91107
Jain, Kamal; Vazirani, Vijay V.; Ye, Yinyu
12
2005
A computationally motivated definition of parametric estimation and its applications to the Gaussian distribution. Zbl 1095.68033
Schulman, Leonard J.; Vazirani, Vijay V.
1
2005
Multiway cuts in node weighted graphs. Zbl 1068.68178
Garg, Naveen; Vazirani, Vijay V.; Yannakakis, Mihalis
55
2004
An approximation algorithm for the fault tolerant metric facility location problem. Zbl 1138.90416
Jain, Kamal; Vazirani, Vijay V.
11
2004
An auction-based market equilibrium algorithm for the separable gross substitutability case. Zbl 1105.91303
Garg, Rahul; Kapoor, Sanjiv; Vazirani, Vijay
4
2004
Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. Zbl 1325.90060
Jain, Kamal; Mahdian, Mohammad; Markakis, Evangelos; Saberi, Amin; Vazirani, Vijay V.
85
2003
A stochastic process on the hypercube with applications to peer-to-peer networks. Zbl 1192.68018
Adler, Micah; Halperin, Eran; Karp, Richard M.; Vazirani, Vijay V.
10
2003
An improved approximation scheme for computing Arrow-Debreu prices for the linear case. Zbl 1205.91109
Devanur, Nikhil R.; Vazirani, Vijay V.
4
2003
Equitable cost allocations via primal-dual-type algorithms. Zbl 1192.90107
Jain, Kamal; Vazirani, Vijay V.
5
2002
A primal-dual schema based approximation algorithm for the element connectivity problem. Zbl 1122.90351
Jain, Kamal; Măndoiu, Ion; Vazirani, Vijay V.; Williamson, David P.
2
2002
Primal-dual schema based approximation algorithms. Zbl 1054.68170
Vazirani, Vijay V.
1
2002
Approximation algorithms for metric facility location and \(k\)-median problems using the primal-dual schema and Lagrangian relaxation. Zbl 1138.90417
Jain, Kamal; Vazirani, Vijay V.
307
2001
Applications of approximation algorithms to cooperative games. Zbl 1323.68570
Jain, Kamal; Vazirani, Vijay
49
2001
A greedy facility location algorithm analyzed using dual fitting. Zbl 0998.68701
Mahdian, Mohammad; Markakis, Evangelos; Saberi, Amin; Vazirani, Vijay
8
2001
A graph theoretic approach to software watermarking. Zbl 1008.68663
Venkatesan, Ramarathnam; Vazirani, Vijay; Sinha, Saurabh
5
2001
An approximation algorithm for the fault tolerant metric facility location problem. Zbl 0976.90056
Jain, Kamal; Vazirani, Vijay V.
4
2000
Recent results on approximating the Steiner tree problem and its generalizations. Zbl 0953.68120
Vazirani, Vijay V.
4
2000
Approximation algorithms. Zbl 1005.68002
Vazirani, Vijay V.
67
1999
On the bidirected cut relaxation for the metric Steiner tree problem (extended abstract). Zbl 0938.68072
Rajagopalan, Sridhar; Vazirani, Vijay V.
14
1999
Finding separator cuts in planar graphs within twice the optimal. Zbl 0943.68077
Garg, Naveen; Saran, Huzur; Vazirani, Vijay V.
4
1999
A primal-dual schema based approximation algorithm for the element connectivity problem. Zbl 0934.68110
Jain, Kamal; Măndoiu, Ion; Vazirani, Vijay V.; Williamson, David P.
4
1999
Primal-dual RNC approximation algorithms for set cover and covering integer programs. Zbl 0914.68096
Rajagopalan, Sridhar; Vazirani, Vijay V.
21
1998
The “Art of trellis decoding” is computationally hard – for large fields. Zbl 0906.94024
Jain, Kamal; Măndoiu, Ion; Vazirani, Vijay V.
1
1998
Primal-dual approximation algorithms for integral flow and multicut in trees. Zbl 0873.68075
Garg, N.; Vazirani, V. V.; Yannakakis, M.
103
1997
Approximate max-flow min-(multi)cut theorems and their applications. Zbl 0844.68061
Garg, Naveen; Vazirani, Vijay V.; Yannakakis, Mihalis
62
1996
An efficient algorithm for constructing minimal trellises for codes over finite abelian groups. Zbl 0874.94038
Vazirani, Vijay V.; Saran, Huzur; Rajan, B. Sundar
11
1996
Finding \(k\) cuts within twice the optimal. Zbl 0828.68082
Saran, Huzur; Vazirani, Vijay V.
39
1995
A primal-dual approximation algorithm for generalized Steiner network problems. Zbl 0838.90133
Williamson, David P.; Goemans, Michel X.; Mihail, Milena; Vazirani, Vijay V.
19
1995
A polyhedron with all \(s-t\) cuts as vertices, and adjacency of cuts. Zbl 0845.90047
Garg, Naveen; Vazirani, Vijay V.
2
1995
A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm. Zbl 0806.05058
Vazirani, Vijay V.
28
1994
On-line algorithms for weighted bipartite matching and stable marriages. Zbl 0938.68934
Khuller, Samir; Mitchell, Stephen G.; Vazirani, Vijay V.
25
1994
Multiway cuts in directed and node weighted graphs (extended abstract). Zbl 1418.68168
Garg, Naveen; Vazirani, Vijay V.; Yannakakis, Mihalis
12
1994
Randomized parallel algorithms for matroid union and intersection, with applications to arborescences and edge-disjoint spanning trees. Zbl 0796.05021
Narayanan, H.; Saran, Huzur; Vazirani, Vijay V.
7
1994
Approximate MAX-flow MIN-(multi)cut theorems and their applications. Zbl 1310.05198
Garg, Naveen; Vazirani, Vijay V.; Yannakakis, Mihalis
22
1993
A primal-dual approximation algorithm for generalized Steiner network problems. Zbl 1310.90116
Williamson, David P.; Goemans, Michel X.; Mihail, Milena; Vazirani, Vijay V.
9
1993
Improved bounds for the max-flow min-multicut ratio for planar and \(K_{r,r}\)-free graphs. Zbl 0803.90056
Tardos, Éva; Vazirani, Vijay V.
9
1993
Efficient sequential and parallel algorithms for maximal bipartite sets. Zbl 0764.68130
Pearson, David; Vazirani, Vijay V.
3
1993
Primal-dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover. Zbl 1418.68244
Garg, Naveen; Vazirani, Vijay V.; Yannakakis, Mihalis
1
1993
A polyhedron with all \(s-t\) cuts as vertices, and adjacency of cuts. Zbl 0923.90059
Garg, Naveen; Vazirani, Vijay V.
1
1993
Processor efficient parallel algorithms for the two disjoint paths problem and for finding a Kuratowski homeomorph. Zbl 0761.68074
Khuller, Samir; Mitchell, Stephen G.; Vazirani, Vijay V.
5
1992
Suboptimal cuts: their enumeration, weight and number (extended abstract). Zbl 1427.68254
Vazirani, Vijay V.; Yannakakis, Mihalis
1
1992
Randomized parallel algorithms for matroid union and intersection, with applications to arboresences and edge-disjoint spanning trees. Zbl 0815.05021
Narayanan, H.; Saran, Huzur; Vazirani, Vijay V.
1
1992
Representing and enumerating edge connectivity cuts in \(\mathcal {RNC}\). Zbl 0765.68041
Naor, Dalit; Vazirani, Vijay V.
8
1991
Planar graph coloring is not self-reducible, assuming P\(\neq NP\). Zbl 0729.05019
Khuller, Samir; Vazirani, Vijay V.
5
1991
On-line algorithms for weighted bipartite matching and stable marriages. Zbl 0768.68154
Khuller, Samir; Mitchell, Stephen G.; Vazirani, Vijay V.
4
1991
Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs. Zbl 0696.68076
Vazirani, Vijay V.; Yannakakis, Milhalis
31
1989
Maximum matchings in general graphs through randomization. Zbl 0689.68092
Rabin, Michael O.; Vazirani, Vijay V.
16
1989
NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems. Zbl 0673.05075
Vazirani, Vijay V.
16
1989
The two-processor scheduling problem is in random NC. Zbl 0692.68043
Vazirani, Umesh V.; Vazirani, Vijay V.
6
1989
Pfaffian orientations, 0/1 permanents, and even cycles in directed graphs. Zbl 0648.68060
Vazirani, Vijay V.; Yannakakis, Mihalis
5
1988
NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems. Zbl 0651.68086
Vazirani, Vijay V.
2
1988
Matching is as easy as matrix inversion. Zbl 0632.68041
Mulmuley, Ketan; Vazirani, Umesh V.; Vazirani, Vijay V.
135
1987
Global wire routing in two-dimensional arrays. Zbl 0634.94024
Karp, R. M.; Leighton, F. T.; Rivest, R. L.; Thompson, C. D.; Vazirani, U. V.; Vazirani, V. V.
17
1987
Random generation of combinatorial structures from a uniform distribution. Zbl 0597.68056
Jerrum, Mark R.; Valiant, Leslie G.; Vazirani, Vijay V.
169
1986
NP is as easy as detecting unique solutions. Zbl 0621.68030
Valiant, L. G.; Vazirani, V. V.
126
1986
NC algorithms for comparability graphs, interval graphs, and testing for unique perfect matching. Zbl 0598.68050
Kozen, Dexter; Vazirani, Umesh V.; Vazirani, Vijay V.
19
1985
Efficient and secure pseudo-random number generation. Zbl 0579.65005
Vazirani, Umesh V.; Vazirani, Vijay V.
9
1985
Solving the weighted parity problem for gammoids by reduction to graphic matching. Zbl 0566.05017
Tong, Po; Lawler, E. L.; Vazirani, V. V.
13
1984
A natural encoding scheme proved probabilistic polynomial complete. Zbl 0525.68025
Vazirani, Umesh V.; Vazirani, Vijay V.
8
1983
NP-completeness of some generalizations of the maximum matching problem. Zbl 0493.68039
Stockmeyer, Larry J.; Vazirani, Vijay V.
76
1982
Scheduling open shops with parallel machines. Zbl 0489.90053
Lawler, E. L.; Luby, M. G.; Vazirani, V. V.
9
1982
all top 5

Cited by 2,830 Authors

51 Xu, Dachuan
24 Vazirani, Vijay V.
23 Du, Donglei
20 Wu, Chenchen
16 Goldberg, Leslie Ann
15 Jerrum, Mark R.
13 Bentz, Cédric
13 Spirakis, Paul G.
13 Zhang, Dongmei
11 Segev, Danny
11 Williamson, David P.
10 Guo, Jiong
10 Nagamochi, Hiroshi
10 Nagarajan, Viswanath
10 Niedermeier, Rolf
10 Paschos, Vangelis Th.
10 Rautenbach, Dieter
9 Buchbinder, Niv
9 Caragiannis, Ioannis
9 Chekuri, Chandra S.
9 Elbassioni, Khaled M.
9 Saurabh, Saket
8 Dyer, Martin E.
8 Gupta, Anupam
8 Hoefer, Martin
8 Kratsch, Stefan
8 Manlove, David F.
8 Manthey, Bodo
8 Mehta, Ruta
8 Mirrokni, Vahab S.
8 Tardos, Éva
8 Watanabe, Osamu
8 Zhang, Peng
7 Arvind, Vikraman
7 Bezáková, Ivona
7 Bilò, Vittorio
7 Chrobak, Marek
7 Flammini, Michele
7 Garg, Jugal
7 Hajiaghayi, Mohammad Taghi
7 Huber, Mark L.
7 Kaklamanis, Christos
7 Karpinski, Marek
7 Köbler, Johannes
7 Könemann, Jochen
7 Levin, Asaf
7 Naor, Joseph Seffi
7 Parekh, Ojas
7 Pruhs, Kirk R.
7 Serna, Maria José
7 Vigoda, Eric
7 Wahlström, Magnus
7 Wang, Yishui
7 Yannakakis, Mihalis
6 Chen, Zhizhong
6 Costa, Marie-Christine
6 Cygan, Marek
6 Fukunaga, Takuro
6 Galanis, Andreas
6 Gurvich, Vladimir A.
6 Hemaspaandra, Lane A.
6 Hochbaum, Dorit S.
6 Karp, Richard Manning
6 Kobayashi, Yusuke
6 Kortsarz, Guy
6 Maffioli, Francesco
6 Mehlhorn, Kurt
6 Mestre, Julián
6 Moscardelli, Luca
6 Papadimitriou, Christos Harilaos
6 Randall, Dana J.
6 Ravi, Ramamoorthi
6 Rothe, Jörg-Matthias
6 Schafer, Guido
6 Sinclair, Alistair
6 Stein, Clifford
6 Xu, Chao
6 Xu, Jinhui
6 Ye, Yinyu
5 Bansal, Nikhil
5 Boros, Endre
5 Cameron, Kathie
5 Chen, Jian-er
5 Datta, Samir
5 Feige, Uriel
5 Fotakis, Dimitris A.
5 Galbiati, Giulia
5 Goemans, Michel X.
5 Goldreich, Oded
5 Guruswami, Venkatesan
5 Hermelin, Danny
5 Hirai, Hiroshi
5 Ibaraki, Toshihide
5 Joos, Felix Claudius
5 Koutsoupias, Elias
5 Krysta, Piotr
5 Kulik, Ariel
5 Kumar, Amit
5 Kyropoulou, Maria
5 Li, Yu
...and 2,730 more Authors
all top 5

Cited in 209 Serials

219 Theoretical Computer Science
123 Algorithmica
103 Discrete Applied Mathematics
80 Information Processing Letters
72 Journal of Computer and System Sciences
52 European Journal of Operational Research
51 Mathematical Programming. Series A. Series B
42 Operations Research Letters
40 Theory of Computing Systems
39 SIAM Journal on Computing
39 Journal of Combinatorial Optimization
37 Information and Computation
27 Games and Economic Behavior
25 Discrete Optimization
24 Computers & Operations Research
23 Journal of Discrete Algorithms
22 Discrete Mathematics
22 Combinatorica
21 Computational Complexity
18 Random Structures & Algorithms
14 SIAM Journal on Discrete Mathematics
13 Artificial Intelligence
13 Operations Research
13 Computer Science Review
11 Mathematics of Operations Research
11 Networks
10 Journal of Combinatorial Theory. Series B
10 International Journal of Foundations of Computer Science
10 Journal of Global Optimization
10 Optimization Letters
9 Information Sciences
8 Annals of Operations Research
8 Combinatorics, Probability and Computing
7 Journal of Economic Theory
7 Journal of Scheduling
6 Acta Mathematicae Applicatae Sinica. English Series
6 Linear Algebra and its Applications
6 INFORMS Journal on Computing
6 RAIRO. Operations Research
6 Journal of the Operations Research Society of China
5 The Annals of Statistics
5 Applied Mathematics and Computation
5 Automatica
5 Mathematical Systems Theory
5 Advances in Applied Mathematics
5 Probability Theory and Related Fields
5 Designs, Codes and Cryptography
5 International Journal of Computer Mathematics
5 Constraints
5 CEJOR. Central European Journal of Operations Research
5 Discrete Mathematics, Algorithms and Applications
4 Journal of Statistical Physics
4 Journal of Complexity
4 Discrete & Computational Geometry
4 Journal of Parallel and Distributed Computing
4 International Journal of Computational Geometry & Applications
4 Computational Geometry
4 Distributed Computing
4 Computational Optimization and Applications
4 Journal of Mathematical Sciences (New York)
4 Foundations of Computational Mathematics
4 4OR
4 ACM Transactions on Computation Theory
3 European Journal of Combinatorics
3 Mathematical Social Sciences
3 Journal of Cryptology
3 Japan Journal of Industrial and Applied Mathematics
3 SIAM Journal on Optimization
3 Journal of Computer and Systems Sciences International
3 Economic Theory
3 Annals of Mathematics and Artificial Intelligence
3 Mathematical Problems in Engineering
3 Parallel Algorithms and Applications
3 RAIRO. Theoretical Informatics and Applications
3 Trudy Instituta Matematiki
3 International Game Theory Review
3 OR Spectrum
3 Mathematical Programming Computation
3 ACM Transactions on Algorithms
2 Computers & Mathematics with Applications
2 Communications in Mathematical Physics
2 Journal of Mathematical Physics
2 Advances in Mathematics
2 BIT
2 International Journal of Game Theory
2 Journal of Applied Probability
2 Journal of Combinatorial Theory. Series A
2 Journal of Graph Theory
2 Journal of Mathematical Economics
2 Journal of Statistical Planning and Inference
2 Optimization
2 Asia-Pacific Journal of Operational Research
2 Journal of the American Mathematical Society
2 Machine Learning
2 Economics Letters
2 The Annals of Applied Probability
2 MSCS. Mathematical Structures in Computer Science
2 Automation and Remote Control
2 Proceedings of the National Academy of Sciences of the United States of America
2 Stochastic Processes and their Applications
...and 109 more Serials
all top 5

Cited in 37 Fields

1,071 Computer science (68-XX)
668 Operations research, mathematical programming (90-XX)
550 Combinatorics (05-XX)
355 Game theory, economics, finance, and other social and behavioral sciences (91-XX)
62 Numerical analysis (65-XX)
56 Probability theory and stochastic processes (60-XX)
53 Information and communication theory, circuits (94-XX)
42 Statistics (62-XX)
29 Mathematical logic and foundations (03-XX)
28 Statistical mechanics, structure of matter (82-XX)
25 Linear and multilinear algebra; matrix theory (15-XX)
25 Biology and other natural sciences (92-XX)
23 Convex and discrete geometry (52-XX)
11 Number theory (11-XX)
11 Quantum theory (81-XX)
9 Calculus of variations and optimal control; optimization (49-XX)
8 Systems theory; control (93-XX)
5 Manifolds and cell complexes (57-XX)
4 Order, lattices, ordered algebraic structures (06-XX)
4 Group theory and generalizations (20-XX)
3 Field theory and polynomials (12-XX)
3 Algebraic geometry (14-XX)
3 Functional analysis (46-XX)
2 General and overarching topics; collections (00-XX)
2 History and biography (01-XX)
2 Commutative algebra (13-XX)
2 Real functions (26-XX)
2 Dynamical systems and ergodic theory (37-XX)
2 General topology (54-XX)
1 General algebraic systems (08-XX)
1 Associative rings and algebras (16-XX)
1 Functions of a complex variable (30-XX)
1 Partial differential equations (35-XX)
1 Harmonic analysis on Euclidean spaces (42-XX)
1 Differential geometry (53-XX)
1 Global analysis, analysis on manifolds (58-XX)
1 Mechanics of particles and systems (70-XX)

Citations by Year

Wikidata Timeline

The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.