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

DOI10.1080/01966324.1993.10737362zbMath0808.90125OpenAlexW2070615415WikidataQ58282222 ScholiaQ58282222MaRDI QIDQ4305487

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

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

traveling salesmanweighted undirected graphminimum cost perfect 2-matchingmultiplier adjustment approach

Mathematics Subject Classification ID

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

Cites Work

• 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
• Accelerated branch exchange heuristics for symmetric traveling salesman problems
• The prize collecting traveling salesman problem
• Technical Note—Rounding Symmetric Traveling Salesman Problems with an Asymmetric Assignment Problem
• A Multiplier Adjustment Approach for the Set Partitioning Problem
• TSPLIB—A Traveling Salesman Problem Library
• A Staged Primal-Dual Algorithm for Finding a Minimum Cost Perfect Two-Matching in an Undirected Graph
• Paths, Trees, and Flowers
• Pathology of Traveling-Salesman Subtour-Elimination Algorithms

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