A new bound for the ratio between the 2-matching problem and its linear programming relaxation |
| |
| Authors: | Sylvia Boyd Robert Carr |
| |
| Institution: | 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 等数据库收录！ |
|
