Efficiently solvable special cases of hard combinatorial optimization problems

Efficiently solvable special cases of hard combinatorial optimization problems

0.00 Avg rating0 Votes
Article ID: iaor1999882
Country: Netherlands
Volume: 79
Issue: 1/3
Start Page Number: 55
End Page Number: 69
Publication Date: Oct 1997
Journal: Mathematical Programming
Authors:
Keywords: programming: assignment, programming: travelling salesman
Abstract:

We survey some recent advances in the field of polynomially solvable special cases of hard combinatorial optimization problems like the travelling salesman problem, quadratic assignment problems and Steiner tree problems. Such special cases can be found by considering special cost structures, the geometry of the problem, the special topology of the underlying graph structure or by analyzing special algorithms. In particular we stress the importance of recognition algorithms. We comment on open problems in this area and outline some lines for future research in this field.

Reviews

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