On the accuracy function and the accuracy radius for combinatorial optymization problems

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

Abstrakty

EN

We consider the combinatorial optimization problem in the following form: min{EEF c(e) : F E F} -( formula), where for some finite set E, c = (c(e), e E E) E R+ (formula) is a vector of weights of elements of E, and F C 2E (formula) is a given family of feasible subsets. We assume that the set F is fixed, but the weights of elements belonging to some given subset X C E may vary. The accuracy function describes the quality of a given solution of the problem as a function of weights perturbations. Namely, for a given optimal solution Fo obtained for an initial vector of weights ca E R+, the value a( Fo, X, b) of this function for some specified subset X C E and a value b, where 0 < 1, is equal to the maximum relative error of the solution Fo for arbitrary simultaneous perturbations of weights of elements, satisfying the following conditions: Ic(e) - co(e)I

Słowa kluczowe

EN

combinatorial optimization; sensitivity analysis

• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2000
• Tom: Vol. 48, nr 2
• Strony: 231-245
• Opis fizyczny: Bibliogr. 12 poz., 4 rys.

Twórcy

autor

Libura, M.

• Systems Research Institute, Polish Academy of Sciences, Newelska 6, 01-447, Warsaw, Poland,