Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6895152 | European Journal of Operational Research | 2018 | 22 Pages |
Abstract
We prove these bounds by providing local search algorithms that, in polynomial time, find 2-matchings with few components in the support of the solution. We show that the run times of our algorithms cannot be considerably improved under standard complexity-theoretic assumptions: we show that finding improved TSP solutions via local search is intractable for edge change parameterized by the size of the neighborhoods even for instances with distances one and two; this strengthens a result of Dániel Marx.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Matthias Mnich, Tobias Mömke,