Vijay V. Vazirani
Affiliations: Unniversity of California, Irvine, CA, USA
 Georgia Institute of Technology, College of Computing, Atlanta, GA, USA
According to our database^{1},
Vijay V. Vazirani
authored at least 183 papers
between 1980 and 2023.
Collaborative distances:
Collaborative distances:
Awards
ACM Fellow
ACM Fellow 2005, "For contributions to optimization and approximation algorithms.".
Timeline
Legend:
Book In proceedings Article PhD thesis OtherLinks
Online presence:

on zbmath.org

on ics.uci.edu

on viaf.org

on id.loc.gov

on dnb.info

on isni.org

on dl.acm.org
On csauthors.net:
Bibliography
2023
Inf. Process. Lett., 2023
CoRR, 2023
2022
Games Econ. Behav., 2022
Cores of Games via Total Dual Integrality, with Applications to Perfect Graphs and Polymatroids.
CoRR, 2022
CoRR, 2022
Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science, 2022
NashBargainingBased Models for Matching Markets: OneSided and TwoSided; Fisher and ArrowDebreu.
Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022
Proceedings of the 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2022
A Structural and Algorithmic Study of Stable Matching Lattices of "Nearby" Instances, with Applications.
Proceedings of the 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2022
Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems, 2022
2021
NC Algorithms for Computing a Perfect Matching and a Maximum Flow in OneCrossingMinorFree Graphs.
SIAM J. Comput., 2021
CoRR, 2021
Combinatorial Algorithms for Matching Markets via Nash Bargaining: OneSided, TwoSided and NonBipartite.
CoRR, 2021
NashBargainingBased Models for Matching Markets, with Implementations and Experimental Results.
CoRR, 2021
Computational Complexity of the HyllandZeckhauser Scheme for OneSided Matching Markets.
Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021
2020
Theor. Comput. Sci., 2020
J. ACM, 2020
CoRR, 2020
CoRR, 2020
An ArrowDebreu Extension of the HyllandZeckhauser Scheme: Equilibrium Existence and Algorithms.
CoRR, 2020
Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020
Proceedings of the 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2020
2019
CoRR, 2019
StabilityPreserving, IncentiveCompatible, TimeEfficient Mechanisms for Increasing School Capacity.
CoRR, 2019
CoRR, 2019
NC Algorithms for Computing a Perfect Matching, the Number of Perfect Matchings, and a Maximum Flow in OneCrossingMinorFree Graphs.
Proceedings of the 31st ACM on Symposium on Parallelism in Algorithms and Architectures, 2019
2018
∃RCompleteness for Decision Versions of MultiPlayer (Symmetric) Nash Equilibria.
ACM Trans. Economics and Comput., 2018
Substitution with Satiation: A New Class of Utility Functions and a Complementary Pivot Algorithm.
Math. Oper. Res., 2018
A Generalization of Birkhoff's Theorem for Distributive Lattices, with Applications to Robust Stable Matchings.
CoRR, 2018
A Natural Generalization of Stable Matching Solved via New Insights into Ideal Cuts.
CoRR, 2018
NC Algorithms for Perfect Matching and Maximum Flow in OneCrossingMinorFree Graphs.
CoRR, 2018
A New Class of Combinatorial Markets with Covering Constraints: Algorithms and Applications.
Proceedings of the TwentyNinth Annual ACMSIAM Symposium on Discrete Algorithms, 2018
Nash Social Welfare for Indivisible Items under Separable, PiecewiseLinear Concave Utilities.
Proceedings of the TwentyNinth Annual ACMSIAM Symposium on Discrete Algorithms, 2018
Proceedings of the 2018 ACM Conference on Economics and Computation, 2018
Proceedings of the 26th Annual European Symposium on Algorithms, 2018
2017
CoRR, 2017
CoRR, 2017
Proceedings of the Web and Internet Economics  13th International Conference, 2017
Settling the complexity of Leontief and PLC exchange markets under exact and approximate equilibria.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017
Proceedings of the 2017 ACM Conference on Economics and Computation, 2017
Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017
Proceedings of the 2017 IEEE International Conference on Bioinformatics and Biomedicine, 2017
2016
Theory Comput., 2016
CoRR, 2016
2015
A Complementary Pivot Algorithm for Market Equilibrium under Separable, PiecewiseLinear Concave Utilities.
SIAM J. Comput., 2015
CoRR, 2015
CoRR, 2015
Proceedings of the Algorithmic Game Theory  8th International Symposium, 2015
ETRCompleteness for Decision Versions of Multiplayer (Symmetric) Nash Equilibria.
Proceedings of the Automata, Languages, and Programming  42nd International Colloquium, 2015
Proceedings of the 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, 2015
2014
SIAM J. Discret. Math., 2014
Dagstuhl Reports, 2014
Leontief Exchange Markets Can Solve Multivariate Polynomial Equations, Yielding FIXP and ETR Hardness.
CoRR, 2014
Proceedings of the Web and Internet Economics  10th International Conference, 2014
Dichotomies in equilibrium computation, and complementary pivot algorithms for a new class of nonseparable utility functions.
Proceedings of the Symposium on Theory of Computing, 2014
Proceedings of the TwentyFifth Annual ACMSIAM Symposium on Discrete Algorithms, 2014
2013
Nonseparable, Concave Utilities Are Easy  in a Perfect Price Discrimination Market Model.
SIAM J. Discret. Math., 2013
Proceedings of the Integer Programming and Combinatorial Optimization, 2013
2012
Rational Convex Programs and Efficient Algorithms for 2Player Nash and Nonsymmetric Bargaining Games.
SIAM J. Discret. Math., 2012
The notion of a rational convex program, and an algorithm for the arrowdebreu Nash bargaining game.
J. ACM, 2012
An Improved Definition of Blossoms and a Simpler Proof of the MV Matching Algorithm
CoRR, 2012
A complementary pivot algorithm for markets under separable, piecewiselinear concave utilities.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012
Proceedings of the Computer Science  Theory and Applications, 2012
2011
New geometryinspired relaxations and algorithms for the metric Steiner tree problem.
Math. Program., 2011
A Perfect Price Discrimination Market Model with Production, and a Rational Convex Program for It.
Math. Oper. Res., 2011
J. ACM, 2011
CoRR, 2011
CoRR, 2011
Proceedings of the ACM SIGCOMM 2011 Conference on Applications, 2011
2010
SIAM J. Discret. Math., 2010
Rationality and Strongly Polynomial Solvability of EisenbergGale Markets with Two Agents.
SIAM J. Discret. Math., 2010
Math. Oper. Res., 2010
Games Econ. Behav., 2010
NonSeparable, Quasiconcave Utilities are Easy  in a Perfect Price Discrimination Market Model
CoRR, 2010
Rational Convex Programs, Their Feasibility, and the ArrowDebreu Nash Bargaining Game
CoRR, 2010
CoRR, 2010
Nonseparable, Quasiconcave Utilities are Easy  in a Perfect Price Discrimination Market Model (Extended Abstract).
Proceedings of the Internet and Network Economics  6th International Workshop, 2010
2Player Nash and Nonsymmetric Bargaining Games: Algorithms and Structural Properties.
Proceedings of the Algorithmic Game Theory  Third International Symposium, 2010
Proceedings of the Equilibrium Computation, 25.04.  30.04.2010, 2010
2009
CoRR, 2009
2008
SIAM J. Comput., 2008
Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems.
SIAM J. Comput., 2008
J. ACM, 2008
Continuity Properties of Equilibria in Some Fisher and ArrowDebreu Market Models.
Electron. Colloquium Comput. Complex., 2008
Electron. Colloquium Comput. Complex., 2008
Algorithmica, 2008
Proceedings of the Internet and Network Economics, 4th International Workshop, 2008
Proceedings of the Algorithm Theory, 2008
Proceedings of the 8th ACM SIGCOMM Internet Measurement Conference, 2008
Proceedings of the 2008 ACM Conference on Emerging Network Experiment and Technology, 2008
2007
Theor. Comput. Sci., 2007
A primaldual algorithm for computing Fisher equilibrium in the absence of gross substitutability property.
Theor. Comput. Sci., 2007
J. ACM, 2007
Proceedings of the Internet and Network Economics, Third International Workshop, 2007
Continuity Properties of Equilibrium Prices and Allocations in Linear Fisher Markets.
Proceedings of the Internet and Network Economics, Third International Workshop, 2007
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007
2006
IEEE Trans. Inf. Theory, 2006
J. Algorithms, 2006
EisenbergGale Markets: Rationality, Strongly Polynomial Solvability, and Competition Monotonicity.
Electron. Colloquium Comput. Complex., 2006
New Results on Rationality and Strongly Polynomial Time Solvability in EisenbergGale Markets.
Proceedings of the Internet and Network Economics, Second International Workshop, 2006
Proceedings of the 2006 IEEE Information Theory Workshop, 2006
Minimum Multicolored Subgraph Problem in Multiplex PCR Primer Set Selection and Population Haplotyping.
Proceedings of the Computational Science, 2006
2005
Decis. Support Syst., 2005
A Computationally Motivated Definition Of Parametric Estimation And Its Applications To The Gaussian Distribution.
Comb., 2005
Proceedings of the Internet and Network Economics, First International Workshop, 2005
Proceedings of the Internet and Network Economics, First International Workshop, 2005
Market equilibria for homothetic, quasiconcave utilities and economies of scale in production.
Proceedings of the Sixteenth Annual ACMSIAM Symposium on Discrete Algorithms, 2005
Proceedings of the 2005 IEEE International Symposium on Information Theory, 2005
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005
2004
J. Algorithms, 2004
An Approximation Algorithm for the Fault Tolerant Metric Facility Location Problem.
Algorithmica, 2004
Randomized truthful auctions of digital goods are randomizations over truthful auctions.
Proceedings of the Proceedings 5th ACM Conference on Electronic Commerce (EC2004), 2004
An AuctionBased Market Equilibrium Algorithm for the Separable Gross Substitutability Case.
Proceedings of the Approximation, 2004
2003
Greedy facility location algorithms analyzed using dual fitting with factorrevealing LP.
J. ACM, 2003
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003
Proceedings of the Proceedings 4th ACM Conference on Electronic Commerce (EC2003), 2003
Extensions of the spending constraintmodel: existence and uniqueness of equilibria (extended abstract).
Proceedings of the Proceedings 4th ACM Conference on Electronic Commerce (EC2003), 2003
An Improved Approximation Scheme for Computing ArrowDebreu Prices for the Linear Case.
Proceedings of the FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science, 2003
2002
A primaldual schema based approximation algorithm for the element connectivity problem.
J. Algorithms, 2002
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002
2001
Approximation algorithms for metric facility location and <i>k</i>Median problems using the primaldual schema and Lagrangian relaxation.
J. ACM, 2001
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001
Proceedings of the Approximation, 2001
Proceedings of the Information Hiding, 4th International Workshop, 2001
Springer, ISBN: 9783540653677, 2001
2000
Theor. Comput. Sci., 2000
IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 2000
Proceedings of the Theoretical Aspects of Computer Science, 2000
1999
SIAM J. Comput., 1999
Proceedings of the ThirtyFirst Annual ACM Symposium on Theory of Computing, 1999
Proceedings of the Tenth Annual ACMSIAM Symposium on Discrete Algorithms, 1999
PrimalDual Approximation Algorithms for Metric Facility Location and kMedian Problems.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999
1998
IEEE Trans. Inf. Theory, 1998
PrimalDual RNC Approximation Algorithms for Set Cover and Covering Integer Programs.
SIAM J. Comput., 1998
Proceedings of the Approximation Algorithms for Combinatorial Optimization, 1998
1997
Algorithmica, 1997
1996
An efficient algorithm for constructing minimal trellises for codes over finite abelian groups.
IEEE Trans. Inf. Theory, 1996
SIAM J. Comput., 1996
1995
SIAM J. Comput., 1995
Math. Program., 1995
Comb., 1995
Proceedings of the Computing and Combinatorics, First Annual International Conference, 1995
1994
Theor. Comput. Sci., 1994
Randomized Parallel Algorithms for Matroid Union and Intersection, With Applications to Arboresences and EdgeDisjoint Spanning Trees.
SIAM J. Comput., 1994
A Theory of Alternating Paths and Blossoms for Proving Correctness of the <i>O</i>(sqrt{<i>V E</i>}) General Graph Maximum Matching Algorithm.
Comb., 1994
Proceedings of the Automata, Languages and Programming, 21st International Colloquium, 1994
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1994
1993
J. Algorithms, 1993
Improved Bounds for the MaxFlow MinMulticut Ratio for Planar and K_r, rFree Graphs.
Inf. Process. Lett., 1993
A polyhedron with all st cuts as vertices, and adjacency of cuts.
Proceedings of the 3rd Integer Programming and Combinatorial Optimization Conference, Erice, Italy, April 29, 1993
PrimalDual Approximation Algorithms for Integral Flow and Multicut in Trees, with Applications to Matching and Set Cover.
Proceedings of the Automata, Languages and Programming, 20nd International Colloquium, 1993
Primaldual RNC approximation algorithms for (multi)set (multi)cover and covering integer programs
Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993
1992
Processor Efficient Parallel Algorithms for the Two Disjoint Paths Problem and for Finding a Kuratowski Homeomorph.
SIAM J. Comput., 1992
Proceedings of the Automata, Languages and Programming, 19th International Colloquium, 1992
1991
Theor. Comput. Sci., 1991
Proceedings of the Algorithms and Data Structures, 1991
1990
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990
A Theory of Alternating Paths and Blossoms for Proving Correctness of the O(\surdVE) General Graph Matching Algorithm.
Proceedings of the 1st Integer Programming and Combinatorial Optimization Conference, 1990
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1990
1989
NC Algorithms for Computing the Number of Perfect Matchings in K_3,3Free Graphs and Related Problems
Inf. Comput., February, 1989
SIAM J. Comput., 1989
J. Algorithms, 1989
Discret. Appl. Math., 1989
1988
NC Algorithms for Computing the Number of Perfect Matchings in K3, 3free Graphs and Related Problems.
Proceedings of the SWAT 88, 1988
1987
Comb., 1987
Algorithmica, 1987
1986
Theor. Comput. Sci., 1986
Theor. Comput. Sci., 1986
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1986
1985
Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985
NC Algorithms for Comparability Graphs, Interval Gaphs, and Testing for Unique Perfect Matching.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1985
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985
1984
Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984
Proceedings of the Advances in Cryptology, 1984
1983
Theor. Comput. Sci., 1983
Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983
Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983
Reducibility Among Protocols.
Proceedings of the Advances in Cryptology, 1983
RSA Bits are 732+epsilon Secure.
Proceedings of the Advances in Cryptology, 1983
1982
Oper. Res. Lett., 1982
Inf. Process. Lett., 1982
1980
Proceedings of the 21st Annual Symposium on Foundations of Computer Science, 1980