Minmax Regret Minimum Selecting Items
In this chapter we discuss the Minmax Regret Minimum Selecting Items problem. We are given a set of elements, called items, E = {e1,...,e n } with interval weights and we wish to choose a subset of exactly p items that minimizes the maximal regret. Thus t
- PDF / 471,715 Bytes
- 10 Pages / 430 x 660 pts Page_size
- 64 Downloads / 208 Views
In this chapter we discuss the Minmax Regret Minimum Selecting Items problem. We are given a set of elements, called items, E = {e1 , . . . , en } with interval weights and we wish to choose a subset of exactly p items that minimizes the maximal regret. Thus the set of feasible solutions in this problem is the following: Φ = {X ⊆ E : |X| = p}, where p is a fixed integer such that 1 ≤ p ≤ n. The problem can also be viewed as a special case of 0-1 Knapsack in which the capacities of all items are equal to 1. The optimal solution to the deterministic Minimum Selecting Items problem can be obtained by selecting p items of the smallest weights. This can be done in O(n) time by first selecting p-th smallest weighted item f and by selecting then p − 1 items of the weight less than or equal to the weight of f . It turns out that Minmax Regret Minimum Selecting Items is the only polynomially solvable minmax regret combinatorial optimization problem considered in this monograph. In Section 5.2 we give an algorithm with running time O(n min{p, n − p}) for this problem, which is due to Conde [37]. In Section 5.1 we show that all possibly and necessarily optimal items can be detected very efficiently in O(n) time. Hence for large problems it may be advantageous to perform the preprocessing, described in Section 2.2, before applying the exact algorithm. Since all feasible solutions in the problem have the same cardinality, all results presented in this chapter can also be applied to the Minmax Regret Maximum Selecting Items problem. It is enough to use the transformation shown in the proof of Theorem 1.5.
5.1 Evaluation of Optimality In this section we use the fact, that the deterministic Minimum Selecting Items problem has a matroidal structure. To see this, consider system (E, I), where E is a given set of items and I is the set of subsets of E, whose cardinalities are less than or equal to p, that is I = {X ⊆ E : |X| ≤ p}. It is easy to A. Kasperski: Discrete Optimization with Interval Data, STUDFUZZ 228, pp. 51–60, 2008. c Springer-Verlag Berlin Heidelberg 2008 springerlink.com
52
Minmax Regret Minimum Selecting Items
verify that system (E, I) is a matroid and in literature it is called a uniform matroid. The bases of this matriod are those subsets in I whose cardinalities are exactly p. Hence the set of feasible solutions Φ consists of all bases of a uniform matroid. The greedy algorithm applied to the problem simply outputs p items of the smallest weights. If the item weights are specified as intervals, then we can apply the results from Section 2.2.3 to detect all the possibly and necessarily optimal items. In this section we show that this can be done in linear time O(n). 5.1.1
Possibly Optimal Items
The following proposition characterizes a possibly optimal item: + . Proposition 5.1. Let f be the p-th smallest weighted item under scenario SE Then e ∈ E is possibly optimal if and only if we ≤ wf .
Proof. (⇒) Suppose, by contradiction, that e is possibly optimal and w e > w f . So, there are at least p items whose we
Data Loading...
