×

zbMATH — the first resource for mathematics

On the worst-case performance of some algorithms for the asymmetric traveling salesman problem. (English) Zbl 0478.90070

MSC:
90C35 Programming involving graphs or networks
68Q25 Analysis of algorithms and problem complexity
65K05 Numerical mathematical programming methods
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Christofides, Mathematical Programming
[2] Clarke, Oper. Res. 12 pp 568– (1964)
[3] The complexity of theorem proving procedures. Proceedings 3rd Annual ACM Symposium on Theory of Computing (1971 ) 151–158.
[4] CornuĂ©jols, Math. Program. 14 pp 116– (1978)
[5] Edmonds, Math. Program. 1 pp 127– (1971)
[6] Optimum Branchings, Mathematics of the Decision Sciences Part 1, American Mathematical Society (1968 ) 346–364.
[7] , and , An analysis of approximations for finding a maximum weight hamiltonian circuit. Unpublished.
[8] Frieze, Oper. Res. Verfahren 32 pp 93– (1979)
[9] A generalisation of the greedy algorithm for independence systems. Unpublished.
[10] An extension of Christofides’ Heuristic to the k-person travelling salesman problem. Submitted to Discrete Appl. Math. · Zbl 0508.90085
[11] and , Computers and intractability: A guide to the theory of NP-completeness. W. H. Freeman City (1979). · Zbl 0411.68039
[12] Golden, A.I.I.E. Trans. 9 pp 204– (1977)
[13] , and , Worst-case analysis of greedy type algorithms for independence systems. Report No. 7781-OR, University of Bonn (1977).
[14] The efficacy of the greedy algorithm. Proceedings 7th S-E Conference on Combinatorics, Graph Theory and Computing (1976 ) 341–350.
[15] Karg, Manag. Sci. 10 pp 225– (1964)
[16] Reducibility among combinatorial problems. In Complexity of Computer Computations, and , Eds. Plenum, New York, (1973 ) 85–103.
[17] The fast approximate solution of hard combinatorial problems. Proceedings 6th South Eastern Conference on Combinatorics, Graph Theory and Computing, Utilitas Mathematical, Winnipeg (1975 ) 15–31.
[18] and , An analysis of the greedy heuristic for independence systems. In Algorithmic Aspects of Combinatorics, Ann. Discrete Math. 2, , and , Eds. North Holland, New York (1978 ) 65–74. · Zbl 0392.90058 · doi:10.1016/S0167-5060(08)70322-4
[19] Lin, Bell System Tech. J. 44 pp 2245– (1965) · Zbl 0136.14705 · doi:10.1002/j.1538-7305.1965.tb04146.x
[20] Lin, Oper. Res. 21 pp 498– (1973)
[21] Minina, Sov. Math. 16 pp 26– (1975)
[22] Nicholson, J. Inst. Math. Appl. 3 pp 362– (1967)
[23] Papadimitrou, Oper. Res. 26 pp 434– (1978)
[24] Reiter, J. Appl. Math. 13 pp 864– (1965)
[25] , and , Approximate algorithms for the travelling salesperson problem. Proceedings of 15th IEEE Symposium on Switching and Automata Theory (1974 ) 33–42.
[26] Sahni, J. ACM 23 pp 555– (1976)
[27] van der Cruyssen, J. Oper. Res. Soc. 29 pp 697– (1978)
[28] Webb, Oper. Res. Q. 22 pp 49– (1971)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.