Vijay Vazirani | Academic Influence

Vijay Vazirani's AcademicInfluence.com Rankings

Vijay Vazirani

Computer Science

#421

World Rank

#438

Historical Rank

#239

USA Rank

Database

#1514

World Rank

#1589

Historical Rank

#396

USA Rank

computer-science Degrees

Download Badge

Computer Science

Vijay Vazirani's Degrees

PhD Computer Science University of California, Berkeley
Masters Computer Science Stanford University

Similar Degrees You Can Earn

Why Is Vijay Vazirani Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Vijay Virkumar Vazirani is an Indian American distinguished professor of computer science in the Donald Bren School of Information and Computer Sciences at the University of California, Irvine. Education and career Vazirani first majored in electrical engineering at Indian Institute of Technology, Delhi but in his second year he transferred to MIT and received his bachelor's degree in computer science from MIT in 1979 and his Ph.D. from the University of California, Berkeley in 1983. His dissertation, Maximum Matchings without Blossoms, was supervised by Manuel Blum. After postdoctoral research with Michael O. Rabin and Leslie Valiant at Harvard University, he joined the faculty at Cornell University in 1984. He moved to the IIT Delhi as a full professor in 1990, and moved again to the Georgia Institute of Technology in 1995. He was also a McKay Visiting Professor at the University of California, Berkeley, and a Distinguished SISL Visitor at the Social and Information Sciences Laboratory at the California Institute of Technology. In 2017 he moved to the University of California, Irvine as distinguished professor.

(See a Problem?)

Vijay Vazirani's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

