Vijay V. Vazirani

CoRR, 2024

Cardinal-Utility Matching Markets: The Quest for Envy-Freeness, Pareto-Optimality, and Efficient Computability.

[BibT_eX]

[DOI]

CoRR, 2024

2023

A real polynomial for bipartite graph minimum weight perfect matchings.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2023

Two-Sided Matching Markets: Impossibility Results on Existence of Efficient and Envy Free Solutions.

[BibT_eX]

[DOI]

CoRR, 2023

A Structural and Algorithmic Study of Stable Matching Lattices of Multiple Instances.

[BibT_eX]

[DOI]

CoRR, 2023

LP-Duality Theory and the Cores of Games.

[BibT_eX]

[DOI]

CoRR, 2023

The Investment Management Game: Extending the Scope of the Notion of Core.

[BibT_eX]

[DOI]

CoRR, 2023

Towards a Practical, Budget-Oblivious Algorithm for the Adwords Problem Under Small Bids.

[BibT_eX]

[DOI]

Proceedings of the 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2023

A Nash-Bargaining-Based Mechanism for One-Sided Matching Markets and Dichotomous Utilities.

[BibT_eX]

[DOI]

Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, 2023

2022

The general graph matching game: Approximate core.

[BibT_eX]

[DOI]

Games Econ. Behav., 2022

Cores of Games via Total Dual Integrality, with Applications to Perfect Graphs and Polymatroids.

[BibT_eX]

[DOI]

CoRR, 2022

Insights into the Core of the Assignment Game via Complementarity.

[BibT_eX]

[DOI]

CoRR, 2022

