Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems

被引：2

作者：

Blaeser, Markus ^{[1
]}

Ram, L. Shankar ^{[2
]}

Sviridenko, Maxim

机构：

[1] Univ Saarland, D-66041 Saarbrucken, Germany

[2] ETH, Inst Theoret Informat, Zurich, Switzerland

来源：

OPERATIONS RESEARCH LETTERS | 2009年 / 37卷 / 03期

关键词：

Approximation algorithm; Traveling salesman problem; Cycle cover; Blossom inequalities;

D O I：

10.1016/j.orl.2009.01.011

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We consider an APX-hard variant (Delta-Max-ATSP) and an APX-hard relaxation (Max-3-DCC) of the classical traveling salesman problem. We present a 31/41-approximation algorithm for Delta-Max-ATSP and a 3/4-approximation algorithm for Max-3-DCC with polynomial running time. The results are obtained via a new way of applying techniques for computing undirected cycle covers to directed problems. (C) 2009 Elsevier B.V. All rights reserved.

引用

页码：176 / 180

页数：5

共 22 条

[1]

BARVINOK A., 2002, COMB OPT (SER), P585, DOI 10.1007/0-306-48213-4_12

[2]

Bläser M, 2004, J ALGORITHMS, V50, P23, DOI [10.1016/S0196-6774(03)00112-3, 10.1016/s0196-6774(03)00112-3]

[3]

Bläser M, 2002, LECT NOTES COMPUT SC, V2462, P40

[4]

Bläser M, 2003, SIAM PROC S, P638

[5]

BLASER M, 2005, APPROXIMATING MAXIMU

[6] Rotations of periodic strings and short superstrings [J].

Breslauer, D ;

Jiang, T ;

Jiang, ZG .

JOURNAL OF ALGORITHMS, 1997, 24 (02) :340-353

[7] Approximating capacitated routing and delivery problems [J].

Chalasani, P ;

Motwani, R .

SIAM JOURNAL ON COMPUTING, 1999, 28 (06) :2133-2149

[8]

Chen Z, 2005, Proceedings of the 2005 IEEE International Conference on Natural Language Processing and Knowledge Engineering (IEEE NLP-KE'05), P179

[9]

Christofides N., 1976, WORST CASE ANAL NEW

[10]

FEIGE U, 2007, P 10 INT WORKSH APPR

← 1 2 3 →