Approximation Algorithms (2001) (4239)
Random Generation of Combinatorial Structures from a Uniform Distribution (1986) (1022)
An O(v|v| c |E|) algoithm for finding maximum matching in general graphs (1980) (869)
Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxation (2001) (815)
AdWords and generalized on-line matching (2005) (808)
Matching is as easy as matrix inversion (1987) (770)
NP is as easy as detecting unique solutions (1985) (769)
An optimal algorithm for on-line bipartite matching (1990) (746)
Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP (2002) (460)
Approximate max-flow min-(multi)cut theorems and their applications (1993) (428)
Primal-dual approximation algorithms for integral flow and multicut in trees (1997) (349)
Primal-dual approximation algorithms for metric facility location and k-median problems (1999) (286)
Diversity in times of adversity: probabilistic strategies in microbial survival games. (2005) (285)
Finding k-cuts within twice the optimal (1991) (257)
Applications of approximation algorithms to cooperative games (2001) (224)
NP-Completeness of Some Generalizations of the Maximum Matching Problem (1982) (215)
A primal-dual approximation algorithm for generalized steiner network problems (1993) (209)
Market equilibrium via a primal--dual algorithm for a convex program (2008) (206)
A Graph Theoretic Approach to Software Watermarking (2001) (183)
Market equilibrium via a primal-dual-type algorithm (2002) (177)
Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs (1999) (165)
On-Line Algorithms for Weighted Bipartite Matching and Stable Marriages (1991) (160)
Multiway Cuts in Directed and Node Weighted Graphs (1994) (134)
A theory of alternating paths and blossoms for proving correctness of the $$O(\sqrt V E)$$ general graph maximum matching algorithm (1990) (132)
How many tiers?: pricing in the internet transit market (2011) (131)
Convex Program Duality, Fisher Markets, and Nash Social Welfare (2016) (123)
Multiway cuts in node weighted graphs (2004) (119)
Market equilibrium under separable, piecewise-linear, concave utilities (2011) (112)
Maximum Matchings in General Graphs Through Randomization (1989) (109)
Accelerating simulated annealing for the permanent and combinatorial counting problems (2006) (108)
A stochastic process on the hypercube with applications to peer-to-peer networks (2003) (106)
Strategyproof cost-sharing mechanisms for set cover and facility location games (2003) (106)
Random polynomial time is equal to slightly-random polynomial time (1985) (102)
Efficient and Secure Pseudo-Random Number Generation (1984) (101)
A Greedy Facility Location Algorithm Analyzed Using Dual Fitting (2001) (92)
Approximation Algorithms for Combinatorial Optimization (2000) (91)
On the bidirected cut relaxation for the metric Steiner tree problem (1999) (88)
Eisenberg-Gale markets: Algorithms and game-theoretic properties (2010) (82)
Pfaffian Orientations, 0/1 Permanents, and Even Cycles in Directed Graphs (1988) (76)
NC Algorithms for Computing the Number of Perfect Matchings in K3, 3-free Graphs and Related Problems (1988) (75)
NC Algorithms for Computing the Number of Perfect Matchings in K_3,3-Free Graphs and Related Problems (1989) (75)
Primal-dual RNC approximation algorithms for (multi)-set (multi)-cover and covering integer programs (1993) (74)
On the capacity of multiple unicast sessions in undirected graphs (2005) (73)
Fast monitoring of traffic subpopulations (2008) (72)
Market equilibria for homothetic, quasi-concave utilities and economies of scale in production (2005) (70)
Suboptimal Cuts: Their Enumeration, Weight and Number (Extended Abstract) (1992) (67)
An O(sqrt(|v|) |E|) Algorithm for Finding Maximum Matching in General Graphs (1980) (67)
Primal-Dual Approximation Algorithms for Integral Flow and Multicut in Trees, with Applications to Matching and Set Cover (1993) (66)
Nash Social Welfare for Indivisible Items under Separable, Piecewise-Linear Concave Utilities (2016) (63)
Efficient and Secure Pseudo-Random Number Generation (Extended Abstract) (1984) (62)
An efficient algorithm for constructing minimal trellises for codes over finite Abelian groups (1996) (61)
Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs (1989) (61)
NC Algorithms for Comparability Graphs, Interval Gaphs, and Testing for Unique Perfect Matching (1985) (60)
Algorithmic Game Theory: Combinatorial Algorithms for Market Equilibria (2007) (59)
Eisenberg-Gale markets: algorithms and structural properties (2007) (58)
Equitable cost allocations via primal-dual-type algorithms (2002) (56)
An Improved Approximation Scheme for Computing Arrow-Debreu Prices for the Linear Case (2003) (52)
Trapdoor pseudo-random number generators, with applications to protocol design (1983) (51)
The notion of a rational convex program, and an algorithm for the arrow-debreu Nash bargaining game (2012) (51)
Spending Constraint Utilities with Applications to the Adwords Market (2010) (51)
An Approximation Algorithm for the Fault Tolerant Metric Facility Location Problem (2004) (49)
Learning Economic Parameters from Revealed Preferences (2014) (48)
A new heuristic for rectilinear Steiner trees (1999) (48)
A Complementary Pivot Algorithm for Market Equilibrium under Separable, Piecewise-Linear Concave Utilities (2015) (45)
Improved Bounds for the Max-Flow Min-Multicut Ratio for Planar and K_r, r-Free Graphs (1993) (44)
Randomized parallel algorithms for matroid union and intersection, with applications to arboresences and edge-disjoint spanning trees (1992) (42)
Representing and Enumerating Edge Connectivity Cuts in RNC (1991) (41)
A microbial modified prisoner's dilemma game: how frequency-dependent selection can lead to random phase variation. (2005) (41)
Global Wire Routing in Two-Dimensional Arrays (Extended Abstract) (1983) (40)
Allocation of Divisible Goods Under Lexicographic Preferences (2012) (40)
A primal-dual schema based approximation algorithm for the element connectivity problem (2002) (39)
Finding separator cuts in planar graphs within twice the optimal (1994) (38)
Approximate Max--ow Min-(multi)cut Theorems and Their Applications (1993) (38)
An Auction-Based Market Equilibrium Algorithm for the Separable Gross Substitutability Case (2004) (38)
MINT: a Market for INternet Transit (2008) (37)
Random Polynomial Time is Equal to Semi-Random Polynomial Time (1988) (37)
ETR-Completeness for Decision Versions of Multi-player (Symmetric) Nash Equilibria (2015) (35)
An Improved Definition of Blossoms and a Simpler Proof of the MV Matching Algorithm (2012) (34)
A Theory of Alternating Paths and Blossoms for Proving Correctness of the O(\surdVE) General Graph Matching Algorithm (1990) (34)
Scheduling open shops with parallel machines (1982) (33)
New Results on Rationality and Strongly Polynomial Time Solvability in Eisenberg-Gale Markets (2006) (31)
Algorithmic Game Theory: Basic Solution Concepts and Computational Issues (2007) (31)
∃R-Completeness for Decision Versions of Multi-Player (Symmetric) Nash Equilibria (2018) (30)
Price of Anarchy, Locality Gap, and a Network Service Provider Game (2005) (29)
Minimum Multicolored Subgraph Problem in Multiplex PCR Primer Set Selection and Population Haplotyping (2006) (26)
A natural encoding scheme proved probabilistic polynomial complete (1982) (26)
The Minimum k-Colored Subgraph Problem in Haplotyping and DNA Primer Selection (2004) (24)
Solving the Weighted Parity Problem for Gammoids by Reduction to Graphic Matching (1982) (23)
New geometry-inspired relaxations and algorithms for the metric Steiner tree problem (2008) (23)
An approximation algorithm for the fault tolerant metric facility location problem (2000) (23)
Randomized truthful auctions of digital goods are randomizations over truthful auctions (2004) (22)
Settling the complexity of Leontief and PLC exchange markets under exact and approximate equilibria (2017) (22)
Planar Graph Perfect Matching Is in NC (2017) (22)
Processor efficient parallel algorithms for the two disjoint paths problem, and for finding a Kuratowski homeomorph (1989) (21)
Finding Stable Matchings that are Robust to Errors in the Input (2018) (20)
Recent results on approximating the Steiner tree problem and its generalizations (2000) (19)
RSA bits are .732 + ε secure (1984) (18)
Mutation, Sexual Reproduction and Survival in Dynamic Environments (2015) (17)
Dichotomies in equilibrium computation, and complementary pivot algorithms for a new class of non-separable utility functions (2014) (17)
Efficient Sequential and Parallel Algorithms for Maximal Bipartite Sets (1993) (17)
The two-processor scheduling problem is in R-NC (1985) (16)
A primal-dual algorithm for computing Fisher equilibrium in the absence of gross substitutability property (2005) (16)
Solvency Games (2008) (16)
A polyhedron with alls—t cuts as vertices, and adjacency of cuts (1995) (16)
Primal-Dual Schema Based Approximation Algorithms (2000) (15)
Planar Graph Coloring is not Self-Reducible, Assuming P != NP (1991) (15)
A Perfect Price Discrimination Market Model with Production, and a (Rational) Convex Program for It (2010) (15)
Matching Is as Easy as the Decision Problem, in the NC Model (2019) (14)
Cycles in Zero-Sum Differential Games and Biological Diversity (2018) (14)
Rational Convex Programs and Efficient Algorithms for 2-Player Nash and Nonsymmetric Bargaining Games (2012) (14)
Design is as Easy as Optimization (2006) (13)
Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets (2020) (13)
A Simplification of the MV Matching Algorithm and its Proof (2012) (13)
The Two-Processor Scheduling Problem is in Random NC (1989) (12)
The "art of trellis decoding" is computationally hard-for large fields (1998) (12)
The General Graph Matching Game: Approximate Core (2021) (12)
An Incentive Compatible, Efficient Market for Air Traffic Flow Management (2013) (11)
On-line Algorithms for Weighted Matching and Stable Marriages (1990) (11)
An auction-based market equilibrium algorithm for a production model (2007) (10)
Group Strategyproofness and No Subsidy via LP-Duality (1999) (10)
NC Algorithms for Comparability Graphs, Interval Graphs, and Unique Perfect Matchings (1986) (10)
Building a Better Mousetrap (2007) (10)
Continuity Properties of Equilibrium Prices and Allocations in Linear Fisher Markets (2007) (10)
New Convex Programs for Fisher's Market Model and its Generalizations (2016) (9)
NC Algorithms for Computing a Perfect Matching, the Number of Perfect Matchings, and a Maximum Flow in One-Crossing-Minor-Free Graphs (2019) (9)
2-Player Nash and Nonsymmetric Bargaining Games: Algorithms and Structural Properties (2009) (9)
Profit-maximizing multicast pricing by approximating fixed points [Extended Abstract] (2003) (9)
A Perfect Price Discrimination Market Model with Production, and a Rational Convex Program for It (2011) (8)
Strategyproof cost-sharing Mechanisms for Set Cover and Facility Location Problems (2002) (8)
Reducibility Among Protocols (1983) (8)
Nash Bargaining Via Flexible Budget Markets (2008) (8)
A complementary pivot algorithm for markets under separable, piecewise-linear concave utilities (2012) (8)
Opinion Dynamics in Networks: Convergence, Stability and Lack of Explosion (2016) (8)
Substitution with Satiation: A New Class of Utility Functions and a Complementary Pivot Algorithm (2018) (8)
Stability-Preserving, Time-Efficient Mechanisms for School Choice in Two Rounds (2020) (7)
An Arrow-Debreu Extension of the Hylland-Zeckhauser Scheme: Equilibrium Existence and Algorithms (2020) (7)
Scheduling on Unrelated Parallel Machines (2003) (7)
NC Algorithms for Perfect Matching and Maximum Flow in One-Crossing-Minor-Free Graphs (2018) (7)
Algorithmic Game Theory: Preface (2007) (7)
A Proof of the MV Matching Algorithm (2020) (6)
A Natural Generalization of Stable Matching Solved via New Insights into Ideal Cuts (2018) (6)
A Generalization of Birkhoff's Theorem for Distributive Lattices, with Applications to Robust Stable Matchings (2018) (6)
Dichotomies in Equilibrium Computation and Membership of PLC Markets in FIXP (2016) (6)
On Computability of Equilibria in Markets with Production (2013) (6)
A Limited-Backtrack Greedy Schema for Approximation Algorithms (1994) (6)
Settling Some Open Problems on 2-Player Symmetric Nash Equilibria (2014) (6)
A New Class of Combinatorial Markets with Covering Constraints: Algorithms and Applications (2015) (5)
Leontief Exchange Markets Can Solve Multivariate Polynomial Equations, Yielding FIXP and ETR Hardness (2014) (5)
Primal-dual RNC approximation of covering integer programs (1999) (5)
Sampling a Population with a Semi-Random Source (1986) (5)
Extensions of the spending constraint model: existence and uniqueness of equilibria [Extended Abstract] (2003) (5)
Random Bichromatic Matchings (2006) (5)
Introduction to LP-Duality (2003) (5)
Combinatorial Algorithms for Matching Markets via Nash Bargaining: One-Sided, Two-Sided and Non-Bipartite (2021) (5)
A Market for Scheduling, with Applications to Cloud Computing (2015) (4)
Continuity Properties of Equilibria in Some Fisher and Arrow-Debreu Market Models (2009) (4)
Rock-Paper-Scissors, Differential Games and Biological Diversity (2017) (4)
The Computational Worldview and the Sciences : a Report on Two Workshops (2007) (4)
Stable Matchings, Robust Solutions, and Distributive Lattices (2018) (4)
Randomized Online Algorithms for Adwords (2021) (4)
Majorizing estimators and the approximation of #P-complete problems (1999) (4)
Rationality and Strongly Polynomial Solvability of Eisenberg--Gale Markets with Two Agents (2010) (3)
Nonseparable, Concave Utilities Are Easy - in a Perfect Price Discrimination Market Model (2013) (3)
Set Cover via Dual Fitting (2003) (3)
Online Bipartite Matching and Adwords (2021) (3)
The Steiner Tree Problem and Its Generalizations (1998) (3)
2-Player Nash and Nonsymmetric Bargaining via Flexible Budget Markets (2009) (3)
Efficiency, Fairness and Competitiveness in Nash Bargaining Games (2008) (3)
Rational Convex Programs, Their Feasibility, and the Arrow-Debreu Nash Bargaining Game (2010) (3)
A Computationally Motivated Definition Of Parametric Estimation And Its Applications To The Gaussian Distribution (2005) (3)
Minimum Makespan Scheduling (2003) (2)
Efficient algorithms for market equilibria (2007) (2)
Primal-Dual Schema Based Approximation Algorithms (Abstract) (1995) (2)
Substitution with Satiation : A New Class of Utility Functions and a Complementary Pivot Equilibrium Algorithm ∗ Jugal Garg (2015) (2)
Posted price profit maximization for multicast by approximating fixed points (2006) (2)
A Real Polynomial for Bipartite Graph Minimum Weight Perfect Matchings (2020) (2)
The game of survival: Sexual evolution in dynamic environments (2015) (2)
Insights into the Core of the Assignment Game via Complementarity (2022) (2)
A Fast Parallel Algorithm for Finding a Maximal Bipartite Set (1990) (2)
New Characterizations of Core Imputations of Matching and b-Matching Games (2022) (2)
Nash-Bargaining-Based Models for Matching Markets: One-Sided and Two-Sided; Fisher and Arrow-Debreu (2021) (2)
Stability-Preserving, Incentive-Compatible, Time-Efficient Mechanisms for Increasing School Capacity (2019) (2)
Towards a Practical, Budget-Oblivious Algorithm for the Adwords Problem under Small Bids (2022) (2)
Submodularity Helps in Nash and Nonsymmetric Bargaining Games (2014) (2)
NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs (2018) (2)
The 'Art of Trellis Decoding' Is Computationally Hardi - For Large Fields (1998) (2)
RSA Bits are 732+epsilon Secure (1983) (2)
Enhancing techniques in lp based approximation algorithms (2000) (2)
Nash-Bargaining-Based Models for Matching Markets, with Implementations and Experimental Results (2021) (2)
Matching Markets with Transfers and Salaries (DRAFT: Not for distribution) (2021) (1)
The Investment Management Game: Extending the Scope of the Notion of Core (2023) (1)
Approximation algorithms for combinatorial optimization : 5th International Workshop, APPROX 2002, Rome, Italy, September 17-21, 2002 : proceedings (2002) (1)
Online Bipartite Matching and Adwords (Invited Talk) (2022) (1)
Eisenberg-Gale Markets: Rationality, Strongly Polynomial Solvability, and Competition Monotonicity (2006) (1)
One-Sided Matching Markets with Endowments: Equilibria and Algorithms (2020) (1)
Discrete Algorithms Seminar Title: " Overhang " Title: " a Cubic Kernel for Feedback Vertex Set " (2009) (1)
An Extension of the Birkhoff-von Neumann Theorem to Non-Bipartite Graphs (2020) (1)
A Performance-Based Scheme for Pricing Resources in the Cloud (2016) (1)
Approximating the Permanent in O ∗ ( n 7 ) Time (2004) (1)
Algorithmes d'approximation (Collection IRIS) (2007) (1)
Thrifty Algorithms for Multistage Robust Optimization (2013) (1)
A Market for Air Traffic Flow Management (2011) (1)
Equilibrium Pricing of Digital Goods via a New Market Model (2010) (1)
Multiway Cut and k-Cut (2003) (1)
Rounding Applied to Set Cover (2003) (1)
A Structural and Algorithmic Study of Stable Matching Lattices of "Nearby" Instances, with Applications (2018) (1)
Feedback Vertex Set (2003) (1)
Multicut and Integer Multicommodity Flow in Trees (2003) (0)
Multicut in General Graphs (2003) (0)
Algorithmic Aspects of the Internet (2004) (0)
Pro t-Maximizing Multi ast Pri ing by Approximating Fixed Points (2015) (0)
10171 Abstracts Collection - Equilibrium Computation (2010) (0)
Jv J Jej) Algorithm for Finding Maxi- Perfect Matching under Translation 7 Perfect Matching under Translation (0)
10171 Abstracts Collection Equilibrium Computation Dagstuhl Seminar (2008) (0)
Cores of Games via Total Dual Integrality, with Applications to Perfect Graphs and Polymatroids (2022) (0)
Towards an Internet Connectivity Market (2009) (0)
Concave Flow on Small Depth Directed Networks (2017) (0)
Equitable Cost Allocations via Primal--Dual-Type Algorithms (2008) (0)
Multi-Agent Combinatorial Optimization under Submodular Functions (2011) (0)
A Theory of Alternating Paths and Blossoms, from the Perspective of Minimum Length (2021) (0)
LP-Duality Theory and the Cores of Games (2023) (0)
Algorithms and markets (2010) (0)
PROCESSOREFFICIENTPARALLELALGORITHMSFORTHETWO DISJOINT PATHSPROBLEMANDFORFINDINGAKURATOWSKIHOMEOMORPH (1992) (0)
Non-separable, Quasiconcave Utilities are Easy - in a Perfect Price Discrimination Market Model (Extended Abstract) (2010) (0)
A Structural and Algorithmic Study of Stable Matching Lattices of Multiple Instances (2023) (0)
Can the Theory of Algorithms Ratify the "Invisible Hand of the Market"? (2012) (0)
Equilibrium Computation (2014) (0)
An Optimal Algorithm for On-lineBipartite Matching (2015) (0)
Computing in Games (2007) (0)
Submodularity Helps in Nash and Nonsymmetric Bargaining Deeparnab Chakrabarty (2009) (0)
Global Wire Routing in Two-Dimensional Arrays 1 (1987) (0)
Insights into the Core of Matching Games via Complementarity (2022) (0)
Further Results on Stability-Preserving Mechanisms for School Choice (2019) (0)
Probabilistic estimation of overlap graphs for large sequence datasets (2017) (0)
Equilibrium Computation (Dagstuhl Seminar 14342) (2014) (0)
Hardness of Approximation (2003) (0)
Set Cover via the Primal-Dual Schema (2003) (0)
Randomized, Budget-Oblivious Online Algorithms for Adwords (2021) (0)
Settling the Complexity of Arrow-Debreu Markets under Leontief and PLC Utilities, using the Classes FIXP and \Exists-R. (2014) (0)
OntheCoding Advantage ofMultiple Unicast Sessions inUndirected Graphs (2006) (0)
Algorithms and mechanism design for multi-agent systems (2010) (0)
One-Sided Matching Markets (DRAFT: Not for distribution) (2021) (0)
Algorithmic Game Theory and the Internet (Dagstuhl Seminar 03291) (2021) (0)
A Simple Characterization for Truth-Revealing Single-Item Auctions (2005) (0)
Equilibrium Pricing of Semantically Substitutable Digital Goods (2010) (0)
Markets and the Primal-Dual Paradigm (2007) (0)
On the Coding Advantage of Multiple Unicast Sessions in Undirected Graphs (2006) (0)
A Pseudo-Deterministic RNC Algorithm for General Graph Perfect Matching (2019) (0)
Modeling Tiered Pricing in the Internet Transit Market (2011) (0)
Two-Sided Markets: Stable Matching (DRAFT: Not for distribution) (2021) (0)
ALGORITHMS: Collaborative research: development of vector space based methods for protein structure prediction (2007) (0)
The Case for Microcontracts for Internet Connectivity (2010) (0)
Steiner Tree and TSP (2003) (0)

This paper list is powered by the following services:

Other Resources About Vijay Vazirani

en.wikipedia.org

What Schools Are Affiliated With Vijay Vazirani?

Vijay Vazirani is affiliated with the following schools:

Image Attributions

Image Source for Vijay Vazirani