Online Bipartite Matching and Adwords (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science, 2022

Nash-Bargaining-Based Models for Matching Markets: One-Sided and Two-Sided; Fisher and Arrow-Debreu.

[BibT_eX]

[DOI]

Mojtaba Hosseini

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

New Characterizations of Core Imputations of Matching and b-Matching Games.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2022

One-Sided Matching Markets with Endowments: Equilibria and Algorithms.

[BibT_eX]

[DOI]

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 One-Crossing-Minor-Free Graphs.

[BibT_eX]

[DOI]

David Eppstein

SIAM J. Comput., 2021

Randomized Online Algorithms for Adwords.

[BibT_eX]

[DOI]

CoRR, 2021

Combinatorial Algorithms for Matching Markets via Nash Bargaining: One-Sided, Two-Sided and Non-Bipartite.

[BibT_eX]

[DOI]

Ioannis Panageas

CoRR, 2021

Nash-Bargaining-Based Models for Matching Markets, with Implementations and Experimental Results.

[BibT_eX]

[DOI]

Mojtaba Hosseini

CoRR, 2021

Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets.

[BibT_eX]

[DOI]

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

2020

An incentive compatible, efficient market for air traffic flow management.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2020

Planar Graph Perfect Matching Is in NC.

[BibT_eX]

[DOI]

Nima Anari

J. ACM, 2020

A Proof of the MV Matching Algorithm.

[BibT_eX]

[DOI]

CoRR, 2020

An Extension of the Birkhoff-von Neumann Theorem to Non-Bipartite Graphs.

[BibT_eX]

[DOI]

CoRR, 2020

An Arrow-Debreu Extension of the Hylland-Zeckhauser Scheme: Equilibrium Existence and Algorithms.

[BibT_eX]

[DOI]

CoRR, 2020

Matching Is as Easy as the Decision Problem, in the NC Model.

[BibT_eX]

[DOI]

Nima Anari

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

Stability-Preserving, Time-Efficient Mechanisms for School Choice in Two Rounds.

[BibT_eX]

[DOI]

Proceedings of the 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2020

2019

Further Results on Stability-Preserving Mechanisms for School Choice.

[BibT_eX]

[DOI]

Karthik Gajulapalli

James A. Liu

CoRR, 2019

Stability-Preserving, Incentive-Compatible, Time-Efficient Mechanisms for Increasing School Capacity.

[BibT_eX]

[DOI]

CoRR, 2019

A Pseudo-Deterministic RNC Algorithm for General Graph Perfect Matching.

[BibT_eX]

[DOI]

Nima Anari

CoRR, 2019

NC Algorithms for Computing a Perfect Matching, the Number of Perfect Matchings, and a Maximum Flow in One-Crossing-Minor-Free Graphs.

[BibT_eX]

[DOI]

David Eppstein

Proceedings of the 31st ACM on Symposium on Parallelism in Algorithms and Architectures, 2019

2018

∃R-Completeness for Decision Versions of Multi-Player (Symmetric) Nash Equilibria.

[BibT_eX]

[DOI]

ACM Trans. Economics and Comput., 2018

Substitution with Satiation: A New Class of Utility Functions and a Complementary Pivot Algorithm.

[BibT_eX]

[DOI]

Math. Oper. Res., 2018

A Generalization of Birkhoff's Theorem for Distributive Lattices, with Applications to Robust Stable Matchings.

[BibT_eX]

[DOI]

CoRR, 2018

A Natural Generalization of Stable Matching Solved via New Insights into Ideal Cuts.

[BibT_eX]

[DOI]

CoRR, 2018

NC Algorithms for Perfect Matching and Maximum Flow in One-Crossing-Minor-Free Graphs.

[BibT_eX]

[DOI]

David Eppstein

CoRR, 2018

A New Class of Combinatorial Markets with Covering Constraints: Algorithms and Applications.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Nash Social Welfare for Indivisible Items under Separable, Piecewise-Linear Concave Utilities.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Cycles in Zero-Sum Differential Games and Biological Diversity.

[BibT_eX]

[DOI]

Proceedings of the 2018 ACM Conference on Economics and Computation, 2018

Finding Stable Matchings That Are Robust to Errors in the Input.

[BibT_eX]

[DOI]

Proceedings of the 26th Annual European Symposium on Algorithms, 2018

2017

Rock-Paper-Scissors, Differential Games and Biological Diversity.

[BibT_eX]

[DOI]

CoRR, 2017

Concave Flow on Small Depth Directed Networks.

[BibT_eX]

[DOI]

CoRR, 2017

A Performance-Based Scheme for Pricing Resources in the Cloud.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Convex Program Duality, Fisher Markets, and Nash Social Welfare.

[BibT_eX]

[DOI]

Proceedings of the 2017 ACM Conference on Economics and Computation, 2017

Mutation, Sexual Reproduction and Survival in Dynamic Environments.

[BibT_eX]

[DOI]

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

Opinion Dynamics in Networks: Convergence, Stability and Lack of Explosion.

[BibT_eX]

[DOI]

Ioannis Panageas

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Probabilistic estimation of overlap graphs for large sequence datasets.

[BibT_eX]

[DOI]

Rahul Nihalani

Sriram P. Chockalingam

Shaowei Zhu

Srinivas Aluru

Proceedings of the 2017 IEEE International Conference on Bioinformatics and Biomedicine, 2017

2016

Dichotomies in Equilibrium Computation and Membership of PLC Markets in FIXP.

[BibT_eX]

[DOI]

Theory Comput., 2016

New Convex Programs for Fisher's Market Model and its Generalizations.

[BibT_eX]

[DOI]

CoRR, 2016

2015

A Complementary Pivot Algorithm for Market Equilibrium under Separable, Piecewise-Linear Concave Utilities.

[BibT_eX]

[DOI]

SIAM J. Comput., 2015

The game of survival: Sexual evolution in dynamic environments.

[BibT_eX]

[DOI]

CoRR, 2015

A Market for Scheduling, with Applications to Cloud Computing.

[BibT_eX]

[DOI]

CoRR, 2015

Settling Some Open Problems on 2-Player Symmetric Nash Equilibria.

[BibT_eX]

[DOI]

Sadra Yazdanbod

Proceedings of the Algorithmic Game Theory - 8th International Symposium, 2015

ETR-Completeness for Decision Versions of Multi-player (Symmetric) Nash Equilibria.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Allocation of Divisible Goods Under Lexicographic Preferences.

[BibT_eX]

[DOI]

Leonard J. Schulman

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.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2014

Equilibrium Computation (Dagstuhl Seminar 14342).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2014

Leontief Exchange Markets Can Solve Multivariate Polynomial Equations, Yielding FIXP and ETR Hardness.

[BibT_eX]

[DOI]

CoRR, 2014

Learning Economic Parameters from Revealed Preferences.

[BibT_eX]

[DOI]

Proceedings of the Web and Internet Economics - 10th International Conference, 2014

Dichotomies in equilibrium computation, and complementary pivot algorithms for a new class of non-separable utility functions.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing, 2014

On Computability of Equilibria in Markets with Production.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

2013

Nonseparable, Concave Utilities Are Easy - in a Perfect Price Discrimination Market Model.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2013

Thrifty Algorithms for Multistage Robust Optimization.

[BibT_eX]

[DOI]

Anupam Gupta

Viswanath Nagarajan

Proceedings of the Integer Programming and Combinatorial Optimization, 2013

2012

Rational Convex Programs and Efficient Algorithms for 2-Player Nash and Nonsymmetric Bargaining Games.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2012

The notion of a rational convex program, and an algorithm for the arrow-debreu Nash bargaining game.

[BibT_eX]

[DOI]

J. ACM, 2012

An Improved Definition of Blossoms and a Simpler Proof of the MV Matching Algorithm

[BibT_eX]

[DOI]

CoRR, 2012

A complementary pivot algorithm for markets under separable, piecewise-linear concave utilities.

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Can the Theory of Algorithms Ratify the "Invisible Hand of the Market"?

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2012

2011

New geometry-inspired relaxations and algorithms for the metric Steiner tree problem.

[BibT_eX]

[DOI]

Math. Program., 2011

A Perfect Price Discrimination Market Model with Production, and a Rational Convex Program for It.

[BibT_eX]

[DOI]

Gagan Goel

Math. Oper. Res., 2011

Market equilibrium under separable, piecewise-linear, concave utilities.

[BibT_eX]

[DOI]

J. ACM, 2011

Modeling Tiered Pricing in the Internet Transit Market

[BibT_eX]

[DOI]

CoRR, 2011

A Market for Air Traffic Flow Management

[BibT_eX]

[DOI]

CoRR, 2011

How many tiers?: pricing in the internet transit market.

[BibT_eX]

[DOI]

Proceedings of the ACM SIGCOMM 2011 Conference on Applications, 2011

2010

Design is as Easy as Optimization.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2010

Rationality and Strongly Polynomial Solvability of Eisenberg--Gale Markets with Two Agents.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2010

Spending Constraint Utilities with Applications to the Adwords Market.

[BibT_eX]

[DOI]

Math. Oper. Res., 2010

Eisenberg-Gale markets: Algorithms and game-theoretic properties.

[BibT_eX]

[DOI]

Games Econ. Behav., 2010

Non-Separable, Quasiconcave Utilities are Easy -- in a Perfect Price Discrimination Market Model

[BibT_eX]

[DOI]

CoRR, 2010

Rational Convex Programs, Their Feasibility, and the Arrow-Debreu Nash Bargaining Game

[BibT_eX]

[DOI]

CoRR, 2010

Equilibrium Pricing of Digital Goods via a New Market Model

[BibT_eX]

[DOI]

CoRR, 2010

Non-separable, Quasiconcave Utilities are Easy - in a Perfect Price Discrimination Market Model (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Internet and Network Economics - 6th International Workshop, 2010

2-Player Nash and Nonsymmetric Bargaining Games: Algorithms and Structural Properties.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Game Theory - Third International Symposium, 2010

10171 Abstracts Collection - Equilibrium Computation.

[BibT_eX]

[DOI]

Proceedings of the Equilibrium Computation, 25.04. - 30.04.2010, 2010

2009

2-Player Nash and Nonsymmetric Bargaining via Flexible Budget Markets

[BibT_eX]

[DOI]

CoRR, 2009

2008

Equitable Cost Allocations via Primal--Dual-Type Algorithms.

[BibT_eX]

[DOI]

SIAM J. Comput., 2008

Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 2008

Market equilibrium via a primal-dual algorithm for a convex program.

[BibT_eX]

[DOI]

Christos H. Papadimitriou

Amin Saberi

J. ACM, 2008

Continuity Properties of Equilibria in Some Fisher and Arrow-Debreu Market Models.

[BibT_eX]

[DOI]

Lei Wang

Electron. Colloquium Comput. Complex., 2008

Solvency Games.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2008

Random Bichromatic Matchings.

[BibT_eX]

[DOI]

Algorithmica, 2008

Efficiency, Fairness and Competitiveness in Nash Bargaining Games.

[BibT_eX]

[DOI]

Proceedings of the Internet and Network Economics, 4th International Workshop, 2008

Nash Bargaining Via Flexible Budget Markets.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory, 2008

Fast monitoring of traffic subpopulations.

[BibT_eX]

[DOI]

Anirudh Ramachandran

Srinivasan Seetharaman

Nick Feamster

Proceedings of the 8th ACM SIGCOMM Internet Measurement Conference, 2008

MINT: a Market for INternet Transit.

[BibT_eX]

[DOI]

Proceedings of the 2008 ACM Conference on Emerging Network Experiment and Technology, 2008

2007

An auction-based market equilibrium algorithm for a production model.

[BibT_eX]

[DOI]

Sanjiv Kapoor

Theor. Comput. Sci., 2007

A primal-dual algorithm for computing Fisher equilibrium in the absence of gross substitutability property.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2007

AdWords and generalized online matching.

[BibT_eX]

[DOI]

J. ACM, 2007

Markets and the Primal-Dual Paradigm.

[BibT_eX]

[DOI]

Proceedings of the Internet and Network Economics, Third International Workshop, 2007

Continuity Properties of Equilibrium Prices and Allocations in Linear Fisher Markets.

[BibT_eX]

[DOI]

Nimrod Megiddo

Proceedings of the Internet and Network Economics, Third International Workshop, 2007

Eisenberg-Gale markets: algorithms and structural properties.

[BibT_eX]

[DOI]

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

2006

On the capacity of multiple unicast sessions in undirected graphs.

[BibT_eX]

[DOI]

Gideon Yuval

IEEE Trans. Inf. Theory, 2006

Posted price profit maximization for multicast by approximating fixed points.

[BibT_eX]

[DOI]

Scott Shenker

J. Algorithms, 2006

Eisenberg-Gale Markets: Rationality, Strongly Polynomial Solvability, and Competition Monotonicity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

New Results on Rationality and Strongly Polynomial Time Solvability in Eisenberg-Gale Markets.

[BibT_eX]

[DOI]

Proceedings of the Internet and Network Economics, Second International Workshop, 2006

On the Coding Advantage of Multiple Unicast Sessions in Undirected Graphs.

[BibT_eX]

[DOI]

Mohammad Taghi Hajiaghayi

Gideon Yuval

Proceedings of the 2006 IEEE Information Theory Workshop, 2006

Minimum Multicolored Subgraph Problem in Multiplex PCR Primer Set Selection and Population Haplotyping.

[BibT_eX]

[DOI]

Proceedings of the Computational Science, 2006

2005

Strategyproof cost-sharing mechanisms for set cover and facility location games.

[BibT_eX]

[DOI]

Milena Mihail

Decis. Support Syst., 2005

A Computationally Motivated Definition Of Parametric Estimation And Its Applications To The Gaussian Distribution.

[BibT_eX]

[DOI]

Leonard J. Schulman

Comb., 2005

A Simple Characterization for Truth-Revealing Single-Item Auctions.

[BibT_eX]

[DOI]

Proceedings of the Internet and Network Economics, First International Workshop, 2005

Price of Anarchy, Locality Gap, and a Network Service Provider Game.

[BibT_eX]

[DOI]

Proceedings of the Internet and Network Economics, First International Workshop, 2005

Market equilibria for homothetic, quasi-concave utilities and economies of scale in production.

[BibT_eX]

[DOI]

Yinyu Ye

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

On the capacity of multiple unicast sessions in undirected graphs.

[BibT_eX]

[DOI]

Proceedings of the 2005 IEEE International Symposium on Information Theory, 2005

AdWords and Generalized On-line Matching.

[BibT_eX]

[DOI]

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

2004

Multiway cuts in node weighted graphs.

[BibT_eX]

[DOI]

J. Algorithms, 2004

An Approximation Algorithm for the Fault Tolerant Metric Facility Location Problem.

[BibT_eX]

[DOI]

Algorithmica, 2004

Randomized truthful auctions of digital goods are randomizations over truthful auctions.

[BibT_eX]

[DOI]

Proceedings of the Proceedings 5th ACM Conference on Electronic Commerce (EC-2004), 2004

An Auction-Based Market Equilibrium Algorithm for the Separable Gross Substitutability Case.

[BibT_eX]

[DOI]

Rahul Garg

Sanjiv Kapoor

Proceedings of the Approximation, 2004

2003

Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP.

[BibT_eX]

[DOI]

J. ACM, 2003

A stochastic process on the hypercube with applications to peer-to-peer networks.

[BibT_eX]

[DOI]

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Profit-maximizing multicast pricing by approximating fixed points.

[BibT_eX]

[DOI]

Scott Shenker

Proceedings of the Proceedings 4th ACM Conference on Electronic Commerce (EC-2003), 2003

Extensions of the spending constraint-model: existence and uniqueness of equilibria (extended abstract).

[BibT_eX]

[DOI]

Proceedings of the Proceedings 4th ACM Conference on Electronic Commerce (EC-2003), 2003

An Improved Approximation Scheme for Computing Arrow-Debreu Prices for the Linear Case.

[BibT_eX]

[DOI]

Proceedings of the FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science, 2003

2002

A primal-dual schema based approximation algorithm for the element connectivity problem.

[BibT_eX]

[DOI]

J. Algorithms, 2002

Market Equilibrium via a Primal-Dual-Type Algorithm.

[BibT_eX]

[DOI]

Christos H. Papadimitriou

Amin Saberi

Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

2001

Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxation.

[BibT_eX]

[DOI]

J. ACM, 2001

Applications of approximation algorithms to cooperative games.

[BibT_eX]

[DOI]

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

A Greedy Facility Location Algorithm Analyzed Using Dual Fitting.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2001

A Graph Theoretic Approach to Software Watermarking.

[BibT_eX]

[DOI]

Ramarathnam Venkatesan

Saurabh Sinha

Proceedings of the Information Hiding, 4th International Workshop, 2001

Approximation algorithms.

[BibT_eX]

[DOI]

Springer, ISBN: 978-3-540-65367-7, 2001

2000

Recent results on approximating the Steiner tree problem and its generalizations.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2000

A new heuristic for rectilinear Steiner trees.

[BibT_eX]

[DOI]

Ion I. Mandoiu

Joseph L. Ganley

IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 2000

Primal-Dual Schema Based Approximation Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Theoretical Aspects of Computer Science, 2000

1999

Finding Separator Cuts in Planar Graphs within Twice the Optimal.

[BibT_eX]

[DOI]

SIAM J. Comput., 1999

Majorizing Estimators and the Approximation of #P-Complete Problems.

[BibT_eX]

[DOI]

Leonard J. Schulman

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

On the Bidirected Cut Relaxation for the Metric Steiner Tree Problem.

[BibT_eX]

[DOI]

Sridhar Rajagopalan

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Primal-Dual Approximation Algorithms for Metric Facility Location and k-Median Problems.

[BibT_eX]

[DOI]

Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

1998

The 'Art of Trellis Decoding' Is Computationally Hardi - For Large Fields.

[BibT_eX]

[DOI]

Ion I. Mandoiu

IEEE Trans. Inf. Theory, 1998

Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs.

[BibT_eX]

[DOI]

Sridhar Rajagopalan

SIAM J. Comput., 1998

The Steiner Tree Problem and Its Generalizations.

[BibT_eX]

[DOI]

Proceedings of the Approximation Algorithms for Combinatorial Optimization, 1998

1997

Primal-Dual Approximation Algorithms for Integral Flow and Multicut in Trees.

[BibT_eX]

[DOI]

Algorithmica, 1997

1996

An efficient algorithm for constructing minimal trellises for codes over finite abelian groups.

[BibT_eX]

[DOI]

B. Sundar Rajan

IEEE Trans. Inf. Theory, 1996

Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications.

[BibT_eX]

[DOI]

SIAM J. Comput., 1996

1995

Finding k Cuts within Twice the Optimal.

[BibT_eX]

[DOI]

SIAM J. Comput., 1995

A polyhedron with alls - t cuts as vertices, and adjacency of cuts.

[BibT_eX]

[DOI]

Math. Program., 1995

A Primal-Dual Approximation Algorithm for Generalized Steiner Network Problems.

[BibT_eX]

[DOI]

Comb., 1995

Primal-Dual Schema Based Approximation Algorithms (Abstract).

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, First Annual International Conference, 1995

1994

On-Line Algorithms for Weighted Bipartite Matching and Stable Marriages.

[BibT_eX]

[DOI]

Samir Khuller

Stephen G. Mitchell

Theor. Comput. Sci., 1994

Randomized Parallel Algorithms for Matroid Union and Intersection, With Applications to Arboresences and Edge-Disjoint Spanning Trees.

[BibT_eX]

[DOI]

H. Narayanan

SIAM J. Comput., 1994

A Theory of Alternating Paths and Blossoms for Proving Correctness of the O(sqrt{V E}) General Graph Maximum Matching Algorithm.

[BibT_eX]

[DOI]

Comb., 1994

Multiway Cuts in Directed and Node Weighted Graphs.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 21st International Colloquium, 1994

A Limited-Backtrack Greedy Schema for Approximation Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1994

1993

Efficient Sequential and Parallel Algorithms for Maximal Bipartite Sets.

[BibT_eX]

[DOI]

David Pearson

J. Algorithms, 1993

Improved Bounds for the Max-Flow Min-Multicut Ratio for Planar and K_r, r-Free Graphs.

[BibT_eX]

[DOI]

Éva Tardos

Inf. Process. Lett., 1993

A polyhedron with all s-t cuts as vertices, and adjacency of cuts.

[BibT_eX]

Proceedings of the 3rd Integer Programming and Combinatorial Optimization Conference, Erice, Italy, April 29, 1993

Primal-Dual Approximation Algorithms for Integral Flow and Multicut in Trees, with Applications to Matching and Set Cover.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 20nd International Colloquium, 1993

Primal-dual RNC approximation algorithms for (multi)-set (multi)-cover and covering integer programs

[BibT_eX]

[DOI]

Sridhar Rajagopalan

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.

[BibT_eX]

[DOI]

Samir Khuller

Stephen G. Mitchell

SIAM J. Comput., 1992

Suboptimal Cuts: Their Enumeration, Weight and Number (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 19th International Colloquium, 1992

1991

Planar Graph Coloring is not Self-Reducible, Assuming P != NP.

[BibT_eX]

[DOI]

Samir Khuller

Theor. Comput. Sci., 1991

Representing and Enumerating Edge Connectivity Cuts in RNC.

[BibT_eX]

[DOI]

Dalit Naor

Proceedings of the Algorithms and Data Structures, 1991

1990

An Optimal Algorithm for On-line Bipartite Matching

[BibT_eX]

[DOI]

Richard M. Karp

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.

[BibT_eX]

Proceedings of the 1st Integer Programming and Combinatorial Optimization Conference, 1990

A Fast Parallel Algorithm for Finding a Maximal Bipartite Set.

[BibT_eX]

[DOI]

David Pearson

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,3-Free Graphs and Related Problems

[BibT_eX]

[DOI]

Inf. Comput., February, 1989

The Two-Processor Scheduling Problem is in Random NC.

[BibT_eX]

[DOI]

SIAM J. Comput., 1989

Maximum Matchings in General Graphs Through Randomization.

[BibT_eX]

[DOI]

Michael O. Rabin

J. Algorithms, 1989

Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs.

[BibT_eX]

[DOI]

Discret. Appl. Math., 1989

1988

NC Algorithms for Computing the Number of Perfect Matchings in K3, 3-free Graphs and Related Problems.

[BibT_eX]

[DOI]

Proceedings of the SWAT 88, 1988

1987

Matching is as easy as matrix inversion.

[BibT_eX]

[DOI]

Ketan Mulmuley

Comb., 1987

Global Wire Routing in Two-Dimensional Arrays.

[BibT_eX]

[DOI]

Richard M. Karp

Frank Thomson Leighton

Algorithmica, 1987

1986

NP is as Easy as Detecting Unique Solutions.

[BibT_eX]

[DOI]

Leslie G. Valiant

Theor. Comput. Sci., 1986

Random Generation of Combinatorial Structures from a Uniform Distribution.

[BibT_eX]

[DOI]

Mark Jerrum

Leslie G. Valiant

Theor. Comput. Sci., 1986

Sampling a Population with a Semi-Random Source.

[BibT_eX]

[DOI]

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1986

1985

The Two-Processor Scheduling Problem is in R-NC

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Dexter Kozen

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1985

Random Polynomial Time Is Equal to Slightly-random Polynomial Time

[BibT_eX]

[DOI]

Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

1984

Efficient and Secure Pseudo-Random Number Generation (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

Efficient and Secure Pseudo-Random Number Generation.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology, 1984

1983

A Natural Encoding Scheme Proved Probabilistic Polynomial Complete.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1983

Trapdoor Pseudo-random Number Generators, with Applications to Protocol Design

[BibT_eX]

[DOI]

Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983

Global Wire Routing in Two-Dimensional Arrays (Extended Abstract)

[BibT_eX]

[DOI]

Richard M. Karp

Frank Thomson Leighton

Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983

Reducibility Among Protocols.

[BibT_eX]

Manuel Blum

Proceedings of the Advances in Cryptology, 1983

RSA Bits are 732+epsilon Secure.

[BibT_eX]

Proceedings of the Advances in Cryptology, 1983

1982

Scheduling open shops with parallel machines.

[BibT_eX]

[DOI]

Eugene L. Lawler

Michael George Luby

Oper. Res. Lett., 1982

NP-Completeness of Some Generalizations of the Maximum Matching Problem.

[BibT_eX]

[DOI]

Larry J. Stockmeyer

Inf. Process. Lett., 1982

1980

An O(sqrt(|v|) |E|) Algorithm for Finding Maximum Matching in General Graphs

[BibT_eX]

[DOI]

Silvio Micali