- Tytuł:
- Quality of solutions for perturbed combinatorial optimization problems
- Autorzy:
- Libura, M.
- Powiązania:
- https://bibliotekanauki.pl/articles/205967.pdf
- Data publikacji:
- 2000
- Wydawca:
- Polska Akademia Nauk. Instytut Badań Systemowych PAN
- Tematy:
-
kombinatoryka
optymalizacja
teoria zbioru
accuracy function
accuracy radius
combinatorial optimization
sensitivity analysis
stability function
stability radius - Opis:
- We consider a general combinatorial optimization problem in which the set of feasible solutions is defined as a given and fixed family of subsets for some finite ground set. To any element of the ground set the so-called weight is associated. The problem consists in finding a feasible subset for which the sum of weights of its elements is the minimum. When the weights of elements vary or are estimated with some accuracy, then the solution of the problem obtained for some initial weights may appear non-optimal. In this paper we consider the quality of a given solution in the case of weights perturbation or inaccuracy. Namely, we study the relative error of a given solution as a function of particular weights perturbation. We also calculate the maximum perturbation or estimation errors of weights which preserve the optimality of a given solution of the problem.
- Źródło:
-
Control and Cybernetics; 2000, 29, 1; 199-219
0324-8569 - Pojawia się w:
- Control and Cybernetics
- Dostawca treści:
- Biblioteka Nauki
Artykuł