Quality of solutions for perturbed combinatorial optimization problems

• Autorzy: Libura M.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

accuracy function; accuracy radius; combinatorial optimization; sensitivity analysis; stability function; stability radius

PL

kombinatoryka; optymalizacja; teoria zbioru

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2000
• Tom: Vol. 29, no 1
• Strony: 199--219
• Opis fizyczny: Bibliogr. 16 poz.,Rys., wykr.,

Twórcy

autor

Libura M.

• Systems Research Institute, Polish Academy of Sciences, Newelska 6, Ol-447 Warszawa, Poland,