The Travelling Salesman Problem on Permuted Monge Matrices

被引：2

作者：

Burkard R.E. ^{[1
]}

Deǐneko V.G. ^{[1
,2
]}

Woeginger G.J. ^{[1
]}

机构：

[1] TU Graz, Institut für Mathematik B, A-8010 Graz

[2] University of Warwick, Warwick Business School

来源：

Journal of Combinatorial Optimization | 1998年 / 2卷 / 4期

关键词：

Combinatorial optimization; Computational complexity; Subtour patching; Travelling salesman problem;

D O I：

10.1023/A:1009768317347

中图分类号：

学科分类号：

摘要：

We consider traveling salesman problems (TSPs) with a permuted Monge matrix as cost matrix where the associated patching graph has a specially simple structure: a multistar, a multitree or a planar graph. In the case of multistars, we give a complete, concise and simplified presentation of Gaikov's theory. These results are then used for designing an O (m3 + mn) algorithm in the case of multitrees, where n is the number of cities and m is the number of subtours in an optimal assignment. Moreover we show that for planar patching graphs, the problem of finding an optimal subtour patching remains NP-complete.

引用

页码：333 / 350

页数：17

共 17 条

[1]

Burkard R.E., Deineko V.G., Polynomially solvable cases of the traveling salesman problem and a new exponential neighborhood, Computing, 54, pp. 191-211, (1995)

[2]

Burkard R.E., Deineko V.G., Van Dal R., Van Der Veen J.A.A., Woeginger G.J., Well-solvable special cases of the TSP: A survey, SIAM Reviews, 40, pp. 496-546, (1998)

[3]

Burkard R.E., Klinz B., Rudolf R., Perspectives of Monge properties in optimization, Discrete Applied Mathematics, 70, pp. 95-161, (1996)

[4]

Burdyuk V.Ya., Trofimov V.N., Generalizations of the results of Gilmore and Gomory on the solution of the travelling salesman problem, Izv. Akad. Nauk SASS, Tech. Kibernet., 3, pp. 16-22, (1976)

[5]

Engineering Cybernetics, 14, pp. 12-18, (1976)

[6]

Deineko V.G., Applying dynamic programming to solving a speical traveling salesman problem, Issledovanie Operaziy i ASU Kiev, 16, pp. 47-50, (1979)

[7]

Deineko V.G., Filonenko V.L., On the reconstruction of specially structured matrices, Aktualnye Problemy EVMI Programmirovanie, pp. 43-45, (1979)

[8]

Gabov H.N., Data structures for weighted matching and nearest common ancestors with linking, Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 434-443

[9]

Gaikov N.E., On the minimization of a linear form on cycles, Vestsi Akad. Navuk BSSR Ser. Fiz.-Mat. Navuk, 4, (1980)

[10]

Gilmore P.C., Gomory R.E., Sequencing a one state variable machine: A solvable case of the travelling salesman problem, Oper. Research, 12, pp. 655-679, (1964)

← 1 2 →