The primal-dual method for approximation algorithms and its application to network design problems

A note on two problems in connexion with graphs

1959 • 22,492 citations

The Hungarian method for the assignment problem

1955 • 11,128 citations

Combinatorial Optimization: Algorithms and Complexity.

1984 • 6,247 citations

On the shortest spanning subtree of a graph and the traveling salesman problem

1956 • 4,806 citations

Geometric Algorithms and Combinatorial Optimization

1988 • 3,622 citations

A Greedy Heuristic for the Set-Covering Problem

1979 • 2,542 citations

Handbooks in operations research and management science

1989 • 2,362 citations

Maximal Flow Through a Network

2009 • 1,942 citations

Maximum matching and a polyhedron with 0,1-vertices

1965 • 1,719 citations

Efficiency of a Good But Not Linear Set Union Algorithm

1975 • 1,348 citations

On the ratio of optimal integral and fractional covers

1975 • 1,124 citations

Randomized rounding: A technique for provably good algorithms and algorithmic proofs

1987 • 1,025 citations

Matching, Euler tours and the Chinese postman

1973 • 979 citations

Multi-Terminal Network Flows

1961 • 959 citations

A Dual-Based Procedure for Uncapacitated Facility Location

1978 • 922 citations

Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms

1974 • 910 citations

A General Approximation Technique for Constrained Forest Problems

1995 • 834 citations

Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms

1977 • 807 citations

Steiner problem in networks: a survey

1987 • 586 citations

The prize collecting traveling salesman problem

1989 • 547 citations

Approximation Algorithms for the Set Covering and Vertex Cover Problems

1982 • 496 citations

1. A Certain Zero-sum Two-person Game Equivalent to the Optimal Assignment Problem

1953 • 480 citations

A linear-time approximation algorithm for the weighted vertex cover problem

1981 • 440 citations

When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks

1995 • 417 citations

Data structures for weighted matching and nearest common ancestors with linking

1990 • 417 citations

Design of Survivable Networks

1992 • 390 citations

A dual ascent approach for steiner tree problems on a directed graph

1984 • 365 citations

An 11/6-approximation algorithm for the network steiner problem

1993 • 342 citations

The minimum latency problem

1994 • 319 citations

Faster scaling algorithms for general graph matching problems

1991 • 311 citations

A note on the prize collecting traveling salesman problem

1993 • 277 citations

A Dual-Ascent Procedure for Large-Scale Uncapacitated Network Design

1989 • 257 citations

Location-Routing Problems

1987 • 250 citations

Heuristic analysis, linear programming and branch and bound

1980 • 229 citations

Matching, a well solved class of integer linear programs

1970 • 216 citations

Improved approximation algorithms for network design problems

1994 • 204 citations

878-approximation Algorithms for MAX CUT and MAX 2SAT

1994 • 181 citations

Finding the Shortest Route between Two Points in a Network

1966 • 160 citations

Hamiltonian location problems

1983 • 103 citations

7* A Primal-Dual Algorithm for Linear Programs

1957 • 102 citations

On a Greedy Heuristic for Complete Matching

1981 • 95 citations

When trees collide

1991 • 88 citations

An approximation algorithm for minimum-cost vertex-connectivity problems

1997 • 85 citations

Approximate max-flow min-(multi)cut theorems and their applications

1993 • 82 citations

A Constant-Factor Approximation Algorithm for thek-MST Problem

1999 • 78 citations

An improved approximation ratio for the minimum latency problem

1996 • 72 citations

Primal-dual approximation algorithms for feedback problems in planar graphs

1996 • 69 citations

Improved approximation guarantees for minimum-weight k-trees and prize-collecting salesmen

1995 • 62 citations

Primal-dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover

1993 • 55 citations

When Cycles Collapse: A General Approximation Technique for Constrained Two-Connectivity Problems

1992 • 48 citations

The point-to-point delivery and connection problems: complexity and algorithms

1992 • 37 citations

Heuristics for weighted perfect matching

1980 • 37 citations

A greedy heuristic for a minimum-weight forest problem

1993 • 34 citations

Formulations and algorithms for network design problems with connectivity requirements

1995 • 28 citations

Approximating minimum-cost graph problems with spanning tree edges

1994 • 22 citations

New primal and dual matching heuristics

1995 • 22 citations

Heuristic matching for graphs satisfying the triangle inequality

1984 • 18 citations

A commercial application of survivable network design: ITP/INPLANS CCS network topology analyzer

1996 • 16 citations

A data structure for bicategories, with application to speeding up an approximation algorithm

1994 • 16 citations

On the design of approximation algorithms for a class of graph problems

1993 • 16 citations

Computational Experience with an Approximation Algorithm on Large-Scale Euclidean Matching Instances

1996 • 15 citations

A scaling technique for better network design

1994 • 9 citations