Min-max and min-max (relative) regret approaches to representatives selection problem - Archive ouverte HAL Access content directly
Journal Articles 4OR: A Quarterly Journal of Operations Research Year : 2012

Min-max and min-max (relative) regret approaches to representatives selection problem

(1, 2) , (1, 2)
1
2

Abstract

The following optimization problem is studied. There are several sets of integer positive numbers whose values are uncertain. The problem is to select one representative of each set such that the sum of the selected numbers is minimum. The uncertainty is modeled by discrete and interval scenarios, and the min-max and min-max (relative) regret approaches are used for making a selection decision. The arising min-max, min-max regret and min-max relative regret optimization problems are shown to be polynomially solvable for interval scenarios. For discrete scenarios, they are proved to be NP-hard in the strong sense if the number of scenarios is part of the input. If it is part of the problem type, then they are NP-hard in the ordinary sense, pseudo-polynomially solvable by a dynamic programming algorithm and possess an FPTAS. This study is motivated by the problem of selecting tools of minimum total cost in the design of a production line.
Not file

Dates and versions

emse-00693479 , version 1 (02-05-2012)

Identifiers

Cite

Alexandre Dolgui, Sergey Kovalev. Min-max and min-max (relative) regret approaches to representatives selection problem. 4OR: A Quarterly Journal of Operations Research, 2012, Volume 10 (Issue 2), pp 181-192. ⟨10.1007/s10288-012-0202-3⟩. ⟨emse-00693479⟩
63 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More