Edit Profile (opens in new tab) Vazirani, Vijay V. Compute Distance To: Compute Author ID: vazirani.vijay-v Published as: Vazirani, Vijay V.; Vazirani, Vijay; Vazirani, V. V. more...less External Links: MGP · Wikidata · GND · IdRef Documents Indexed: 128 Publications since 1982, including 2 Books 2 Contributions as Editor Co-Authors: 84 Co-Authors with 104 Joint Publications 2,580 Co-Co-Authors all top 5 Co-Authors 17 single-authored 13 Mehta, Ruta 10 Yannakakis, Mihalis 9 Garg, Jugal 9 Garg, Naveen Kumar 9 Vazirani, Umesh V. 7 Chakrabarty, Deeparnab 6 Devanur, Nikhil R. 6 Saran, Huzur 5 Mehta, Aranyak 4 Goel, Gagan 4 Khuller, Samir 4 Mai, Tung 4 Măndoiu, Ion I. 4 Saberi, Amin 4 Schulman, Leonard J. 4 Vigoda, Eric 4 Williamson, David P. 4 Yazdanbod, Sadra 3 Anari, Nima 3 Mitchell, Stephen G. 2 Arkin, Adam P. 2 Bezáková, Ivona 2 Bhatnagar, Nayantara 2 Goemans, Michel Xavier 2 Kapoor, Sanjiv 2 Karp, Richard Manning 2 Lawler, Eugene L. 2 Mahdian, Mohammad 2 Markakis, Evangelos 2 Mihail, Milena 2 Narayanan, H. 2 Panageas, Ioannis 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 Blum, Manuel 1 Daniely, Amit 1 Eppstein, David Arthur 1 Garg, Dinesh 1 Garg, Rahul 1 Gupta, Anupam 1 Hajiaghayi, Mohammad Taghi 1 Halperin, Eran 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 Rivest, Ronald Linn 1 Roughgarden, Tim 1 Santosh, Vempala S. 1 Shenker, Scott J. 1 Sinha, Saurabh 1 Stockmeyer, Larry J. 1 Talwar, Kunal 1 Tetali, Prasad 1 Thompson, Clark D. 1 Tong, Po 1 Tröbst, Thorben 1 Urner, Ruth 1 Venkatesan, Ramarathnam 1 Ye, Yinyu 1 Yuval, Gideon all top 5 Serials 11 SIAM Journal on Computing 9 Theoretical Computer Science 7 Journal of the ACM 5 Journal of Algorithms 5 SIAM Journal on Discrete Mathematics 4 Combinatorica 4 Algorithmica 3 IEEE Transactions on Information Theory 3 Information Processing Letters 3 Mathematics of Operations Research 2 Games and Economic Behavior 2 Mathematical Programming. Series A. Series B 2 Journal of Theoretical Biology 1 Discrete Applied Mathematics 1 Operations Research Letters 1 Information and Computation 1 Lecture Notes in Computer Science 1 Theory of Computing all top 5 Fields 84 Computer science (68-XX) 55 Operations research, mathematical programming (90-XX) 50 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 32 Combinatorics (05-XX) 8 Information and communication theory, circuits (94-XX) 4 Biology and other natural sciences (92-XX) 3 Numerical analysis (65-XX) 2 General and overarching topics; collections (00-XX) 2 Linear and multilinear algebra; matrix theory (15-XX) 2 Convex and discrete geometry (52-XX) 2 Probability theory and stochastic processes (60-XX) 2 Statistics (62-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 106 Publications have been cited 2,499 times in 2,045 Documents Cited by ▼ Year ▼ Approximation algorithms for metric facility location and \(k\)-median problems using the primal-dual schema and Lagrangian relaxation. Zbl 1138.90417Jain, Kamal; Vazirani, Vijay V. 359 2001 Algorithmic game theory. Foreword by Christos H. Papadimitriou. Zbl 1130.91005 214 2007 Random generation of combinatorial structures from a uniform distribution. Zbl 0597.68056Jerrum, Mark R.; Valiant, Leslie G.; Vazirani, Vijay V. 211 1986 Matching is as easy as matrix inversion. Zbl 0632.68041Mulmuley, Ketan; Vazirani, Umesh V.; Vazirani, Vijay V. 159 1987 NP is as easy as detecting unique solutions. Zbl 0621.68030Valiant, L. G.; Vazirani, V. V. 156 1986 Primal-dual approximation algorithms for integral flow and multicut in trees. Zbl 0873.68075Garg, N.; Vazirani, V. V.; Yannakakis, M. 113 1997 Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. Zbl 1325.90060Jain, Kamal; Mahdian, Mohammad; Markakis, Evangelos; Saberi, Amin; Vazirani, Vijay V. 106 2003 NP-completeness of some generalizations of the maximum matching problem. Zbl 0493.68039Stockmeyer, Larry J.; Vazirani, Vijay V. 85 1982 AdWords and generalized online matching. Zbl 1312.68239Mehta, Aranyak; Saberi, Amin; Vazirani, Umesh V.; Vazirani, Vijay V. 75 2007 Approximation algorithms. Zbl 1005.68002Vazirani, Vijay V. 75 1999 Approximate max-flow min-(multi)cut theorems and their applications. Zbl 0844.68061Garg, Naveen; Vazirani, Vijay V.; Yannakakis, Mihalis 71 1996 Multiway cuts in node weighted graphs. Zbl 1068.68178Garg, Naveen; Vazirani, Vijay V.; Yannakakis, Mihalis 62 2004 Applications of approximation algorithms to cooperative games. Zbl 1323.68570Jain, Kamal; Vazirani, Vijay 46 2001 Finding \(k\) cuts within twice the optimal. Zbl 0828.68082Saran, Huzur; Vazirani, Vijay V. 44 1995 Market equilibrium via a primal-dual algorithm for a convex program. Zbl 1325.91024Devanur, Nikhil R.; Papadimitriou, Christos H.; Saberi, Amin; Vazirani, Vijay V. 38 2008 Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs. Zbl 0696.68076Vazirani, Vijay V.; Yannakakis, Milhalis 33 1989 A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm. Zbl 0806.05058Vazirani, Vijay V. 31 1994 On-line algorithms for weighted bipartite matching and stable marriages. Zbl 0938.68934Khuller, Samir; Mitchell, Stephen G.; Vazirani, Vijay V. 30 1994 Primal-dual RNC approximation algorithms for set cover and covering integer programs. Zbl 0914.68096Rajagopalan, Sridhar; Vazirani, Vijay V. 29 1998 Approximate MAX-flow MIN-(multi)cut theorems and their applications. Zbl 1310.05198Garg, Naveen; Vazirani, Vijay V.; Yannakakis, Mihalis 25 1993 A primal-dual approximation algorithm for generalized Steiner network problems. Zbl 0838.90133Williamson, David P.; Goemans, Michel X.; Mihail, Milena; Vazirani, Vijay V. 24 1995 NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems. Zbl 0673.05075Vazirani, Vijay V. 22 1989 Global wire routing in two-dimensional arrays. Zbl 0634.94024Karp, R. M.; Leighton, F. T.; Rivest, R. L.; Thompson, C. D.; Vazirani, U. V.; Vazirani, V. V. 20 1987 Maximum matchings in general graphs through randomization. Zbl 0689.68092Rabin, Michael O.; Vazirani, Vijay V. 19 1989 Accelerating simulated annealing for the permanent and combinatorial counting problems. Zbl 1225.68270Bezáková, Ivona; Štefankovič, Daniel; Vazirani, Vijay V.; Vigoda, Eric 17 2008 NC algorithms for comparability graphs, interval graphs, and testing for unique perfect matching. Zbl 0598.68050Kozen, Dexter; Vazirani, Umesh V.; Vazirani, Vijay V. 16 1985 On the bidirected cut relaxation for the metric Steiner tree problem (extended abstract). Zbl 0938.68072Rajagopalan, Sridhar; Vazirani, Vijay V. 16 1999 Market equilibrium under separable, piecewise-linear, concave utilities. Zbl 1327.91042Vazirani, Vijay V.; Yannakakis, Mihalis 15 2011 Multiway cuts in directed and node weighted graphs (extended abstract). Zbl 1418.68168Garg, Naveen; Vazirani, Vijay V.; Yannakakis, Mihalis 14 1994 Market equilibria for homothetic, quasi-concave utilities and economies of scale in production. Zbl 1297.91107Jain, Kamal; Vazirani, Vijay V.; Ye, Yinyu 13 2005 Eisenberg-Gale markets: algorithms and structural properties. Zbl 1232.91452Jam, Kamal; Vazirani, Vijay V. 13 2007 Solving the weighted parity problem for gammoids by reduction to graphic matching. Zbl 0566.05017Tong, Po; Lawler, E. L.; Vazirani, V. V. 12 1984 An approximation algorithm for the fault tolerant metric facility location problem. Zbl 1138.90416Jain, Kamal; Vazirani, Vijay V. 12 2004 Nash social welfare for indivisible items under separable, piecewise-linear concave utilities. Zbl 1403.91204Anari, Nima; Mai, Tung; Oveis Gharan, Shayan; Vazirani, Vijay V. 12 2018 An efficient algorithm for constructing minimal trellises for codes over finite abelian groups. Zbl 0874.94038Vazirani, Vijay V.; Saran, Huzur; Rajan, B. Sundar 12 1996 Eisenberg-Gale markets: algorithms and game-theoretic properties. Zbl 1201.91110Jain, Kamal; Vazirani, Vijay V. 12 2010 Spending constraint utilities with applications to the Adwords market. Zbl 1216.91011Vazirani, Vijay V. 11 2010 ETR-completeness for decision versions of multi-player (symmetric) Nash equilibria. Zbl 1441.68072Garg, Jugal; Mehta, Ruta; Vazirani, Vijay V.; Yazdanbod, Sadra 11 2015 Improved bounds for the max-flow min-multicut ratio for planar and \(K_{r,r}\)-free graphs. Zbl 0803.90056Tardos, Éva; Vazirani, Vijay V. 10 1993 A stochastic process on the hypercube with applications to peer-to-peer networks. Zbl 1192.68018Adler, Micah; Halperin, Eran; Karp, Richard M.; Vazirani, Vijay V. 10 2003 Scheduling open shops with parallel machines. Zbl 0489.90053Lawler, E. L.; Luby, M. G.; Vazirani, V. V. 10 1982 Allocation of divisible goods under lexicographic preferences. Zbl 1369.91109Schulman, Leonard J.; Vazirani, Vijay V. 9 2015 A primal-dual approximation algorithm for generalized Steiner network problems. Zbl 1310.90116Williamson, David P.; Goemans, Michel X.; Mihail, Milena; Vazirani, Vijay V. 9 1993 Combinatorial algorithms for market equilibria. Zbl 1151.91616Vazirani, Vijay V. 9 2007 Representing and enumerating edge connectivity cuts in \(\mathcal {RNC}\). Zbl 0765.68041Naor, Dalit; Vazirani, Vijay V. 8 1991 A greedy facility location algorithm analyzed using dual fitting. Zbl 0998.68701Mahdian, Mohammad; Markakis, Evangelos; Saberi, Amin; Vazirani, Vijay 8 2001 Minimum multicolored subgraph problem in multiplex PCR primer set selection and population haplotyping. Zbl 1155.92338Hajiaghayi, M. T.; Jain, K.; Lau, L. C.; Măndoiu, I. I.; Russell, A.; Vazirani, V. V. 8 2006 The notion of a rational convex program, and an algorithm for the Arrow-Debreu Nash bargaining game. Zbl 1281.91095Vazirani, Vijay V. 8 2012 Planar graph coloring is not self-reducible, assuming P\(\neq NP\). Zbl 0729.05019Khuller, Samir; Vazirani, Vijay V. 7 1991 Randomized parallel algorithms for matroid union and intersection, with applications to arborescences and edge-disjoint spanning trees. Zbl 0796.05021Narayanan, H.; Saran, Huzur; Vazirani, Vijay V. 7 1994 Efficient and secure pseudo-random number generation. Zbl 0579.65005Vazirani, Umesh V.; Vazirani, Vijay V. 7 1985 A natural encoding scheme proved probabilistic polynomial complete. Zbl 0525.68025Vazirani, Umesh V.; Vazirani, Vijay V. 7 1983 Processor efficient parallel algorithms for the two disjoint paths problem and for finding a Kuratowski homeomorph. Zbl 0761.68074Khuller, Samir; Mitchell, Stephen G.; Vazirani, Vijay V. 6 1992 A complementary pivot algorithm for market equilibrium under separable, piecewise-linear concave utilities. Zbl 1410.91325Garg, Jugal; Mehta, Ruta; Sohoni, Milind; Vazirani, Vijay V. 6 2015 Planar graph perfect matching is in NC. Zbl 1491.68131Anari, Nima; Vazirani, Vijay V. 5 2020 An auction-based market equilibrium algorithm for the separable gross substitutability case. Zbl 1105.91303Garg, Rahul; Kapoor, Sanjiv; Vazirani, Vijay 5 2004 2-player Nash and nonsymmetric bargaining games: algorithms and structural properties. Zbl 1310.91008Vazirani, Vijay V. 5 2010 Equitable cost allocations via primal-dual-type algorithms. Zbl 1192.90107Jain, Kamal; Vazirani, Vijay V. 5 2002 Finding separator cuts in planar graphs within twice the optimal. Zbl 0943.68077Garg, Naveen; Saran, Huzur; Vazirani, Vijay V. 5 1999 A graph theoretic approach to software watermarking. Zbl 1008.68663Venkatesan, Ramarathnam; Vazirani, Vijay; Sinha, Saurabh 5 2001 An improved approximation scheme for computing Arrow-Debreu prices for the linear case. Zbl 1205.91109Devanur, Nikhil R.; Vazirani, Vijay V. 5 2003 The two-processor scheduling problem is in random NC. Zbl 0692.68043Vazirani, Umesh V.; Vazirani, Vijay V. 5 1989 On-line algorithms for weighted bipartite matching and stable marriages. Zbl 0768.68154Khuller, Samir; Mitchell, Stephen G.; Vazirani, Vijay V. 4 1991 An approximation algorithm for the fault tolerant metric facility location problem. Zbl 0976.90056Jain, Kamal; Vazirani, Vijay V. 4 2000 Accelerating simulated annealing for the permanent and combinatorial counting problems. Zbl 1192.90160Bezáková, Ivona; Štefankovič, Daniel; Vazirani, Vijay V.; Vigoda, Eric 4 2006 A primal-dual schema based approximation algorithm for the element connectivity problem. Zbl 0934.68110Jain, Kamal; Măndoiu, Ion; Vazirani, Vijay V.; Williamson, David P. 4 1999 Rational convex programs and efficient algorithms for 2-player Nash and nonsymmetric bargaining games. Zbl 1258.68189Vazirani, Vijay V. 4 2012 Recent results on approximating the Steiner tree problem and its generalizations. Zbl 0953.68120Vazirani, Vijay V. 4 2000 Efficient sequential and parallel algorithms for maximal bipartite sets. Zbl 0764.68130Pearson, David; Vazirani, Vijay V. 3 1993 Learning economic parameters from revealed preferences. Zbl 1406.91095Balcan, Maria-Florina; Daniely, Amit; Mehta, Ruta; Urner, Ruth; Vazirani, Vijay V. 3 2014 A complementary pivot algorithm for markets under separable, piecewise-linear concave utilities. Zbl 1286.90091Garg, Jugal; Mehta, Ruta; Sohoni, Milind; Vazirani, Vijay V. 3 2012 Pfaffian orientations, 0/1 permanents, and even cycles in directed graphs. Zbl 0648.68060Vazirani, Vijay V.; Yannakakis, Mihalis 3 1988 NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems. Zbl 0651.68086Vazirani, Vijay V. 3 1988 Rationality and strongly polynomial solvability of Eisenberg-Gale markets with two agents. Zbl 1229.91125Chakrabarty, Deeparnab; Devanur, Nikhil R.; Vazirani, Vijay V. 3 2010 New geometry-inspired relaxations and algorithms for the metric Steiner tree problem. Zbl 1143.90376Chakrabarty, Deeparnab; Devanur, Nikhil R.; Vazirani, Vijay V. 3 2008 Nash bargaining via flexible budget markets. (Abstract). Zbl 1143.91326Vazirani, Vijay V. 3 2008 Settling the complexity of Leontief and PLC exchange markets under exact and approximate equilibria. Zbl 1371.91126Garg, Jugal; Mehta, Ruta; Vazirani, Vijay V.; Yazdanbod, Sadra 3 2017 Settling some open problems on 2-player symmetric Nash equilibria. Zbl 1358.91004Mehta, Ruta; Vazirani, Vijay V.; Yazdanbod, Sadra 3 2015 Solvency games. Zbl 1248.91021Berger, Noam; Kapur, Nevin; Schulman, Leonard J.; Vazirani, Vijay V. 3 2008 Diversity in times of adversity: probabilistic strategies in microbial survival games. Zbl 1445.92306Wolf, Denise M.; Vazirani, Vijay V.; Arkin, Adam P. 3 2005 Primal-dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover. Zbl 1418.68244Garg, Naveen; Vazirani, Vijay V.; Yannakakis, Mihalis 2 1993 A primal-dual algorithm for computing Fisher equilibrium in the absence of gross substitutability property. Zbl 1294.91062Garg, Dinesh; Jain, Kamal; Talwar, Kunal; Vazirani, Vijay V. 2 2007 On the capacity of multiple unicast sessions in undirected graphs. Zbl 1315.94118Jain, Kamal; Vazirani, Vijay V.; Yuval, Gideon 2 2006 Primal-dual schema based approximation algorithms. Zbl 1054.68170Vazirani, Vijay V. 2 2002 Mutation, sexual reproduction and survival in dynamic environments. Zbl 1402.92318Mehta, Ruta; Panageas, Ioannis; Piliouras, Georgios; Tetali, Prasad; Vazirani, Vijay V. 2 2017 A polyhedron with all \(s-t\) cuts as vertices, and adjacency of cuts. Zbl 0845.90047Garg, Naveen; Vazirani, Vijay V. 2 1995 A primal-dual schema based approximation algorithm for the element connectivity problem. Zbl 1122.90351Jain, Kamal; Măndoiu, Ion; Vazirani, Vijay V.; Williamson, David P. 2 2002 Dichotomies in equilibrium computation, and complementary pivot algorithms for a new class of non-separable utility functions. Zbl 1315.91040Garg, Jugal; Mehta, Ruta; Vazirani, Vijay V. 2 2014 New geometry-inspired relaxations and algorithms for the metric Steiner tree problem. Zbl 1231.90364Chakrabarty, Deeparnab; Devanur, Nikhil R.; Vazirani, Vijay V. 2 2011 A perfect price discrimination market model with production, and a rational convex program for it. Zbl 1238.91095Goel, Gagan; Vazirani, Vijay V. 2 2011 The general graph matching game: approximate core. Zbl 1485.91014Vazirani, Vijay V. 2 2022 Substitution with satiation: a new class of utility functions and a complementary pivot algorithm. Zbl 1443.91154Garg, Jugal; Mehta, Ruta; Vazirani, Vijay V. 1 2018 On computability of equilibria in markets with production. Zbl 1425.91273Garg, Jugal; Vazirani, Vijay V. 1 2014 A computationally motivated definition of parametric estimation and its applications to the Gaussian distribution. Zbl 1095.68033Schulman, Leonard J.; Vazirani, Vijay V. 1 2005 Randomized parallel algorithms for matroid union and intersection, with applications to arboresences and edge-disjoint spanning trees. Zbl 0815.05021Narayanan, H.; Saran, Huzur; Vazirani, Vijay V. 1 1992 An auction-based market equilibrium algorithm for a production model. Zbl 1121.91039Kapoor, Sanjiv; Mehta, Aranyak; Vazirani, Vijay 1 2007 Dichotomies in equilibrium computation and membership of PLC markets in FIXP. Zbl 1415.91191Garg, Jugal; Mehta, Ruta; Vazirani, Vijay V. 1 2016 Random bichromatic matchings. Zbl 1147.05054Bhatnagar, Nayantara; Randall, Dana; Vazirani, Vijay V.; Vigoda, Eric 1 2008 A perfect price discrimination market model with production, and a (rational) convex program for it. Zbl 1310.91072Goel, Gagan; Vazirani, Vijay 1 2010 The “Art of trellis decoding” is computationally hard – for large fields. Zbl 0906.94024Jain, Kamal; Măndoiu, Ion; Vazirani, Vijay V. 1 1998 The general graph matching game: approximate core. Zbl 1485.91014Vazirani, Vijay V. 2 2022 Planar graph perfect matching is in NC. Zbl 1491.68131Anari, Nima; Vazirani, Vijay V. 5 2020 Nash social welfare for indivisible items under separable, piecewise-linear concave utilities. Zbl 1403.91204Anari, Nima; Mai, Tung; Oveis Gharan, Shayan; Vazirani, Vijay V. 12 2018 Substitution with satiation: a new class of utility functions and a complementary pivot algorithm. Zbl 1443.91154Garg, Jugal; Mehta, Ruta; Vazirani, Vijay V. 1 2018 Finding stable matchings that are robust to errors in the input. Zbl 07378730Mai, Tung; Vazirani, Vijay V. 1 2018 Settling the complexity of Leontief and PLC exchange markets under exact and approximate equilibria. Zbl 1371.91126Garg, Jugal; Mehta, Ruta; Vazirani, Vijay V.; Yazdanbod, Sadra 3 2017 Mutation, sexual reproduction and survival in dynamic environments. Zbl 1402.92318Mehta, Ruta; Panageas, Ioannis; Piliouras, Georgios; Tetali, Prasad; Vazirani, Vijay V. 2 2017 Dichotomies in equilibrium computation and membership of PLC markets in FIXP. Zbl 1415.91191Garg, Jugal; Mehta, Ruta; Vazirani, Vijay V. 1 2016 ETR-completeness for decision versions of multi-player (symmetric) Nash equilibria. Zbl 1441.68072Garg, Jugal; Mehta, Ruta; Vazirani, Vijay V.; Yazdanbod, Sadra 11 2015 Allocation of divisible goods under lexicographic preferences. Zbl 1369.91109Schulman, Leonard J.; Vazirani, Vijay V. 9 2015 A complementary pivot algorithm for market equilibrium under separable, piecewise-linear concave utilities. Zbl 1410.91325Garg, Jugal; Mehta, Ruta; Sohoni, Milind; Vazirani, Vijay V. 6 2015 Settling some open problems on 2-player symmetric Nash equilibria. Zbl 1358.91004Mehta, Ruta; Vazirani, Vijay V.; Yazdanbod, Sadra 3 2015 Learning economic parameters from revealed preferences. Zbl 1406.91095Balcan, Maria-Florina; Daniely, Amit; Mehta, Ruta; Urner, Ruth; Vazirani, Vijay V. 3 2014 Dichotomies in equilibrium computation, and complementary pivot algorithms for a new class of non-separable utility functions. Zbl 1315.91040Garg, Jugal; Mehta, Ruta; Vazirani, Vijay V. 2 2014 On computability of equilibria in markets with production. Zbl 1425.91273Garg, Jugal; Vazirani, Vijay V. 1 2014 Thrifty algorithms for multistage robust optimization. Zbl 1372.90092Gupta, Anupam; Nagarajan, Viswanath; Vazirani, Vijay V. 1 2013 Nonseparable, concave utilities are easy – in a perfect price discrimination market model. Zbl 1274.91239Vazirani, Vijay V. 1 2013 The notion of a rational convex program, and an algorithm for the Arrow-Debreu Nash bargaining game. Zbl 1281.91095Vazirani, Vijay V. 8 2012 Rational convex programs and efficient algorithms for 2-player Nash and nonsymmetric bargaining games. Zbl 1258.68189Vazirani, Vijay V. 4 2012 A complementary pivot algorithm for markets under separable, piecewise-linear concave utilities. Zbl 1286.90091Garg, Jugal; Mehta, Ruta; Sohoni, Milind; Vazirani, Vijay V. 3 2012 Market equilibrium under separable, piecewise-linear, concave utilities. Zbl 1327.91042Vazirani, Vijay V.; Yannakakis, Mihalis 15 2011 New geometry-inspired relaxations and algorithms for the metric Steiner tree problem. Zbl 1231.90364Chakrabarty, Deeparnab; Devanur, Nikhil R.; Vazirani, Vijay V. 2 2011 A perfect price discrimination market model with production, and a rational convex program for it. Zbl 1238.91095Goel, Gagan; Vazirani, Vijay V. 2 2011 Eisenberg-Gale markets: algorithms and game-theoretic properties. Zbl 1201.91110Jain, Kamal; Vazirani, Vijay V. 12 2010 Spending constraint utilities with applications to the Adwords market. Zbl 1216.91011Vazirani, Vijay V. 11 2010 2-player Nash and nonsymmetric bargaining games: algorithms and structural properties. Zbl 1310.91008Vazirani, Vijay V. 5 2010 Rationality and strongly polynomial solvability of Eisenberg-Gale markets with two agents. Zbl 1229.91125Chakrabarty, Deeparnab; Devanur, Nikhil R.; Vazirani, Vijay V. 3 2010 A perfect price discrimination market model with production, and a (rational) convex program for it. Zbl 1310.91072Goel, Gagan; Vazirani, Vijay 1 2010 Market equilibrium via a primal-dual algorithm for a convex program. Zbl 1325.91024Devanur, Nikhil R.; Papadimitriou, Christos H.; Saberi, Amin; Vazirani, Vijay V. 38 2008 Accelerating simulated annealing for the permanent and combinatorial counting problems. Zbl 1225.68270Bezáková, Ivona; Štefankovič, Daniel; Vazirani, Vijay V.; Vigoda, Eric 17 2008 New geometry-inspired relaxations and algorithms for the metric Steiner tree problem. Zbl 1143.90376Chakrabarty, Deeparnab; Devanur, Nikhil R.; Vazirani, Vijay V. 3 2008 Nash bargaining via flexible budget markets. (Abstract). Zbl 1143.91326Vazirani, Vijay V. 3 2008 Solvency games. Zbl 1248.91021Berger, Noam; Kapur, Nevin; Schulman, Leonard J.; Vazirani, Vijay V. 3 2008 Random bichromatic matchings. Zbl 1147.05054Bhatnagar, Nayantara; Randall, Dana; Vazirani, Vijay V.; Vigoda, Eric 1 2008 Equitable cost allocations via primal-dual-type algorithms. Zbl 1165.91014Jain, Kamal; Vazirani, Vijay V. 1 2008 Algorithmic game theory. Foreword by Christos H. Papadimitriou. Zbl 1130.91005 214 2007 AdWords and generalized online matching. Zbl 1312.68239Mehta, Aranyak; Saberi, Amin; Vazirani, Umesh V.; Vazirani, Vijay V. 75 2007 Eisenberg-Gale markets: algorithms and structural properties. Zbl 1232.91452Jam, Kamal; Vazirani, Vijay V. 13 2007 Combinatorial algorithms for market equilibria. Zbl 1151.91616Vazirani, Vijay V. 9 2007 A primal-dual algorithm for computing Fisher equilibrium in the absence of gross substitutability property. Zbl 1294.91062Garg, Dinesh; Jain, Kamal; Talwar, Kunal; Vazirani, Vijay V. 2 2007 An auction-based market equilibrium algorithm for a production model. Zbl 1121.91039Kapoor, Sanjiv; Mehta, Aranyak; Vazirani, Vijay 1 2007 Minimum multicolored subgraph problem in multiplex PCR primer set selection and population haplotyping. Zbl 1155.92338Hajiaghayi, M. T.; Jain, K.; Lau, L. C.; Măndoiu, I. I.; Russell, A.; Vazirani, V. V. 8 2006 Accelerating simulated annealing for the permanent and combinatorial counting problems. Zbl 1192.90160Bezáková, Ivona; Štefankovič, Daniel; Vazirani, Vijay V.; Vigoda, Eric 4 2006 On the capacity of multiple unicast sessions in undirected graphs. Zbl 1315.94118Jain, Kamal; Vazirani, Vijay V.; Yuval, Gideon 2 2006 Market equilibria for homothetic, quasi-concave utilities and economies of scale in production. Zbl 1297.91107Jain, Kamal; Vazirani, Vijay V.; Ye, Yinyu 13 2005 Diversity in times of adversity: probabilistic strategies in microbial survival games. Zbl 1445.92306Wolf, Denise M.; Vazirani, Vijay V.; Arkin, Adam P. 3 2005 A computationally motivated definition of parametric estimation and its applications to the Gaussian distribution. Zbl 1095.68033Schulman, Leonard J.; Vazirani, Vijay V. 1 2005 Multiway cuts in node weighted graphs. Zbl 1068.68178Garg, Naveen; Vazirani, Vijay V.; Yannakakis, Mihalis 62 2004 An approximation algorithm for the fault tolerant metric facility location problem. Zbl 1138.90416Jain, Kamal; Vazirani, Vijay V. 12 2004 An auction-based market equilibrium algorithm for the separable gross substitutability case. Zbl 1105.91303Garg, Rahul; Kapoor, Sanjiv; Vazirani, Vijay 5 2004 Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. Zbl 1325.90060Jain, Kamal; Mahdian, Mohammad; Markakis, Evangelos; Saberi, Amin; Vazirani, Vijay V. 106 2003 A stochastic process on the hypercube with applications to peer-to-peer networks. Zbl 1192.68018Adler, 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.91109Devanur, Nikhil R.; Vazirani, Vijay V. 5 2003 Equitable cost allocations via primal-dual-type algorithms. Zbl 1192.90107Jain, Kamal; Vazirani, Vijay V. 5 2002 Primal-dual schema based approximation algorithms. Zbl 1054.68170Vazirani, Vijay V. 2 2002 A primal-dual schema based approximation algorithm for the element connectivity problem. Zbl 1122.90351Jain, Kamal; Măndoiu, Ion; Vazirani, Vijay V.; Williamson, David P. 2 2002 Approximation algorithms for metric facility location and \(k\)-median problems using the primal-dual schema and Lagrangian relaxation. Zbl 1138.90417Jain, Kamal; Vazirani, Vijay V. 359 2001 Applications of approximation algorithms to cooperative games. Zbl 1323.68570Jain, Kamal; Vazirani, Vijay 46 2001 A greedy facility location algorithm analyzed using dual fitting. Zbl 0998.68701Mahdian, Mohammad; Markakis, Evangelos; Saberi, Amin; Vazirani, Vijay 8 2001 A graph theoretic approach to software watermarking. Zbl 1008.68663Venkatesan, Ramarathnam; Vazirani, Vijay; Sinha, Saurabh 5 2001 An approximation algorithm for the fault tolerant metric facility location problem. Zbl 0976.90056Jain, Kamal; Vazirani, Vijay V. 4 2000 Recent results on approximating the Steiner tree problem and its generalizations. Zbl 0953.68120Vazirani, Vijay V. 4 2000 Approximation algorithms. Zbl 1005.68002Vazirani, Vijay V. 75 1999 On the bidirected cut relaxation for the metric Steiner tree problem (extended abstract). Zbl 0938.68072Rajagopalan, Sridhar; Vazirani, Vijay V. 16 1999 Finding separator cuts in planar graphs within twice the optimal. Zbl 0943.68077Garg, Naveen; Saran, Huzur; Vazirani, Vijay V. 5 1999 A primal-dual schema based approximation algorithm for the element connectivity problem. Zbl 0934.68110Jain, 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.68096Rajagopalan, Sridhar; Vazirani, Vijay V. 29 1998 The “Art of trellis decoding” is computationally hard – for large fields. Zbl 0906.94024Jain, Kamal; Măndoiu, Ion; Vazirani, Vijay V. 1 1998 Primal-dual approximation algorithms for integral flow and multicut in trees. Zbl 0873.68075Garg, N.; Vazirani, V. V.; Yannakakis, M. 113 1997 Approximate max-flow min-(multi)cut theorems and their applications. Zbl 0844.68061Garg, Naveen; Vazirani, Vijay V.; Yannakakis, Mihalis 71 1996 An efficient algorithm for constructing minimal trellises for codes over finite abelian groups. Zbl 0874.94038Vazirani, Vijay V.; Saran, Huzur; Rajan, B. Sundar 12 1996 Finding \(k\) cuts within twice the optimal. Zbl 0828.68082Saran, Huzur; Vazirani, Vijay V. 44 1995 A primal-dual approximation algorithm for generalized Steiner network problems. Zbl 0838.90133Williamson, David P.; Goemans, Michel X.; Mihail, Milena; Vazirani, Vijay V. 24 1995 A polyhedron with all \(s-t\) cuts as vertices, and adjacency of cuts. Zbl 0845.90047Garg, 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.05058Vazirani, Vijay V. 31 1994 On-line algorithms for weighted bipartite matching and stable marriages. Zbl 0938.68934Khuller, Samir; Mitchell, Stephen G.; Vazirani, Vijay V. 30 1994 Multiway cuts in directed and node weighted graphs (extended abstract). Zbl 1418.68168Garg, Naveen; Vazirani, Vijay V.; Yannakakis, Mihalis 14 1994 Randomized parallel algorithms for matroid union and intersection, with applications to arborescences and edge-disjoint spanning trees. Zbl 0796.05021Narayanan, H.; Saran, Huzur; Vazirani, Vijay V. 7 1994 Approximate MAX-flow MIN-(multi)cut theorems and their applications. Zbl 1310.05198Garg, Naveen; Vazirani, Vijay V.; Yannakakis, Mihalis 25 1993 Improved bounds for the max-flow min-multicut ratio for planar and \(K_{r,r}\)-free graphs. Zbl 0803.90056Tardos, Éva; Vazirani, Vijay V. 10 1993 A primal-dual approximation algorithm for generalized Steiner network problems. Zbl 1310.90116Williamson, David P.; Goemans, Michel X.; Mihail, Milena; Vazirani, Vijay V. 9 1993 Efficient sequential and parallel algorithms for maximal bipartite sets. Zbl 0764.68130Pearson, 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.68244Garg, Naveen; Vazirani, Vijay V.; Yannakakis, Mihalis 2 1993 A polyhedron with all \(s-t\) cuts as vertices, and adjacency of cuts. Zbl 0923.90059Garg, Naveen; Vazirani, Vijay V. 1 1993 Processor efficient parallel algorithms for the two disjoint paths problem and for finding a Kuratowski homeomorph. Zbl 0761.68074Khuller, Samir; Mitchell, Stephen G.; Vazirani, Vijay V. 6 1992 Randomized parallel algorithms for matroid union and intersection, with applications to arboresences and edge-disjoint spanning trees. Zbl 0815.05021Narayanan, H.; Saran, Huzur; Vazirani, Vijay V. 1 1992 Suboptimal cuts: their enumeration, weight and number (extended abstract). Zbl 1427.68254Vazirani, Vijay V.; Yannakakis, Mihalis 1 1992 Representing and enumerating edge connectivity cuts in \(\mathcal {RNC}\). Zbl 0765.68041Naor, Dalit; Vazirani, Vijay V. 8 1991 Planar graph coloring is not self-reducible, assuming P\(\neq NP\). Zbl 0729.05019Khuller, Samir; Vazirani, Vijay V. 7 1991 On-line algorithms for weighted bipartite matching and stable marriages. Zbl 0768.68154Khuller, Samir; Mitchell, Stephen G.; Vazirani, Vijay V. 4 1991 Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs. Zbl 0696.68076Vazirani, Vijay V.; Yannakakis, Milhalis 33 1989 NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems. Zbl 0673.05075Vazirani, Vijay V. 22 1989 Maximum matchings in general graphs through randomization. Zbl 0689.68092Rabin, Michael O.; Vazirani, Vijay V. 19 1989 The two-processor scheduling problem is in random NC. Zbl 0692.68043Vazirani, Umesh V.; Vazirani, Vijay V. 5 1989 Pfaffian orientations, 0/1 permanents, and even cycles in directed graphs. Zbl 0648.68060Vazirani, Vijay V.; Yannakakis, Mihalis 3 1988 NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems. Zbl 0651.68086Vazirani, Vijay V. 3 1988 Matching is as easy as matrix inversion. Zbl 0632.68041Mulmuley, Ketan; Vazirani, Umesh V.; Vazirani, Vijay V. 159 1987 Global wire routing in two-dimensional arrays. Zbl 0634.94024Karp, R. M.; Leighton, F. T.; Rivest, R. L.; Thompson, C. D.; Vazirani, U. V.; Vazirani, V. V. 20 1987 Random generation of combinatorial structures from a uniform distribution. Zbl 0597.68056Jerrum, Mark R.; Valiant, Leslie G.; Vazirani, Vijay V. 211 1986 NP is as easy as detecting unique solutions. Zbl 0621.68030Valiant, L. G.; Vazirani, V. V. 156 1986 ...and 6 more Documents all cited Publications top 5 cited Publications all top 5 Cited by 3,224 Authors 53 Xu, Dachuan 26 Du, Donglei 26 Vazirani, Vijay V. 26 Wu, Chenchen 17 Goldberg, Leslie Ann 17 Jerrum, Mark R. 17 Zhang, Peng 15 Zhang, Dongmei 13 Bentz, Cédric 12 Niedermeier, Rolf 12 Rautenbach, Dieter 11 Segev, Danny 11 Williamson, David P. 10 Buchbinder, Niv 10 Caragiannis, Ioannis 10 Chekuri, Chandra S. 10 Garg, Jugal 10 Guo, Jiong 10 Hoefer, Martin 10 Kratsch, Stefan 10 Mehlhorn, Kurt 10 Nagamochi, Hiroshi 10 Nagarajan, Viswanath 10 Paschos, Vangelis Th. 10 Pilipczuk, Marcin L. 10 Saurabh, Saket 10 Spirakis, Paul G. 10 Vigoda, Eric 9 Dyer, Martin E. 9 Elbassioni, Khaled M. 9 Garg, Naveen Kumar 9 Hajiaghayi, Mohammad Taghi 9 Köbler, Johannes 9 Mehta, Ruta 9 Mirrokni, Vahab S. 9 Ravi, Ramamoorthi 9 Wang, Yishui 9 Zhang, Zhao 8 Arvind, Vikraman 8 Galanis, Andreas 8 Gupta, Anupam 8 Könemann, Jochen 8 Manlove, David F. 8 Manthey, Bodo 8 Naor, Joseph Seffi 8 Parekh, Ojas D. 8 Pruhs, Kirk R. 8 Schafer, Guido 8 Wahlström, Magnus 8 Watanabe, Osamu 7 Bezáková, Ivona 7 Chrobak, Marek 7 Cygan, Marek 7 Datta, Samir 7 Flammini, Michele 7 Han, Lu 7 Hirai, Hiroshi 7 Huber, Mark L. 7 Kaklamanis, Christos 7 Karpinski, Marek 7 Kobayashi, Yusuke 7 Lecué, Guillaume 7 Levin, Asaf 7 Rothe, Jörg-Matthias 7 Tardos, Éva 7 Torán, Jacobo 7 Xu, Chao 7 Yannakakis, Mihalis 7 Ye, Yinyu 6 Bansal, Nikhil 6 Bilò, Vittorio 6 Chandrasekaran, Karthekeyan 6 Costa, Marie-Christine 6 Deng, Xiao-Tie 6 Fotakis, Dimitris A. 6 Fukunaga, Takuro 6 Guruswami, Venkatesan 6 Gurvich, Vladimir A. 6 Hochbaum, Dorit S. 6 Karp, Richard Manning 6 Kortsarz, Guy 6 Lampis, Michael 6 Li, Min 6 Lingas, Andrzej 6 Maffioli, Francesco 6 Marx, Dániel 6 Mestre, Julián 6 Moscardelli, Luca 6 Papadimitriou, Christos Harilaos 6 Randall, Dana J. 6 Sinclair, Alistair 6 Štefankovič, Daniel 6 Stein, Clifford 6 Swamy, Chaitanya 6 Thierauf, Thomas 6 Vardi, Moshe Ya’akov 6 Wang, Jianxin 6 Xu, Jinhui 5 Barman, Siddharth 5 Boros, Endre ...and 3,124 more Authors all top 5 Cited in 237 Serials 222 Theoretical Computer Science 130 Algorithmica 107 Discrete Applied Mathematics 77 Information Processing Letters 72 Journal of Computer and System Sciences 59 Mathematical Programming. Series A. Series B 50 SIAM Journal on Computing 46 Journal of Combinatorial Optimization 45 Operations Research Letters 44 Theory of Computing Systems 43 European Journal of Operational Research 38 Information and Computation 27 Computers & Operations Research 26 Operations Research 26 Discrete Optimization 24 Computational Complexity 23 Discrete Mathematics 23 Combinatorica 23 Journal of Discrete Algorithms 22 Games and Economic Behavior 21 SIAM Journal on Discrete Mathematics 18 Random Structures & Algorithms 17 Artificial Intelligence 14 Mathematics of Operations Research 12 INFORMS Journal on Computing 12 Optimization Letters 11 Networks 10 Information Sciences 10 Journal of Combinatorial Theory. Series B 10 International Journal of Foundations of Computer Science 10 Journal of Global Optimization 9 Annals of Operations Research 9 Computer Science Review 8 Combinatorics, Probability and Computing 8 Journal of the Operations Research Society of China 7 Linear Algebra and its Applications 7 Journal of Scheduling 6 The Annals of Statistics 6 Journal of Economic Theory 6 Acta Mathematicae Applicatae Sinica. English Series 6 Probability Theory and Related Fields 6 RAIRO. Operations Research 6 Discrete Mathematics, Algorithms and Applications 5 Journal of Statistical Physics 5 Physica A 5 Applied Mathematics and Computation 5 Mathematical Systems Theory 5 Advances in Applied Mathematics 5 Discrete & Computational Geometry 5 Computational Geometry 5 Designs, Codes and Cryptography 5 International Journal of Computer Mathematics 5 Distributed Computing 5 Constraints 5 CEJOR. Central European Journal of Operations Research 4 Automatica 4 Journal of Complexity 4 Journal of Parallel and Distributed Computing 4 International Journal of Computational Geometry & Applications 4 SIAM Journal on Optimization 4 Computational Optimization and Applications 4 Journal of Mathematical Sciences (New York) 4 The Journal of Artificial Intelligence Research (JAIR) 4 Trudy Instituta Matematiki 4 Foundations of Computational Mathematics 4 4OR 4 Journal of Industrial and Management Optimization 4 Electronic Journal of Statistics 4 ACM Transactions on Computation Theory 3 Computing 3 Journal of Mathematical Economics 3 European Journal of Combinatorics 3 Mathematical Social Sciences 3 Social Choice and Welfare 3 Journal of Cryptology 3 Japan Journal of Industrial and Applied Mathematics 3 Journal of Computer and Systems Sciences International 3 Economic Theory 3 The Electronic Journal of Combinatorics 3 Annals of Mathematics and Artificial Intelligence 3 Bernoulli 3 Mathematical Problems in Engineering 3 Parallel Algorithms and Applications 3 RAIRO. Theoretical Informatics and Applications 3 International Game Theory Review 3 OR Spectrum 3 Mathematical Programming Computation 3 ACM Transactions on Algorithms 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 Computational and Applied Mathematics 2 Journal of Graph Theory 2 Journal of Statistical Planning and Inference 2 Optimization 2 Asia-Pacific Journal of Operational Research ...and 137 more Serials all top 5 Cited in 39 Fields 1,251 Computer science (68-XX) 756 Operations research, mathematical programming (90-XX) 613 Combinatorics (05-XX) 378 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 70 Numerical analysis (65-XX) 63 Probability theory and stochastic processes (60-XX) 62 Information and communication theory, circuits (94-XX) 56 Statistics (62-XX) 33 Statistical mechanics, structure of matter (82-XX) 31 Mathematical logic and foundations (03-XX) 28 Linear and multilinear algebra; matrix theory (15-XX) 26 Biology and other natural sciences (92-XX) 24 Convex and discrete geometry (52-XX) 15 Number theory (11-XX) 14 Quantum theory (81-XX) 11 Calculus of variations and optimal control; optimization (49-XX) 9 Systems theory; control (93-XX) 7 Manifolds and cell complexes (57-XX) 6 Group theory and generalizations (20-XX) 4 Order, lattices, ordered algebraic structures (06-XX) 4 Algebraic geometry (14-XX) 3 General and overarching topics; collections (00-XX) 3 Commutative algebra (13-XX) 3 Dynamical systems and ergodic theory (37-XX) 3 Functional analysis (46-XX) 2 History and biography (01-XX) 2 Field theory and polynomials (12-XX) 2 Real functions (26-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 Geometry (51-XX) 1 Differential geometry (53-XX) 1 Algebraic topology (55-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.