|
|||||
|
|
A new bound for the ratio between the 2-matching problem and its linear programming relaxation |
|
| Authors: | Sylvia Boyd Robert Carr |
| Affiliation: | Department of Computer Science, University of Ottawa, Ottawa, Canada? e-mail: sylvia@site.uottawa.ca, CA Sandia National Labs, Albuquerque, New Mexico, USA, e-mail: bobcarr@cs.sandia.gov, US |
| Abstract: | Consider the 2-matching problem defined on the complete graph, with edge costs which satisfy the triangle inequality. We prove that the value of a minimum cost 2-matching is bounded above by 4/3 times the value of its linear programming relaxation, the fractional 2-matching problem. This lends credibility to a long-standing conjecture that the optimal value for the traveling salesman problem is bounded above by 4/3 times the value of its linear programming relaxation, the subtour elimination problem. Received August 26, 1996 / Revised version received July 6, 1999? Published online September 15, 1999 |
| Keywords: | : 2-matching – traveling salesman problem – subtour elimination problem – polyhedral combinatorics Mathematics Subject Classification (1991): 05A99, 65K05 |
| 本文献已被 SpringerLink 等数据库收录！ | |