A Fast Lower Bound for the Minimum Cost Perfect 2-Matching Linear Program

DOI10.1080/01966324.1993.10737362MaRDI QIDQ4305487zbMATH OpenOpenAlexWikidataFDO

Authors Charles E. Noon, G.-M. You, Thomas Justin Chan

Publication date 13 September 1994

Published in American Journal of Mathematical and Management Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/01966324.1993.10737362

zbMATH Keywords

minimum cost perfect 2-matchingmultiplier adjustment approachtraveling salesmanweighted undirected graph

Mathematics Subject Classification ID

Linear programming (90C05) Programming involving graphs or networks (90C35)

Recommendations

• A new bound for the ratio between the 2-matching problem and its linear programming relaxation
• A Staged Primal-Dual Algorithm for Finding a Minimum Cost Perfect Two-Matching in an Undirected Graph
• A cutting plane algorithm for minimum perfect 2-matchings
• New primal and dual matching heuristics

Cites work

• A Multiplier Adjustment Approach for the Set Partitioning Problem
• A Staged Primal-Dual Algorithm for Finding a Minimum Cost Perfect Two-Matching in an Undirected Graph
• Accelerated branch exchange heuristics for symmetric traveling salesman problems
• An improved assignment lower bound for the Euclidean traveling salesman problem
• New lower bounds for the symmetric travelling salesman problem
• On the symmetric travelling salesman problem I: Inequalities
• Optimal Solution of Set Covering/Partitioning Problems Using Dual Heuristics
• Pathology of Traveling-Salesman Subtour-Elimination Algorithms
• Paths, Trees, and Flowers
• Technical Note—Rounding Symmetric Traveling Salesman Problems with an Asymmetric Assignment Problem
• The prize collecting traveling salesman problem
• TSPLIB—A Traveling Salesman Problem Library

Cited in

(4)

• Minimum cost perfect matching with delays for two sources
• A cutting plane algorithm for minimum perfect 2-matchings
• A new bound for the ratio between the 2-matching problem and its linear programming relaxation
• A Staged Primal-Dual Algorithm for Finding a Minimum Cost Perfect Two-Matching in an Undirected Graph

This page was built for publication: A Fast Lower Bound for the Minimum Cost Perfect 2-Matching Linear Program

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4305487)