Algorithmica DOI 10.1007/s00453-016-0174-3
Primal–Dual Algorithms for Precedence Constrained Covering Problems S. Thomas McCormick1 · Britta Peis2 · José Verschae3 · Andreas Wierz2
Received: 30 March 2015 / Accepted: 6 June 2016 © Springer Science+Business Media New York 2016
Abstract A covering problem is an integer linear program of type min{c T x | m n Ax ≥ D, 0 ≤ x ≤ d, x ∈ Z} where A ∈ Zm×n + , D ∈ Z+ , and c, d ∈ Z+ . In this paper, we study covering problems with additional precedence constraints {xi ≤ x j ∀ j i ∈ P}, where P = ([n], ) is some arbitrary, but fixed partial order on the items represented by the column-indices of A. Such precedence constrained covering problems (PCCPs) are of high theoretical and practical importance even in the special case of the precedence constrained knapsack problem, that is, where m = 1 and d ≡ 1. Our main result is a strongly-polynomial primal–dual approximation algorithm for PCCP with d ≡ 1. Our approach generalizes the well-known knapsack cover inequalities to obtain an IP formulation which renders any explicit precedence constraints redundant. The approximation ratio of this algorithm is upper bounded by the width of P, that is, by the size of a maximum antichain in P. Interestingly, this bound is independent of the number of constraints. We are not aware of any other results on approximation algorithms for PCCP on arbitrary posets P. For the general case with
B
Andreas Wierz
[email protected] S. Thomas McCormick
[email protected] Britta Peis
[email protected] José Verschae
[email protected]
1
Sauder School of Business, UBC, Vancouver, Canada
2
RWTH Aachen University, Aachen, Germany
3
Pontificia Universidad Católica de Chile, Santiago, Chile
123
Algorithmica
d ≡ 1, we present pseudo-polynomial algorithms. Finally, we show that the problem does not admit a PTAS under standard complexity assumptions. Keywords Approximation algorithms · Precedence constraints · Knapsack problem · Capacitated covering
1 Introduction We consider integer linear programs of type min{c T x | Ax ≥ D, 0 ≤ x ≤ d, x ∈ Z}, is a non-negative integral matrix with entries u ik , D ∈ Zm where A ∈ Zm×n + + is a demand n k vector with entries D , and c, d ∈ Z+ . Such integer linear programs are usually called covering problems. The name becomes more evident if we interpret a solution vector x ∈ Zn+ as choice of multiplicities xi of items of type i ∈ N = [n] that needs to satisfy a set of m covering constraints i∈N u ik xi ≥ D k (k ∈ K = [m]). Each item i is equipped with a per-unit weight u ik w.r.t. covering-constraint k, a per-unit cost ci , and an upper bound di on the multiplicity of item i. For example, the special case of just one covering constraint (m = 1), and upper The bounds di = 1 on the multiplicities models the classical knapsack problem. knapsack problem is more familiar in the packing variant max{c T x | i∈N u i xi ≤ B, x ∈ {0, 1}n } which asks for a subset of items in N of maximum c-value that fits into a knapsack of capacity B. This problem can equivalently be formulated in the covering variant min{c T x | i∈N u i xi ≥ D, x ∈ {0, 1}n }, where D = i∈N u i − B, which aims at minimizing the value of items that are not packed into the knapsack. Although the packing and covering variants are equivalent if we look for the optimal solution, they are not when we approximate them. The knapsack problem belongs to one of the most studied problems in combinatorial optimization (see, e.g. [11]), and is well-known to be weakly NP-hard [11]. Nevertheless, it is computationally tractable as there exist e.g., an FPTAS [9] and a primal–dual 2-approximation [3,11] for the problem. However, in various settings of knapsack-type problems, and also in more general covering problems, the items to be chosen need to obey certain precedence relations in the following sense: the chosen multiplicity of item i may not exceed the chosen multiplicity of item j, whenever j ≺ i in some predefined partially ordered set (poset) P = (N , ). That is, we consider the precedence constrained covering problem (PCCP) min c T x | Ax ≥ D, 0 ≤ x ≤ d, x ∈ Z, xi ≤ x j ∀ j i ∈ P w.r.t. an arbitrary, but fixed poset P = (N , ). Due to its importance both from a theoretical and practical perspective, we will put special emphasize on the case where m = 1 and d ≡ 1, that is, the precedence constrained knapsack problem (PCKP). For the sake of simplicity, we use D as a scalar whenever m = 1. PCKP and its generalizations are not only very interesting on their own right. Besides, they are also used as a subroutine in algorithms for max clique and scheduling with precedence constraints (see, e.g., [21]).
123
Algorithmica
Evidently, the complexity of precedence constrained covering problems, already in PCKP, depends strongly on the structure of the underlying poset P. For example, if P is an antichain, that is, if there is no precedence relation between any two items, then PCKP reduces to the classical and tractable knapsack problem. In the other extreme, where P is a chain, that is, where all items are comparable, the problem is trivially solvable: the optimal solution consists of the smallest initial subchain whose weight covers D. Known results Due to the two extreme examples of PCKP described above, the reader could be tempted to think that PCKP is rather easy in the presence of arbitrary partial orders as well—but this is not the case. The packing variant of PCKP restricted to u i = ci for all elements i ∈ N with a bipartite partial order was already proven to be strongly NP-complete by Johnson and Niemi [10]. Hajiaghayi et al. [8] show that the packing version of PCKP is inapproxδ
3 +
imable within a factor of 2log (n) , for some δ > 0, unless 3SAT ∈ DTIME(2n 4 ) for all > 0. The result is based on the hardness result for bipartite clique by Feige and Kogan [6]. Using instead the result of Khot [13], we obtain that for any > 0, if SAT does not have a probabilistic algorithm that runs in 2n , there is no polynomial time (possibly randomized) algorithm for the packing variant of PCKP that achieves
an approximation ratio n for some that depends on . Special cases of the packing variant of PCKP can be solved in polynomial time. Johnson and Niemi [10] provide an FPTAS for instances where P is a tree. Kolliopoulos and Steiner [14] show that there is an FPTAS if P is 2-dimensional and provide an optimal algorithm if P is bipartite, its complement is chordal bipartite and all items either have zero weight or zero capacity. Pritchard and Chakrabarty [18] provide an O(α 2 )-approximation algorithm for the multidimensional precedence constrained packing problem with dilation α, which is defined as the maximal number of constraints any variable appears in. The polyhedral structure of PCKP was investigated by a wide range of papers, including work of Boyd [2], Park and Park [17], Van de Leensel et al. [20] and Boland et al. [1]. The work includes cutting planes as well as preprocessing steps that can be used to reduce the problem size. Covering problems (CPs) without precedence constraints and with at most p nonzero entries per row are NP-hard to approximate within a factor of p − 1 − and p − under the unique games conjecture, respectively, due to Dinur et al. [5] and Khot and Regev [12]. This bound was also achieved by a primal–dual algorithm due to Fujito and Yabuta [7] and a greedy algorithm due to Koufogiannakis and Young [16]. The special case of CP with dilation α was proven to be inapproximable within any factor below Θ(ln(α)) [19]. This bound was also achieved by an iterative rounding algorithm due to Kolliopoulos and Young [15]. For more information on covering problems without precedence constraints, we refer the reader to Pritchard and Chakrabarty [18]. Since PCCP contains CP as a special case, it inherits its lower bounds. To the best of our knowledge, there are no approximation algorithms known for PCCP under the presence of arbitrary precedence constraints, yet.
123
Algorithmica
Our contribution and outline of the paper In Sect. 2, we extend the primal–dual 2approximation algorithm of Carnes and Shmoys [3] for the knapsack problem without precedence constraints (KP) towards general bounds d on the multiplicities. As in [3], the algorithm is based on knapsack cover inequalities to bound the integrality gap. Though this is probably not too exciting from a theoretical point of view, it helps to understand the more involved algorithmic and analytic techniques in the subsequent sections. In Sect. 3, we investigate the knapsack problem with precedence constraints (PCKP). We observe that adding precedence constraints to the knapsack covering inequalities may lead to an unbounded integrality gap. However, we were able to incorporate the poset structure into the knapsack covering inequalities by shifting weights along the poset. This way, a primal–dual approach led us to a w(P)approximate solution, where w(P) denotes the width of poset P, that is, the maximal size of an antichain in P. We give an example showing that this result is tight in the sense that our algorithm may in fact output a solution with performance ratio w(P). Thereafter, in Sect. 4, we show that the algorithm can be generalized to deal with more than one covering constraint, that is, to the precedence constrained covering problem (PCCP), provided that d ≡ 1. Surprisingly, the approximation factor w(P) remains the same, that is, the factor is independent of the number of constraints. As a byproduct we yield a p-approximation for the covering problem without precedence constraints, where p denotes the maximal number of non-zero entries in any row of matrix A, which was already discussed by Fujito and Yabuta [7] and Koufogiannakis and Young [16]. For PCCP with general d, we provide a construction that allows to solve the problem within an approximation factor of w(P)Δ in pseudo-polynomial time, where Δ = maxi di is the maximum item multiplicity. Finally, in Sect. 5, we provide an inapproximability result in showing that there is no PTAS for PCKP unless N P ⊆ ∩>0 BPTIME(2n ).
1.1 Preliminaries A partially ordered set is a tuple P = (N , ) consisting of a set of elements N and an order relation for pairs of elements. In our context, elements are also called items. Two elements i, j ∈ N are comparable if i j or j i holds, and incomparable otherwise. An element i ∈ N is smaller or equal, respectively larger or equal to j ∈ N , if i j or j i holds, respectively. The elements are equal if i is both, smaller and larger or equal to j. A subset of items I ⊆ N is called a chain if P restricted to I induces a linear order on the set I . Analogously, a subset of items I ⊆ N is called an antichain if no pair of items i, j ∈ I is comparable. The size of a maximum chain and antichain, respectively, is denoted by h(P) and w(P). A subset I ⊆ N is called ideal if i ∈ I, j i implies j ∈ I . An ideal I ⊆ [n] is also said to be closed under P. We define the ideal i↓ and filter i↑, respectively, of an element i ∈ N as the set of all items which are smaller or equal and larger or equal, respectively, to i, that is, i↓:={ j ∈ N : j i} and i↑:={ j ∈ N : i j}.
123
Algorithmica
The set of all ideals of P is denoted by L(P). An element i ∈ N covers j ∈ N , if j i and there is no element k ∈ N such that j ≺ k ≺ i. The set min P:={i ∈ N : j ∈ N with j ≺ i} denotes the set of minimal items in N . Finally, we define P(A) for an ideal A ∈ L(P) as the poset P restricted to items which are not in A, that is P(A):=(N \ A, ). Notice that the restriction of a poset is also a poset. Often it is easier to talk about a poset in terms of a graph, hence, whenever it is more convenient, we use P as a graph (N , E) with an edge (i, j) ∈ E if and only if j covers i. This graph is denoted by the cover graph of P. An α-approximation algorithm for a minimization problem P is an algorithm with polynomially bounded running time which finds a feasible solution for P with solution cost of at most α times the cost of an optimal solution. A fully polynomial time approximation scheme (FPTAS) is a family F of α-approximation algorithms such that for any α > 1 there exists an α-approximation algorithm in F.
2 Knapsack Cover Inequalities Carnes and Shmoys [3] introduced the first primal–dual algorithm for the classical knapsack problem in its covering variant (KP) min{ i∈[n] ci xi : i∈[n] u i x i ≥ D, x ∈ {0, 1}n }, that is, the special case of PCCP where m = 1, d ≡ 1, and P is an antichain. A simple instance with two items {1, 2}, weights u 1 = D − 1, u 2 = D, costs c1 = 0, c2 = D and demand D shows that the LP relaxation of the formulation above has an unbounded integrality gap. The optimal IP solution has to select item two with solution cost D while an optimal LP solution chooses item one and only a fraction D1 of item two, yielding optimal solution costs of one. The integrality gap can be strengthened with help of the so-called knapsack cover inequalities i∈N \A u i (A)xi ≥ D(A) for A ⊆ N , introduced by Carr et al. [4]. These inequalities read as follows: if set A ⊆ N were selected into the solution, then the remaining items have to cover a residual demand of at least D(A):= max{D − i∈A u i , 0}. Due to integrality constraints for items, the constraint coefficients can be cropped at the right hand side value, hence u i (A):= min{u i , D(A)} can be seen as the effective weight of an item given that the items in A are part of the solution. The inequalities are also helpful for the design of approximation algorithms for a variety of covering related problems such as facility location [3] or network design [4]. As shown in [3], a primal–dual greedy algorithm now yields a 2-approximation to (KP). The overall goal of this paper is to design and analyze primal–dual algorithms for far reaching generalizations of (KP). Our generalizations advance in three directions: (1) we consider arbitrary integral bounds d ∈ Zn+ on the item-multiplicities, (2) we consider a set of m covering constraints, instead of only one, and (3) we add precedence constraints. At this point however, mainly in order to get the reader familiar with the techniques used in this paper, we extend the problem only in direction (1) we present a short N . Therefore, we redefine analysis of a generalization of the result in [3] towards d ∈ Z+ the residual demand for a set of items A ⊆ N as D(A):= max{D − i∈A u i di , 0}, that is, we assume that whenever an item is part of the solution, its item multiplicity is chosen to be as large as possible. With these definitions, the linear relaxation of the
123
Algorithmica
Algorithm 1: Primal–Dual algorithm for PCKP 1: 2: 3: 4: 5: 6: 7:
Let S = ∅, y ≡ 0. while D(S) > 0 do Increase y(S) until some dual constraint becomes tight for item i ∈ N \ S. xi = min{ D(S) u i , di }. S = S ∪ {i}. end while return S.
knapsack problem with general d ∈ Zn+ becomes min
i∈N
ci xi |
u i (A) · xi ≥ D(A) ∀A ⊆ N , x ≥ 0 .
(1)
i ∈A /
Note that the upper bound x ≤ d is given implicitly by the new definition of D(A) and u i (A) as increasing a variable xi beyond di increases the solution costs without further decreasing the residual demand for constraints for sets A + i (which is short for A ∪ {i}). For the same reason, the new formulation is infeasible if the knapsack instance was infeasible as D(N ) = D − u i di > 0 and the constraint for A = N contains no more variables. The primal–dual algorithm, given as Algorithm 1, works as follows. We start with an integral infeasible primal solution S = ∅ and a feasible solution y ≡ 0 of ⎫ ⎧ ⎪ ⎪ ⎬ ⎨ D(A) · y(A) | u i (A) · y(A) ≤ ci ∀i ∈ N , y(A) ≥ 0 , (2) max ⎪ ⎪ ⎭ ⎩ A⊆N A⊆N : i ∈A /
which is the dual of (1). In each iteration, we increase the dual variable corresponding to the current partial solution S until a dual constraint becomes tight for some item i ∈ N \ S. The item is added to the solution and xi is either set to its upper bound di or to the minimal value such that the residual demand D(S) is exceeded. The algorithm iterates until the solution exceeds the knapsack demand, that is until D(S) ≤ 0. Theorem 1 Algorithm 1 is a primal–dual 2-approximation for the knapsack problem with general d ∈ Zn+ . Proof Theorem 1 follows from the statements of the following two Lemmata.
Lemma 1 Algorithm 1 finds a feasible primal–dual solution pair (S, y) for the knapsack problem with general d ∈ Zn+ . Furthermore, for all items i ∈ S the corresponding dual constraint is tight. Proof This proof is essentially equivalent to the case d ≡ 1 given in [3]. Let S = {1, . . . , } be the set of items in increasing order in which the algorithm added the items. In each iteration i, the algorithm adds item i ∈ / S to S, hence it terminates after at most |N | iterations. Upon completion, we either have D(S) = D − i∈S u i di ≤ 0
123
Algorithmica
or the instance is infeasible since D(N ) > 0. Due to Line 4, it is clear that xk = dk for all k = 1, . . . , − 1 and the last variable x will be minimal such that the weight of S exceeds the knapsack capacity. For each item i ∈ S it is clear that the dual constraint is tight since we only add items if their corresponding constraint became tight. As soon as an item was added to S, it no longer has any non-zero constraint coefficients for dual variables considered in any later iteration. Hence, no dual constraint will be violated. Lemma 2 Algorithm 1 finds a 2-approximation for the knapsack problem with general d ∈ Zn+ . Proof Let S = {1, . . . , } be the support of the solution found by Algorithm 1 ordered in increasing order in which the algorithm considered the items with item multiplicities x. Then i∈S u i xi − u < D holds since otherwise, reducing x by one would still be feasible, which violates the definition in Line 4 of the algorithm. We also know that y(A) is only positive for sets A ⊆ {1, . . . , − 1} which are a prefix of S. Hence, we can estimate the solution cost by cost (S) =
ci xi =
=
y(A)
A⊆N
<
y(A)u i (A)xi =
i∈S A⊆N :i ∈A /
i∈S
y(A) D −
A⊆N
y(A)
A⊆N
u i (A)xi − u (A) −
i∈S
u i (A)xi
i∈S\A
u i di + u (A)
i∈A
i∈A
u i di + u (A) ≤ 2
y(A)D(A) ≤ 2 · OPT,
A⊆N
which concludes the proof.
A straightforward generalization of the results for KP towards PCKP would invoke the following precedence constrained minimum knapsack formulation: n ci xi | u i (A)xi ≥ D(A) ∀A ⊆ N , xi − x j ≥ 0 ∀i j, x ∈ {0, 1} min i∈N
i ∈A /
(PK P2 ) However, the integrality gap of this LP can be unbounded as stated in Proposition 1. In order to bound the integrality gap, we will incorporate the poset structure into the knapsack cover inequalities, see the next section. Proposition 1 Formulation (PK P2 ) has an unbounded integrality gap. Proof Consider an instance of PCKP with n items, demand D = 1, u i ≡ 1 for all i ∈ [n], c1 = n, ci = 1 for all i ∈ [n] \ {1} and a partial order which is a chain of length n with 1 2 · · · n. Then an optimal IP solution has to buy item one at cost n due to the partial order constraints. The LP solution, however, selects the solution vector ( n1 , . . . , n1 ) with solution cost nn + n−1 n < 2.
123
Algorithmica
3 Precedence Constrained Knapsack Cover Inequalities This section introduces our novel generalization of knapsack cover inequalities towards precedence constraints. For this section we consider only PCKPs, that is m = 1 and d ≡ 1. Instead of independently formulated precedence constraints, we generalize the notion of effective weight towards precedence constrained effective weight. The formulation from Sect. 2 introduces a constraint for each subset A ⊆ [n] of items which lower bounds the weight of selected items in [n] \ A given that all items in A are part of the solution. We now describe a similar type of constraint in the presence of precedence constraints. Let us ease into the idea by considering our inequality for A = ∅. If the demand D is positive, clearly at least one of the minimal items in min P has to be selected in any feasible solution. Hence, a constraint of type
xi ≥ 1
(3)
i∈min P
would be a valid inequality for PCKP. But this type of constraint has a weakness. It does not distinguish between minimal items which enable us to select a large amount of weight and minimal items which do not have any successors. Selecting an expensive minimal item which contains a lot of weight in its filter may be preferable to lowpriced items with few successors. Therefore, we would like to replace the right hand side value by the actual demand D and introduce weight coefficients for the elements which reflect the total amount of weight obtainable by selecting them. Our approach defines the effective weight of an item i ∈ min P to be a share of the total weight in its filter i↑. Intuitively, we take each non-minimal item j ∈ P \ min P [i.e. the elements with coefficient zero in (3)] and project its weight down uniformly onto the minimal items in its shadow, that is, onto j↓ ∩ min P. The formal definition follows in the next paragraph. More generally, we can define our constraints under the assumption that a certain subset A of items is part of the solution. Formalizing the explanation above, we define the effective weight u¯ i (A) of an item i and ideal A ∈ L(P) of selected items to be the depicted share of the total weight of the filter i↑, if i ∈ min P(A), or zero otherwise. Recall that P(A) denotes the partially ordered set P restricted to elements which are not in A. In order to project down weights, we define X j (A) for item j to be the set of items in min j↓ with respect to P(A), that is, X j (A):={i : i j and i ∈ min P(A)}. As usual, coefficients exceeding the right hand side of any inequality can be cropped. Hence for items i ∈ min P(A), the effective weight is given by ⎧ ⎨
⎫ u j (A) ⎬ u¯ i (A):= min D(A), u i + . ⎩ |X j (A)| ⎭ j:i≺ j
The sum describes the total amount of projected weight for an item. With help of the definitions above, we can formulate PCKP as (PPC K P ) with dual of its linear relaxation (D PC K P ).
123
Algorithmica
min
⎧ ⎨ ⎩
i∈N
ci xi |
u¯ i (A) · xi ≥ D(A) ∀A ∈ L(P), x ∈ {0, 1}n
i∈min P (A)
⎫ ⎬ ⎭
(PPC K P ) ⎫ ⎪ ⎪ ⎬ max y(A)D(A) | u¯ i (A)· y(A) ≤ ci ∀i ∈ N , y(A) ≥ 0 ∀A ∈ L(P) ⎪ ⎪ ⎪ ⎪ ⎩A∈L(P ) ⎭ A∈L(P ):i∈ ⎧ ⎪ ⎪ ⎨
min P (A)
(D PC K P ) The primal covering constraints i∈min P (A) u¯ i (A) · xi ≥ D(A) for A ∈ L(P), which we call precedence constrained knapsack cover inequalities, ensure that the selected elements in min P(A) satisfy the residual demand D(A). In contrast to the previous section, however, the effective weight u¯ i (A) of an item i has changed to also reflect a share of the item weights in the filter of i. The new set of constraints has two advantages. (1) The set of partial order constraints is no longer required as it is implicitly enforced by the constraints. (2) The primal–dual greedy algorithm is guided such that it will always generate a solution which is closed under P. The bad example described in Proposition 1 is no longer valid in (PPC K P ). In fact, for this particular instance, the LP optimum now coincides with the IP optimum. Lemma 3 shows that the formulation indeed models the precedence constrained knapsack problem. Lemma 3 (PPC K P ) is a valid relaxation for PCKP, that is, any integer feasible solution in (PK P2 ) is feasible in (PPC K P ). Furthermore, any feasible solution for ((PPC K P )) which is closed under P is feasible in (PK P2 ). Proof Let us consider an integer feasible solution x of (PK P2 ) with support S:={i : xi = 1} and an arbitrary ideal A ∈ L(P). Since x is feasible in (PK P2 ), we know that i∈S\A u i (A) ≥ D(A) holds. We will see that the corresponding covering constraint in ((PPC K P )) will also be satisfied. If S \ A ⊆ min P(A), we are done as the elements in both sums coincide and the coefficients in the covering constraint of (PPC K P ) dominate the corresponding coefficients in (PK P2 ). Now, suppose that there is an item i ∈ (S \ min P(A)) \ A. Since the knapsack instance is precedence constrained, all items in i↓ ∩ min P(A) = X i (A) are also contained in S. Since the weight of item i is allocated uniformly among the items in X i (A) and X i (A) \ S = ∅ holds, the weight of item i is also present in the covering constraint of (PPC K P ). As this observation holds for all items in (S \ min P(A)) \ A, we can deduce that i∈S∩min P (A) u¯ i (A) ≥ i∈S\A u i (A) ≥ D(A) holds. For the second implication, we consider an integer feasible solution x of (PPC K P ) we know that with support S = {i : xi = 1}. Since x is feasible, i∈min P (S) u¯ i (S)x i = 0 ≥ D(S) holds. Hence we conclude that i∈S u i ≥ D. Since S is assumed to be closed under P and the knapsack constraint is satisfied, the solution is feasible in (PK P2 ). Lemma 4 shows that the primal–dual greedy algorithm described in the previous section (Algorithm 1), finds a feasible primal–dual solution pair (S, y) to (PPC K P )
123
Algorithmica
and (D PC K P ). The subsequent Theorem 2 derives an upper bound of w(P) on the solution quality. Finally, Lemma 5 shows that this bound is tight. Lemma 4 The greedy algorithm finds a feasible primal–dual solution pair (S, y) to (PPC K P ) and (D PC K P ) in polynomial time. Furthermore, for any item i ∈ S, the corresponding dual constraint is tight. Proof For this proof, we denote the chain of ideals Si ∈ L(P) which are generated by the algorithm by ∅ = S0 ⊂ S1 ⊂ · · · ⊂ S = S. It is easyto see that the generated primal solution S satisfies the knapsack constraint D ≤ i∈S u i as the algorithm stops only if D(S) ≤ 0 or S = [n]. If the algorithm stopped due to the latter and D(S) > 0, it is clear that the instance was infeasible. Otherwise, the solution satisfies the knapsack constraint and it remains to show that the solution is closed under P, which follows from an inductive argument. Indeed, the empty set is closed under P, hence solution S0 is closed under P. The algorithm adds an item i in iteration k only if it is a minimal item with respect to P(Sk ). Due to the definition of P(A) it is clear that Sk ∪ {i} remains an ideal if i ∈ min P(Sk ). Let us consider the chain of ideals for dual feasibility. The algorithm increases dual variables only on the chain S0 ⊂ · · · ⊂ S . As soon as an item was added to subset Sk , it has no more non-zero constraint coefficients in any later iteration due to the design of our constraints. Recall that a constraint sums the effective precedence constrained weight among all items in P(Sk ), namely no items which are contained in Sk . Since the algorithm makes sure that an item is added to the solution as soon as the first constraint in an iteration became tight, this concludes the proof. Theorem 2 A solution found by the greedy algorithm has cost of at most w(P) · OPT, where w(P) denotes the size of a maximum antichain in P. Proof Let S be the set of items in the final solution with integer feasible solution x = χ S . Then the solution cost can be evaluated as follows: cost (S) =
ci =
i∈S
≤
i∈S
A∈L(P ): i∈min P (A)
y(A)u¯ i (A) =
A∈L(P )
y(A)
u¯ i (A)
i∈min P (A)∩S
y(A)D(A)| min P(A) ∩ S|
A∈L(P )
≤ max {| min P(A) ∩ S|} A∈L(P )
y(A)D(A) ≤ w(P) · OPT.
A∈L(P )
The second equality is due to the fact that we only add items to S if the corresponding dual constraint is tight. The third equality can be achieved by reordering the terms of the sum. By definition, we know that u¯ i (A) ≤ D(A) holds, hence the first inequality holds. The second inequality estimates the sum by taking the maximum among terms. Since minimal elements are incomparable by definition, we know that the cardinality can be bounded by the size of a maximum antichain in P. Lemma 5 The bound in Theorem 2 is tight.
123
Algorithmica
Proof Consider a poset with 2nk items consisting of k parallel chains each of length 2n with the following functions representing the ith item in the th chain: u i = 1 if i ≤ n and u i = k − 1 if i > n, ci = 1 if i ≤ n and ci = K if i > n for some fixed, large K ∈ Z+ . If we consider a corresponding PCKP instance with D = nk, an optimal solution will consist of the first n items from each of the k chains with a solution cost of nk. Each chain on its own will also correspond to a feasible solution with cost n + K n. Let us consider the precedence constrained knapsack inequality for A = ∅ which reads as follows: k=1 u¯ 1 (∅)x1 = k=1 nkx1 ≥ nk. For the optimum solution, all variables in this constraint are set to one, hence k=1 u¯ 1 (∅)x1 = knk and k = w(P) which yields equality in our argumentation in the proof of Theorem 2. Since our algorithm starts by increasing the corresponding dual variable y(∅), this concludes the proof. As a remark we want to point out that the modified primal–dual greedy algorithm inherits the primal–dual greedy algorithm of Carnes and Shmoys [3] in the special case where P is an antichain. Theorem 3 shows that the algorithm yields a constant factor approximation whenever the precedence constrained effective weight is bounded by a constant factor. In the case of an antichain we have α = 1, hence a 2-approximation. Theorem 3 If there is a constant α ≥ 1 such that u¯ i (A) ≤ αu i (A) holds for all items i ∈ N and ideals A ∈ L(P), then the primal–dual algorithm finds a solution of cost at most 2α · OPT. Proof Let S be the set of items in the final solution with integer feasible solution x = χ S and be the last item considered by the algorithm. Then the solution cost can be evaluated as follows: cost (S) = ci = y(A)u¯ i (A) ≤ α y(A) u i (A) i∈S
≤α
i∈S
A∈L(P ): i∈min P (A)
A∈L(P )
i∈min P (A)∩S
(4) y(A)(D(A) + u (A)) ≤ 2α · OPT.
(5)
A∈L(P )
The first inequality is due to our assumption that u¯ i (A) ≤ αu i (A). The steps (4)–(5) are essentially equivalent to the proof of Lemma 2 and due to the fact that i∈S u i x i − u < D holds. Corollary 1 If P is an antichain, then the primal–dual greedy algorithm finds a 2approximation for PCKP.
4 Precedence Constrained Covering Problems The precedence constrained knapsack cover inequalities can also be used to reformulate general PCCPs with d ≡ 1 by replacing each knapsack constraint
123
Algorithmica
k k i∈N u i x i ≥ D individually. Hence, a PCCP instance (PPCC P ) with dual of the linear relaxation (D PCC P ).
min
⎧ ⎨ ⎩
ci xi |
u¯ ik (A) · xi ≥ D k (A) ∀A ∈ L(P) ∀k ∈ K , x ∈ {0, 1}n
i∈min P (A)
i∈N
can be reformulated as ⎫ ⎬ ⎭
(PPCC P )
max
⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩k∈K
y k (A)D k (A) |
A∈L(P )
k∈K A∈L(P ): i∈min P (A)
⎫ ⎪ ⎪ ⎬
u¯ ik (A)· y k (A) ≤ ci ∀i ∈ N , y ≥ 0 . ⎪ ⎪ ⎭ (D PCC P )
Similar to Lemma 3, it is easy to see that the model is a relaxation for (PCCP). We will now show that a slightly modified version of Algorithm 1 also finds a primal–dual solution pair for (PPCC P ) and (D PCC P ). Therefore, let us consider an iteration of the algorithm for some partial solution S . In the one-dimensional case, we increased the corresponding dual variable y(S ) until a dual constraint became tight. In this case, we have m variables y k (S ) to choose from. The natural way to increase variables here is to increase each variable proportionally to its residual demand D k (S ) until a constraint becomes tight for item i ∈ / S . As before, we add item i to S and iterate k
until D (S ) ≤ 0 for all k ∈ K . With the same argumentation as in Lemma 4, we can observe that the algorithm finds a primal–dual solution pair (S, y) to (PPCC P ) and (D PCC P ). Theorem 4 yields the approximation ratio of w(P) which surprisingly coincides with the one-dimensional case. Theorem 4 A solution found by the modified primal–dual algorithm has cost of at most w(P) · OPT. Proof As before, let S be the set of items in the final solution with integer feasible solution x = χ S . Then the solution cost can be evaluated as follows: cost (S) =
ci =
i∈S
=
y k (A)
(6)
u¯ ik (A)
i∈min P (A)∩S
y (A)D k (A)| min P(A) ∩ S| k
A∈L(P ) k∈K
≤ max {| min P(A) ∩ S|} A∈L(P )
which concludes the proof.
123
y k (A)u¯ ik (A)
i∈S k∈K A∈L(P ): i∈min P (A)
A∈L(P ) k∈K
≤
(7)
y k (A)D k (A) ≤ w(P) · OPT, (8)
A∈L(P ) k∈K
Algorithmica
Corollary 2 If the poset is an antichain, the modified primal–dual algorithm finds a solution with cost no larger than p · OPT, where p denotes the maximal number of non-zero entries in any row of the initial constraint set Ax ≥ D. Proof Let us consider the proof of Theorem 4 for the situation stated in Corollary 2. Since P is an antichain, any subset of N is an ideal, that is, L(P) = 2 N . Furthermore, if we consider a fixed constraint k ∈ K , we know that the total number of non-zero entries is bounded by some integer p k . Hence, the term i∈min P (A)∩S u¯ ik (A) in step (7) can be bounded by p k D k (A). With this observation in mind, the proof of Theorem 4 reads as follows. cost (S) = ci = y k (A)u¯ ik (A) (9) i∈S
=
A⊆N k∈K
≤ max{ p } k
k∈K
which concludes the proof.
i∈S k∈K A⊆N : i ∈A /
y k (A)
u¯ ik (A) ≤
i∈S\A
y k (A)D k (A) p k
A⊆N k∈K
y (A)D (A) ≤ p · OPT, k
(10)
k
(11)
A⊆N k∈K
For the special case of capacitated covering problems without precedence constraints and with d ≡ 1, the primal–dual algorithm finds a p-approximation, where p denotes the maximal number of non-zero entries in any row of the initial constraint set Ax ≥ D. A similar algorithm for this special case was also pointed out by Fujito and Yabuta [7] and Koufogiannakis and Young [16]. Unfortunately, the results of this section can not be extended towards PCCP with d ≡ 1 in the way we did this for KP in Sect. 2. Lemma 2 shows that a solution found by the algorithm considered in this section may no longer have bounded cost. Nevertheless, we are able to provide a pseudo-polynomial time approximation algorithm for this case with help of Theorem 3. Proposition 2 The approximation ratio of the modified variant of Algorithm 1 for instances of PCCP with d ≡ 1 is unbounded even if m = 1. Proof Consider an instance with two items N = {1, 2} with demand D, a partial order P = (N , 1 2) and c ≡ 1, u 1 = 1, u 2 = D, d1 = D, d2 = 1. Then the optimal IP solution consists of a single copy of the first item and a single copy of the second item, the algorithm however would select D copies of item one. Proposition 3 For PCCP with d ≡ 1 there is a w(P)Δ-approximation algorithm with running time O(n 2 mΔ), where Δ = maxi {di }. Proof From an instance of PCCP with d ≡ 1 we can construct an instance of PCCP with d ≡ 1 by introducing di copies of each item which are denoted by i k , 0 ≤ k ≤ di . In the partially ordered set, we replace each item i by its di copies and introduce a chain i 1 i 2 · · · i di . For each cover i j we introduce precedence constraints
123
Algorithmica
i k j k for 0 ≤ k ≤ d j . Note that we can assume that di ≥ d j holds whenever i j, hence the constraints above can always be constructed. For the approximation factor, we need to determine the maximum size of an antichain in the constructed partial order P . Since we introduce at most Δ copies of each item, the constructed partially ordered set is a subset of the Δ-power set, that is, P ⊆ ×Δ P:=P Δ . A maximum antichain in P Δ intersected with each of the layers contains at most w(P) elements. Hence, a maximum antichain can be of cardinality at most w(P)Δ.
5 Inapproximability of PCKP We will show by reduction from the densest k-subhypergraph problem that PCKP does not admit a PTAS. The densest k-subhypergraph problem is given by a hypergraph G = (V, E) and parameter k and asks for a subset of k vertices such that the number of induced hyperedges is maximized. In case of normal graphs (i.e. hypergraphs whose edges contain exactly two vertices), Khot showed that there is no PTAS for the problem unless N P ⊆ ∩>0 BPTIME(2n ) [13]. At this point we want to point out that the k-subhypergraph problem was shown to be δ hard to approximate within a factor of 2(log n) for some δ > 0 under the assumption 3
4+
) [8]. Unfortunately, we can not use this result for that 3-SAT ∈ / DTIME(2n our reduction as their construction requires the hyperedges to contain more than a constant number of vertices (In this case, ρ in Theorem 6 dominates the approximation factor). Nevertheless, any emerging inapproximability results in hypergraphs with edges containing only a constant number of vertices may improve our lower bound. In order to formulate the densest k-subhypergraph problem as a precedence constrained covering problem, we will use the following auxiliary problem denoted by the smallest -Edge induced subhypergraph problem (-EIS). Given a hypergraph G = (V, E) and a parameter we seek to select at least hyperedges such that the total number of induced vertices is minimized. It is easy to observe that an exact algorithm for the latter problem can be used in order to solve the densest k-subhypergraph problem: If we guess the optimal number of edges ∗ of the densest k-subhypergraph problem, an optimal solution to -EIS will contain exactly k vertices as well. Hence, a binary search for ∗ could be used in order to solve the densest k-subhypergraph problem with such algorithm. In the remainder of this section, we will see that we can also transfer approximation factors, hence, transferring the inapproximability of the densest k-subhypergraph problem to -EIS. With help of the following Theorem 5, this transfers to PCKP as well. Theorem 5 For any > 0, a (1 + )-approximation algorithm for PCKP can be used to obtain a (1 + )-approximation algorithm for -EIS. Proof From a given instance of -EIS with graph G = (V, E) and parameter we can construct an instance of PCKP as follows. We introduce items for each vertex v ∈ V and each hyperedge e ∈ E and precedence constraints of the form v ≤ e ⇔ v ∈ e.
123
Algorithmica
Vertex-items will be associated with a cost cv = 1 and zero weight, edges will be associated with zero cost and weight we = 1. The PCKP instance seeks for a solution with weight at least . By construction, a feasible solution to the PCKP instance requires the selection of at least edge items on the second level in the bipartite order. Prior to the selection of an edge item, all its adjacent vertex items had to be selected. Hence, a feasible solution to PCKP with weight equal to corresponds to a feasible solution to -EIS and vice-versa. Since both objective functions coincide, it is easy to see that a (1 + )approximation for PCKP can be used to obtain the same approximation factor for -EIS. Theorem 6 For any > 0, a (1 + )-approximation algorithm for -EIS can be 1 )-approximation algorithm for the densest k-subhypergraph problem, used as a ( 1+ρ where ρ denotes the size of a largest edge. Proof Let us consider a given instance G = (V, E) with parameter k of the densest k-subhypergraph problem with optimal objective function value ∗ and the corresponding ∗ -EIS instance. If we apply a (1 + )-approximation algorithm for -EIS to the instance, we obtain a subhypergraph G = (V , E ) of G with ∗ edges. Note that we can always remove edges from the solution to obtain exactly ∗ edges without increasing the objective function value. Claim |V | ≤ (1 + )k. Let V ∗ be an optimal solution for the k-densest subhypergraph problem, then |V | ≤ (1 + )|V ∗ | ≤ (1 + )k. Hence, we can not immediately use the graph G as a solution to the densest ksubhypergraph problem as it may contain at most k excess vertices. We will show that said vertices can be removed without decreasing the objective function value too drastically, as follows. We iteratively select a vertex v ∈ V with minimum degree in G and remove it from V until k vertices remain. In order to estimate the total number of remaining edges, let G
= (V
, E
) denote the graph at the end of the procedure. 1 Claim |E
| ≥ ∗ 1+ρ
The total number of removed edges can be estimated as follows: |E | − |E
| ≤ avg Deg(G
)k 1 = deg(v)k k
v∈V
≤ ρ|E |, where ρ is the largest size of an edge. Hence, ∗ ≤ |E | ≤ (1 + ρ)|E
|.
n
Corollary 3 There exists no PTAS for PCKP unless N P ⊆ ∩>0 BPTIME(2 ).
123
Algorithmica
Proof Any (1 + )-approximation for PCKP yields a (1 + 2) approximation for the densest k-subgraph problem. Hence, a PTAS for PCKP can be used as a PTAS for the densest k-subgraph problem which is not possible under the stated complexity assumptions as shown by Khot [13].
6 Summary and Outlook This paper described primal–dual approximation algorithms for several generalizations of the classical minimum knapsack problem. More precisely, we solved variants of PCCP which are of the form ci xi : Ax ≥ D, x ≤ d, x ∈ Z+ , (POSET) , min i∈N
where (POSET) describes a set of partial order constraints, A ∈ Zm×n and D and d + are of appropriate dimension. As an introduction, we described a 2-approximation algorithm for d ≡ 1 and m = 1 without precedence constraints. The following results were subject to precedence constraints. We introduced a generalized notion of the well-known knapsack cover inequalities towards precedence constraints, denoted by precedence constrained knapsack cover inequalities. With help of these inequalities we were able to provide a w(P) approximation algorithm for PCKP, that is, d ≡ 1, m = 1 which we generalized towards d ≡ 1, m > 1. As a byproduct, we derived a p-approximation for CP with d ≡ 1, m > 1 without precedence constraints which was already discussed in [7,16]. Finally, we provided a construction which allows to solve PCCP with d ≡ 1 and m > 1 within a factor of w(P)Δ in pseudo-polynomial time. It remains open to find an algorithm with strongly polynomial bounds. Our results are also summarized in Table 1. Although we presented the first approximation algorithms for precedence constrained covering problems, there still remains a gap between the lower and upper bounds. It would especially be interesting to provide a lower bound similar to the packing version of PCKP as provided by Hajiaghayi et al. [8]. For the generalization Table 1 Summary of the results in this paper and lower bounds on the approximation ratio m=1
d≡1
(POSET)
Lower bound
Previous upper bound
Our upper bound
Y
N
N
NP-hard
2, rounding, (FPTAS)
2, primal–dual
Y
Y
Y
no PTAS
n/a
w(P)
N
Y
Y
no PTAS
n/a
w(P)
Y
N
Y
no PTAS
n/a
w(P)Δ
N
N
Y
no PTAS
n/a
(pseudo-polynomial) w(P)Δ (pseudo-polynomial) n
Lower bounds are assuming N P ∩>0 BPTIME(2 ). Bounds in bold are results of this paper
123
Algorithmica
towards d ≡ 1 we were only able to provide pseudo-polynomial algorithms, hence it remains open to provide strongly polynomial bounds. Since CPs with bounded dilation α are approximable within Θ(log(α)), it might be interesting to consider this case in the presence of precedence constraints as well.
References 1. Boland, N., Bley, A., Fricke, C., Froyland, G., Sotirov, R.: Clique-based facets for the precedence constrained knapsack problem. Math. Program. 133(1–2), 481–511 (2012) 2. Boyd, A.: Polyhedral results for the precedence-constrained knapsack problem. Discrete Appl. Math. 41(3), 185–201 (1993) 3. Carnes, T., Shmoys, D.: Primal–dual schema for capacitated covering problems. In: Andrea, L., Alessandro, P., Giovanni R. (eds) Integer Programming and Combinatorial Optimization, pp. 288– 302. Springer, Berlin (2008) 4. Carr, R., Fleischer, L., Leung, V., Phillips, C.: Strengthening integrality gaps for capacitated network design and covering problems. In: Proceedings of the Eleventh Annual ACM–SIAM Symposium on Discrete Algorithms, pp. 106–115. Society for Industrial and Applied Mathematics, Philadelphia (2000) 5. Dinur, I., Guruswami, V., Khot, S., Regev, O.: A new multilayered pcp and the hardness of hypergraph vertex cover. SIAM J. Comput. 34(5), 1129–1146 (2005) 6. Feige, U., Kogan, S.: Hardness of approximation of the balanced complete bipartite subgraph problem. Tech. Rep. MCS04-04, Department of Computer Science and Applied Mathematics, Weizmann Institute, Rehovot, Israel (2004) 7. Fujito T., Yabuta, T.: Submodular integer cover and its application to production planning. In: Giuseppe, P., Roberto, S.-O. (eds) Approximation and Online Algorithms, pp. 154–166. Springer, Berlin (2005) 8. Hajiaghayi, M., Jain, K., Konwar, K.,Lau, L., Mandoiu, I., Russell , A., Shvartsman, A., Vazirani V.: The minimum k-colored subgraph problem in haplotyping and DNA primer selection. In: Proceedings of the International Workshop on Bioinformatics Research and Applications (IWBRA) (2006) 9. Ibarra, O.H., Kim, C.E.: Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM 22(4), 463–468 (1975) 10. Johnson, D., Niemi, K.: On knapsacks, partitions, and a new dynamic programming technique for trees. Math. Oper. Res. 8(1), 1–14 (1983) 11. Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Berlin (2004) 12. Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2-ε. J. Comput. Syst. Sci. 74(3), 335–349 (2008) 13. Khot, S.: Ruling out ptas for graph min-bisection, dense k-subgraph, and bipartite clique. SIAM J. Comput. 36(4), 1025–1071 (2006) 14. Kolliopoulos S., Steiner G.: Partially-ordered knapsack and applications to scheduling. In: Algorithms ESA 2002, pp. 612–624. Springer (2002) 15. Kolliopoulos, S.G., Young, N.E.: Tight approximation results for general covering integer programs. In: 42nd IEEE Symposium on Foundations of Computer Science. Proceedings, pp. 522–528. IEEE (2001) 16. Koufogiannakis, C., Young, N.E.: Greedy δ-approximation algorithm for covering with arbitrary constraints and submodular cost. Algorithmica 66(1), 113–152 (2013) 17. Park, K., Park, S.: Lifting cover inequalities for the precedence-constrained knapsack problem. Discrete Appl. Math. 72(3), 219–241 (1997) 18. Pritchard, D., Chakrabarty, D.: Approximability of sparse integer programs. Algorithmica 61(1), 75–93 (2011) 19. Trevisan, L.: Non-approximability results for optimization problems on bounded degree instances. In: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, pp. 453–461. ACM (2001) 20. Van de Leensel, R., van Hoesel, C., van de Klundert, J.: Lifting valid inequalities for the precedence constrained knapsack problem. Math. Program. 86(1), 161–185 (1999) 21. Woeginger, G.: On the approximability of average completion time scheduling under precedence constraints. Discrete Appl. Math. 131(1), 237–252 (2003)
123