Vijay V. Vazirani
According to our database^{1},
Vijay V. Vazirani
authored at least 153 papers
between 1980 and 2019.
Collaborative distances:
Collaborative distances:
Timeline
Legend:
Book In proceedings Article PhD thesis OtherLinks
Homepages:

at viaf.org

at id.loc.gov

at dnb.info

at isni.org

at dl.acm.org
On csauthors.net:
Bibliography
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 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
Cycles in ZeroSum Differential Games and Biological Diversity.
Proceedings of the 2018 ACM Conference on Economics and Computation, 2018
Planar Graph Perfect Matching Is in NC.
Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018
Finding Stable Matchings That Are Robust to Errors in the Input.
Proceedings of the 26th Annual European Symposium on Algorithms, 2018
2017
A PerformanceBased Scheme for Pricing Resources in the Cloud.
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
Convex Program Duality, Fisher Markets, and Nash Social Welfare.
Proceedings of the 2017 ACM Conference on Economics and Computation, 2017
Mutation, Sexual Reproduction and Survival in Dynamic Environments.
Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017
Opinion Dynamics in Networks: Convergence, Stability and Lack of Explosion.
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017
An Incentive Compatible, Efficient Market for Air Traffic Flow Management.
Proceedings of the Computing and Combinatorics  23rd International Conference, 2017
2016
Dichotomies in Equilibrium Computation and Membership of PLC Markets in FIXP.
Theory of Computing, 2016
2015
A Complementary Pivot Algorithm for Market Equilibrium under Separable, PiecewiseLinear Concave Utilities.
SIAM J. Comput., 2015
Settling Some Open Problems on 2Player Symmetric Nash Equilibria.
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
Allocation of Divisible Goods Under Lexicographic Preferences.
Proceedings of the 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, 2015
2014
Submodularity Helps in Nash and Nonsymmetric Bargaining Games.
SIAM J. Discrete Math., 2014
Equilibrium Computation (Dagstuhl Seminar 14342).
Dagstuhl Reports, 2014
Learning Economic Parameters from Revealed Preferences.
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
On Computability of Equilibria in Markets with Production.
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. Discrete Math., 2013
Thrifty Algorithms for Multistage Robust Optimization.
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. Discrete Math., 2012
A complementary pivot algorithm for markets under separable, piecewiselinear concave utilities.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012
The notion of a rational convex program, and an algorithm for the ArrowDebreu Nash bargaining game.
Proceedings of the TwentyThird Annual ACMSIAM Symposium on Discrete Algorithms, 2012
Can the Theory of Algorithms Ratify the "Invisible Hand of the Market"?
Proceedings of the Computer Science  Theory and Applications, 2012
2011
A Perfect Price Discrimination Market Model with Production, and a Rational Convex Program for It.
Math. Oper. Res., 2011
How many tiers?: pricing in the internet transit market.
Proceedings of the ACM SIGCOMM 2011 Conference on Applications, 2011
2010
Rationality and Strongly Polynomial Solvability of EisenbergGale Markets with Two Agents.
SIAM J. Discrete Math., 2010
Spending Constraint Utilities with Applications to the Adwords Market.
Math. Oper. Res., 2010
EisenbergGale markets: Algorithms and gametheoretic properties.
Games and Economic Behavior, 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
A Perfect Price Discrimination Market Model with Production, and a (Rational) Convex Program for It.
Proceedings of the Algorithmic Game Theory  Third International Symposium, 2010
Market Equilibrium under Separable, PiecewiseLinear, Concave Utilities.
Proceedings of the Innovations in Computer Science, 2010
10171 Abstracts Collection  Equilibrium Computation.
Proceedings of the Equilibrium Computation, 25.04.  30.04.2010, 2010
2009
Continuity Properties of Equilibria in Some Fisher and ArrowDebreu Market Models.
Proceedings of the Internet and Network Economics, 5th International Workshop, 2009
2008
Equitable Cost Allocations via PrimalDualType Algorithms.
SIAM J. Comput., 2008
Market equilibrium via a primaldual algorithm for a convex program.
J. ACM, 2008
Efficiency, Fairness and Competitiveness in Nash Bargaining Games.
Proceedings of the Internet and Network Economics, 4th International Workshop, 2008
Nash Bargaining Via Flexible Budget Markets.
Proceedings of the Algorithm Theory, 2008
New GeometryInspired Relaxations and Algorithms for the Metric Steiner Tree Problem.
Proceedings of the Integer Programming and Combinatorial Optimization, 2008
Fast monitoring of traffic subpopulations.
Proceedings of the 8th ACM SIGCOMM Internet Measurement Conference, 2008
Solvency Games.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2008
MINT: a Market for INternet Transit.
Proceedings of the 2008 ACM Conference on Emerging Network Experiment and Technology, 2008
Nash Bargaining Via Flexible Budget Markets.
Proceedings of the Algorithmic Aspects in Information and Management, 2008
2007
AdWords and generalized online matching.
J. ACM, 2007
Markets and the PrimalDual Paradigm.
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
EisenbergGale markets: algorithms and structural properties.
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007
2006
On the capacity of multiple unicast sessions in undirected graphs.
IEEE Trans. Information Theory, 2006
Posted price profit maximization for multicast by approximating fixed points.
J. Algorithms, 2006
EisenbergGale Markets: Rationality, Strongly Polynomial Solvability, and Competition Monotonicity.
Electronic Colloquium on Computational Complexity (ECCC), 2006
New Results on Rationality and Strongly Polynomial Time Solvability in EisenbergGale Markets.
Proceedings of the Internet and Network Economics, Second International Workshop, 2006
Accelerating simulated annealing for the permanent and combinatorial counting problems.
Proceedings of the Seventeenth Annual ACMSIAM Symposium on Discrete Algorithms, 2006
Random Bichromatic Matchings.
Proceedings of the LATIN 2006: Theoretical Informatics, 2006
On the Coding Advantage of Multiple Unicast Sessions in Undirected Graphs.
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
Design Is as Easy as Optimization.
Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006
2005
A Computationally Motivated Definition Of Parametric Estimation And Its Applications To The Gaussian Distribution.
Combinatorica, 2005
An AuctionBased Market Equilibrium Algorithm for a Production Model.
Proceedings of the Internet and Network Economics, First International Workshop, 2005
A Simple Characterization for TruthRevealing SingleItem Auctions.
Proceedings of the Internet and Network Economics, First International Workshop, 2005
A PrimalDual Algorithm for Computing Fisher Equilibrium in the Absence of Gross Substitutability Property.
Proceedings of the Internet and Network Economics, First International Workshop, 2005
Price of Anarchy, Locality Gap, and a Network Service Provider Game.
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
On the capacity of multiple unicast sessions in undirected graphs.
Proceedings of the 2005 IEEE International Symposium on Information Theory, 2005
AdWords and Generalized Online Matching.
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005
2004
Multiway cuts in node weighted graphs.
J. Algorithms, 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
A stochastic process on the hypercube with applications to peertopeer networks.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003
Profitmaximizing multicast pricing by approximating fixed points.
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
Strategyproof costsharing mechanisms for set cover and facility location games.
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
Equitable cost allocations via primaldualtype algorithms.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002
Market Equilibrium via a PrimalDualType Algorithm.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002
2001
Approximation algorithms for metric facility location and kMedian problems using the primaldual schema and Lagrangian relaxation.
J. ACM, 2001
Applications of approximation algorithms to cooperative games.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001
A Greedy Facility Location Algorithm Analyzed Using Dual Fitting.
Proceedings of the Approximation, 2001
A Graph Theoretic Approach to Software Watermarking.
Proceedings of the Information Hiding, 4th International Workshop, 2001
Approximation algorithms.
Springer, ISBN: 9783540653677, 2001
2000
Recent results on approximating the Steiner tree problem and its generalizations.
Theor. Comput. Sci., 2000
An approximation algorithm for the fault tolerant metric facility location problem.
Proceedings of the Approximation Algorithms for Combinatorial Optimization, 2000
PrimalDual Schema Based Approximation Algorithms.
Proceedings of the Theoretical Aspects of Computer Science, 2000
1999
Finding Separator Cuts in Planar Graphs within Twice the Optimal.
SIAM J. Comput., 1999
Majorizing Estimators and the Approximation of #PComplete Problems.
Proceedings of the ThirtyFirst Annual ACM Symposium on Theory of Computing, 1999
On the Bidirected Cut Relaxation for the Metric Steiner Tree Problem.
Proceedings of the Tenth Annual ACMSIAM Symposium on Discrete Algorithms, 1999
A PrimalDual Schema Based Approximation Algorithm for the Element Connectivity Problem.
Proceedings of the Tenth Annual ACMSIAM Symposium on Discrete Algorithms, 1999
A new heuristic for rectilinear Steiner trees.
Proceedings of the 1999 IEEE/ACM International Conference on ComputerAided Design, 1999
PrimalDual Approximation Algorithms for Metric Facility Location and kMedian Problems.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999
1998
The 'Art of Trellis Decoding' Is Computationally Hardi  For Large Fields.
IEEE Trans. Information Theory, 1998
PrimalDual RNC Approximation Algorithms for Set Cover and Covering Integer Programs.
SIAM J. Comput., 1998
The Steiner Tree Problem and Its Generalizations.
Proceedings of the Approximation Algorithms for Combinatorial Optimization, 1998
1997
PrimalDual Approximation Algorithms for Integral Flow and Multicut in Trees.
Algorithmica, 1997
1996
An Efficient Algorithm for Constructing Minimal Trellises for Codes over Finite Abelian Groups.
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996
1995
Finding k Cuts within Twice the Optimal.
SIAM J. Comput., 1995
A polyhedron with alls  t cuts as vertices, and adjacency of cuts.
Math. Program., 1995
PrimalDual Schema Based Approximation Algorithms (Abstract).
Proceedings of the Computing and Combinatorics, First Annual International Conference, 1995
1994
A Theory of Alternating Paths and Blossoms for Proving Correctness of the O(sqrt{V E}) General Graph Maximum Matching Algorithm.
Combinatorica, 1994
Multiway Cuts in Directed and Node Weighted Graphs.
Proceedings of the Automata, Languages and Programming, 21st International Colloquium, 1994
A LimitedBacktrack Greedy Schema for Approximation Algorithms.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1994
Finding separator cuts in planar graphs within twice the optimal
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994
1993
Efficient Sequential and Parallel Algorithms for Maximal Bipartite Sets.
J. Algorithms, 1993
Improved Bounds for the MaxFlow MinMulticut Ratio for Planar and K_r, rFree Graphs.
Inf. Process. Lett., 1993
A primaldual approximation algorithm for generalized Steiner network problems.
Proceedings of the TwentyFifth Annual ACM Symposium on Theory of Computing, 1993
Approximate maxflow min(multi)cut theorems and their applications.
Proceedings of the TwentyFifth Annual ACM Symposium on Theory of Computing, 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
Randomized Parallel Algorithms for Matroid Union and Intersection, with Applications to Arboresences and EdgeDisjoint Spanning Trees.
Proceedings of the Third Annual ACM/SIGACTSIAM Symposium on Discrete Algorithms, 1992
Suboptimal Cuts: Their Enumeration, Weight and Number (Extended Abstract).
Proceedings of the Automata, Languages and Programming, 19th International Colloquium, 1992
1991
Planar Graph Coloring is not SelfReducible, Assuming P != NP.
Theor. Comput. Sci., 1991
Representing and Enumerating Edge Connectivity Cuts in RNC.
Proceedings of the Algorithms and Data Structures, 1991
OnLine Algorithms for Weighted Bipartite Matching and Stable Marriages.
Proceedings of the Automata, Languages and Programming, 18th International Colloquium, 1991
Finding kcuts within Twice the Optimal
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991
1990
An Optimal Algorithm for Online Bipartite Matching
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
A Fast Parallel Algorithm for Finding a Maximal Bipartite Set.
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
The TwoProcessor Scheduling Problem is in Random NC.
SIAM J. Comput., 1989
Maximum Matchings in General Graphs Through Randomization.
J. Algorithms, 1989
Pfaffian orientations, 01 permanents, and even cycles in directed graphs.
Discrete Applied Mathematics, 1989
Processor Efficient Parallel Algorithms for the Two Disjoint Paths Problem, and for Finding a Kuratowski Homeomorph
Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989
1988
NC Algorithms for Computing the Number of Perfect Matchings in K3, 3free Graphs and Related Problems.
Proceedings of the SWAT 88, 1988
Pfaffian Orientations, 0/1 Permanents, and Even Cycles in Directed Graphs.
Proceedings of the Automata, Languages and Programming, 15th International Colloquium, 1988
1987
Matching is as easy as matrix inversion.
Combinatorica, 1987
Global Wire Routing in TwoDimensional Arrays.
Algorithmica, 1987
Matching Is as Easy as Matrix Inversion
Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987
1986
NP is as Easy as Detecting Unique Solutions.
Theor. Comput. Sci., 1986
Random Generation of Combinatorial Structures from a Uniform Distribution.
Theor. Comput. Sci., 1986
Sampling a Population with a SemiRandom Source.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1986
1985
The TwoProcessor Scheduling Problem is in RNC
Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985
NP Is as Easy as Detecting Unique Solutions
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
Random Polynomial Time Is Equal to Slightlyrandom Polynomial Time
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985
1984
Efficient and Secure PseudoRandom Number Generation (Extended Abstract)
Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984
Efficient and Secure PseudoRandom Number Generation.
Proceedings of the Advances in Cryptology, 1984
1983
A Natural Encoding Scheme Proved Probabilistic Polynomial Complete.
Theor. Comput. Sci., 1983
Trapdoor Pseudorandom Number Generators, with Applications to Protocol Design
Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983
Global Wire Routing in TwoDimensional Arrays (Extended Abstract)
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
Scheduling open shops with parallel machines.
Oper. Res. Lett., 1982
NPCompleteness of Some Generalizations of the Maximum Matching Problem.
Inf. Process. Lett., 1982
A Natural Encoding Scheme Proved Probabilistic Polynomial Complete
Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 1982
1980
An O(sqrt(v) E) Algorithm for Finding Maximum Matching in General Graphs
Proceedings of the 21st Annual Symposium on Foundations of Computer Science, 1980