Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Fundamenta Informaticae

1 2011

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: reoptimization

Sortuj według:

Ogranicz wyniki do:

On the Hardness of Reoptimization with Multiple Given Solutions

Böckenhauer H. J., Hromkovič J., Sprock A.

Fundamenta Informaticae

2011

Vol. 110, nr 1-4

59-76

In reoptimization, we consider the following scenario: Given an instance of a hard optimization problem together with an optimal solution for it, we want to solve a locally modified instance of the problem. It has recently been shown for several hard optimization problems that their corresponding reoptimization variants remain NP-hard or even hard to approximate whereas they often admit improved approximation ratios. In this paper, we investigate a generalization of the reoptimization concept where we are given not only one optimal solution but multiple optimal solutions for an instance. We prove, for some variants of the Steiner tree problem and the traveling salesman problem, that the known reoptimization hardness results carry over to this generalized setting. Moreover, we consider the performance of local search strategies on reoptimization problems. We show that local search does notwork for solving TSP reoptimization, even in the presence ofmultiple solutions.