Greedy-type-resistance of combinatorial problems

Greedy-type-resistance of combinatorial problems

0.00 Avg rating0 Votes
Article ID: iaor20071401
Country: Netherlands
Volume: 3
Issue: 4
Start Page Number: 288
End Page Number: 298
Publication Date: Dec 2006
Journal: Discrete Optimization
Authors: ,
Keywords: heuristics
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.