×

Greedy-type resistance of combinatorial problems. (English) Zbl 1112.90065

Summary: This paper gives a sufficient condition for a combinatorial problem to be greedy-type resistant, i.e. such that, on some instances of the problem, any greedy-type algorithm will output the unique worst possible solution. The condition is used to show that the Equipartition, the \(k\)-clique, the asymmetric traveling salesman, the Hamiltonian path, the min-max matching, and the assignment problems are all greedy-type resistant.

MSC:

90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ausiello, G.; Crescenzi, P.; Gambosi, G.; Kann, V.; Marchetti-Spaccamela, A.; Protasi, M., Complexity and Approximation (1999), Springer: Springer Berlin · Zbl 0937.68002
[2] Bang-Jensen, J.; Gutin, G.; Yeo, A., When the greedy algorithm fails, Discrete Optimization, 1, 2, 121-127 (2004) · Zbl 1087.90059
[3] G. Bendall, Domination analysis beyond the Traveling Salesman Problem, Ph.D. Thesis, Department of Mathematics, University of Kentucky, 2004; G. Bendall, Domination analysis beyond the Traveling Salesman Problem, Ph.D. Thesis, Department of Mathematics, University of Kentucky, 2004
[4] Garey, M.; Johnson, D., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman and Company: W.H. Freeman and Company New York · Zbl 0411.68039
[5] Glover, F.; Punnen, A. P., The traveling salesman problem: New solvable cases and linkages with the development of approximation algorithms, Journal of the Operational Research Society, 48, 502-510 (1997) · Zbl 0882.90124
[6] Gutin, G.; Punnen, A. P., The Traveling Salesman Problem and Its Variations (2002), Kluwer Academic Publishers: Kluwer Academic Publishers Boston · Zbl 0996.00026
[7] Gutin, G.; Vaishtein, A.; Yeo, A., Domination analysis of combinatorial optimization problems, Discrete Applied Mathematics, 129, 2-3, 513-520 (2003) · Zbl 1052.90062
[8] G. Gutin, A. Vainshtein, A. Yeo, When greedy-type algorithms fail, unpublished manuscript, 2002; G. Gutin, A. Vainshtein, A. Yeo, When greedy-type algorithms fail, unpublished manuscript, 2002
[9] Gutin, G.; Yeo, A., Anti-matroids, Operations Research Letters, 30, 2, 97-99 (2002) · Zbl 1030.90107
[10] Gutin, G.; Yeo, A.; Zverovich, A., Traveling salesman should not be greedy: Domination analysis of greedy-type heuristics for the TSP, Discrete Applied Mathematics, 117, 1-3, 81-86 (2002) · Zbl 1004.68121
[11] Korte, B.; Vygen, J., Combinatorial Optimization, Theory and Algorithms (2002), Springer · Zbl 1002.90046
[12] Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G.; Shmoys, D. B., The Traveling Salesman Problem (1985), Wiley: Wiley New York · Zbl 0563.90075
[13] J. Oxley, Matroid Theory, Oxford University Press, Oxford; J. Oxley, Matroid Theory, Oxford University Press, Oxford · Zbl 1115.05001
[14] Punnen, A.; Margot, F.; Kabadi, S., TSP heuristics: Domination analysis and complexity, Algorithmica, 35, 2, 111-127 (2003) · Zbl 1060.90075
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.