Greedy-Type-Resistance of Combinatorial Problems.pdf.pdf' (181.29 kB)
Download file

Greedy-Type-Resistance of Combinatorial Problems

Download (181.29 kB)
journal contribution
posted on 01.07.1989, 00:00 authored by Gareth Bendall, Francois MargotFrancois Margot
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.

History

Date

01/07/1989

Usage metrics

Exports