Approximation Algorithms: Packing Problems

This is the lecture notes from Chandra Chekuri's CS583 course on Approximation Algorithms. Chapter 4: Packing Problems. You can read Chapter 5: Load Balancing and Bin Packing, here. Chapter 3: Knapsack, here.

Chapter 4

In the previous lecture we discussed the Knapsack problem. In this lecture we discuss other packing and independent set problems. We first discuss an abstract model of packing problems. Let

N

be a finite ground set. A collection of

I \subset 2^{N}

of subsets of

N

is said to be down closed if the following property is true:

A \in I

implies that for all

B \subset A, B \in I

. A down closed collection is also often called and independence system. The sets in

I

are called independent sets. Given an independence family

(N, I)

and a non-negative weight function

w : N \to R^{+}

the maximum weight independent set problem is to find

max_{S \in I} w (S)

. That is, find an independent set in

I

of maximum weight. Often we may be interested in the setting where all weights are

1

in which case we wish to find the maximum cardinality independent set. We discuss some canonical examples.

Example 4.1. Independent sets in graphs: Given a graph

G = (V, E)

I = {S \subseteq V ∣ there are no edges between nodes in S}

. Here the ground set is

V

. There are many interesting special cases of the graph problem. For instance problems arising from geometric objects such as intervals, rectangles, disks and others.

Example 4.2. Matchings in graphs: Given a graph

G = (V, E)

let

I = {M \subseteq E ∣ M is a matching in G}

. Here the ground set is

E

Example 4.3. Matroids: A matroid

M = (N, I)

is defined as a system where

I

is down closed and in addition satisfies the following key property: if

A, B \in I

and

| B | > | A |

then there is an element

e \in B ∖ A

such that

A \cup {e} \in I

. There are many examples of matroids. We will not go into details here.

Example 4.4. Intersections of independence systems: given some

k

independence systems on the same ground set

(N, I_{1}), (N, I_{2}), \dots, (N, I_{k})

the system defined by

(N, I_{1} \cap I_{2} \dots \cap I_{k})

is also an independence system. Well-known examples include intersections of matroids.

4.1 Maximum Independent Set Problem in Graphs

A basic graph optimization problem with many applications is the maximum (weighted) independent set problem (

MIS

) in graphs.

Definition 4.1. Given an undirected graph

G = (V, E)

a subset of nodes

S \subseteq V

is an independent set (stable set) iff there is no edge in

E

between any two nodes in

S

. A subset of nodes

S

is a clique if every pair of nodes in

S

have an edge between them in

G

The

MIS

problem is the following: given a graph

G = (V, E)

find an independent set in

G

of maximum cardinality. In the weighted case, each node

v \in V

has an associated non-negative weight

w (v)

and the goal is to find a maximum weight independent set. This problem is

NP

-Hard and it is natural to ask for approximation algorithms. Unfortunately, as the famous theorem below shows, the problem is extremely hard to approximate.

Theorem 4.2 (Håstad ^[1]). Unless $P = N P$ there is no $\frac{1}{n^{1 - ϵ}}$ -approximation for $MIS$ for any fixed $ϵ > 0$ where $n$ is the number of nodes in the given graph.

Remark 4.1. The maximum clique problem is to find the maximum cardinality clique in a given graph. It is approximation-equivalent to the

MIS

problem; simply complement the graph.

The theorem basically says the following: there are a class of graphs in which the maximum independent set size is either less than

n^{δ}

or greater than

n^{1 - δ}

and it is

NP

-Complete to decide whether a given graph falls into the former category or the latter.

The lower bound result suggests that one should focus on special cases, and several interesting positive results are known. First, we consider a simple greedy algorithm for the unweighted problem.

\underline{Greedy (G)}

$S \leftarrow \emptyset$
While $G$ is not empty do

A.Let $v$ be a node of minimum degree in $G$
B. $S \leftarrow S \cup {v}$
C.Remove $v$ and its neighbors from $G$

Output $S$

Theorem 4.3. Greedy outputs an independent set

S

such that

| S | \geq n / (Δ + 1)

where

Δ

is the maximum degree of any node in the graph. Moreover

| S | \geq α (G) / Δ

where

α (G)

is the cardinality of the largest independent set. Thus Greedy is a

1 / Δ

approximation.

Proof. We upper bound the number of nodes in

V ∖ S

as follows. A node

u

is in

V ∖ S

because it is removed as a neighbor of some node

v \in S

when Greedy added

v

S

. Charge

u

v

. A node

v \in S

can be charged at most

Δ

times since it has at most

Δ

neighbors. Hence we have that

| V ∖ S | \leq Δ | S |

. Since every node is either in

S

V ∖ S

we have

| S | + | V ∖ S | = n

and therefore

(Δ + 1) | S | \geq n

which implies that

| S | \geq n / (Δ + 1)

We now argue that

| S | \geq α (G) / Δ

. Let

S^{*}

be a largest independent set in

G

. As in the above proof we can charge each node

v

S^{*} ∖ S

to a node

u \in S ∖ S^{*}

which is a neighbor of

v

. The number of nodes charged to a node

u \in S ∖ S^{*}

is at most

Δ

. Thus

| S^{*} ∖ S | \leq Δ | S ∖ S^{*} |

Exercise 4.1. Show that Greedy outputs an independent set of size at least

\frac{n}{2 (d + 1)}

where

d

is the average degree of

G

Remark 4.2. The well-known Turan's theorem shows via a clever argument that there is always an independent set of size

\frac{n}{(d + 1)}

where

d

is the average degree of

G

Remark 4.3. For the case of unweighted graphs one can obtain an approximation ratio of

Ω (\frac{\log d}{d \log \log d})

where

d

is the average degree. Surprisingly, under a complexity theory conjecture called the Unique-Games conjecture it is known to be

NP

-Hard to approximate

MIS

to within a factor of

O (\frac{\log^{2} Δ}{Δ})

in graphs with maximum degree

Δ

when

Δ

is sufficiently large.

Exercise 4.2. Consider the weigthed

MIS

problem on graphs of maximum degree

Δ

. Alter Greedy to sort the nodes in non-increasing order of the weight and show that it gives a

\frac{1}{Δ}

-approximation. Can one obtain an

Ω (1 / d)

-approximation for the weighted case where

d

is the average degree?

LP Relaxation: One can formulate a simple linear-programming relaxation for the (weighted)

MIS

problem where we have a variable

x (v)

for each node

v \in V

indicating whether

v

is chosen in the independent set or not. We have constraints which state that for each edge

(u, v)

only one of

u

v

can be chosen.

\begin{aligned} maximize \sum_{v \in V} w (v) x (v) \\ subject to x (u) + x (v) & \leq 1 (u, v) \in E \\ x (v) & \in [0, 1] v \in V \end{aligned}

Although the above is a valid integer programming relaxation of

MIS

when the variabels are constrained to be in

{0, 1}

, it is not a particularly useful formulation for the following simple reason.

Claim 4.1.1. For any graph the optimum value of the above LP relaxation is at least

w (V) / 2

. In particular, for the unweighted case it is at least

n / 2

Simply set each

x (v)

1 / 2

One can obtain a strengthened formulation below by observing that if

S

is clique in

G

then any independent set can pick at most one node from

S

\begin{aligned} maximize \sum_{v \in V} w (v) x (v) \\ subject to \sum_{v \in S} x (v) & \leq 1 S is a clique in G \\ x (v) & \in [0, 1] v \in V \end{aligned}

The above linear program has an exponential number of constraints, and it cannot be solved in polynomial time in general, but for some special cases of interest the above linear program can indeed be solved (or approximately solved) in polynomial time and leads to either exact algorithms or good approximation bounds.

Approximability of Vertex Cover and

MIS

: The following is a basic fact and is easy to prove.

Fact 4.1. In any graph

G = (V, E), S

is a vertex cover in

G

if and only if

V ∖ S

is an independent set in

G

. Thus

α (G) + β (G) = | V |

where

α (G)

is the size of a maximum independent set in

G

and

β (G)

is the size of a minimum vertex cover in

G

The above shows that if one of Vertex Cover or

MIS

NP

-Hard then the other is as well. We have seen that Vertex Cover admits a

2

-approximation while

MIS

admits no constant factor approximation. It is useful to see why a

2

-approximation for Vertex Cover does not give any useful information for

MIS

even though

α (G) + β (G) = | V |

. Suppose

S^{*}

is an optimal vertex cover and has size

\geq | V | / 2

. Then a

2

-approximation algorithm is only guaranteed to give a vertex cover of size

| V |

! Hence one does not obtain a non-trivial independent set by complementing the approximate vertex cover.

Some special cases of

MIS

: We mention some special cases of

MIS

that have been considered in the literature, this is by no means an exhaustive list.

Interval graphs; these are intersection graphs of intervals on a line. An exact algorithm can be obtained via dynamic programming and one can solve more general versions via linear programming methods.
Note that a maximum (weight) matching in a graph $G$ can be viewed as a maximum (weight) independent set in the line-graph of $G$ and can be solved exactly in polynomial time. This has been extended to what are known as claw-free graphs.
Planar graphs and generalizations to bounded-genus graphs, and graphs that exclude a fixed minor. For such graphs one can obtain a $PTAS$ due to ideas originally from Brenda Baker.
Geometric intersection graphs. For example, given $n$ disks on the plane find a maximum number of disks that do not overlap. One could consider other (convex) shapes such as axis parallel rectangles, line segments, pseudo-disks etc. A number of results are known. For example a $PTAS$ is known for disks in the plane. An $Ω (\frac{1}{\log n})$ -approximation for axis-parallel rectangles in the plane when the rectangles are weighted and an $Ω (\frac{1}{\log \log n}) -$ approximation for the unweighted case. For the unweighted case, very recently, Mitchell obtained a constant factor approximation!

4.1.1 Elimination Orders and MIS

We have seen that a simple Greedy algorithm gives a

Δ

-approximation for

MIS

in graphs with max degree

Δ

. One can also get a

Δ

approximation for a larger class of

Δ

-degenerate graphs. To motivate degenerate graphs consider the class of planar graphs. The maximum degree of a planar graph need not be small. Nevertheless, via Euler's theorem, we know that every planar graph has a vertex of degree at most

5

since the maximum number of edges in a planar graph is at most

3 n - 6

. Moreover, every subgraph of a planar graph is planar, and hence the Greedy algorithm will repeatedly find a vertex of degree at most 5 in each iteration. From this one can show that Greedy gives a

1 / 5

-approximation for

MIS

in planar graphs. Now consider the intersection graph of a collection of intervals on the real line. That is, we are given

n

intervals

I_{1}, I_{2}, \dots, I_{n}

where each

I_{i} = [a_{i}, b_{i}]

for real numbers

a_{i} \leq b_{i}

. The goal is to find a maximum number of the intervals in the given set of intervals which do not overlap. This is the same as finding

MIS

in the intersection graph of the intervals - the graph is obtained by creating a vertex

v_{i}

for each

I_{i}

, and by adding edges

v_{i} v_{j}

I_{i}

and

I_{j}

overlap. It is well-known that greedily picking intervals in earliest finish time order (ordering them according to

b_{i}

values) is optimal; the reader should try to prove this. Can one understand the analysis of all these examples in a unified fashion? Yes. For this purpose we consider the class of inductive

k

-independent graphs considered by by Akcoglu et al.^[2] and later again by Ye and Borodin^[3].

For a vertex

v

in a graph we use

N (v)

denote the neighbors of

v

(not including

v

itself). For a graph

G = (V, E)

and

S \subset V

we use

G [S]

to denote the subgraph of

G

induced by

S

Definition 4.4. An undirected graph

G = (V, E)

is inductive

k

-independent if there is an ordering of the vertices

v_{1}, v_{2}, \dots, v_{n}

such that for

1 \leq i \leq n, α (G [N (v_{i}) \cap

{v_{i + 1}, \dots, v_{n}}]) \leq k

Graphs which are inductively

1

-independent have a perfect elimination ordering and are called chordal graphs because they have an alternate characterization. A graph is chordal iff each cycle

C

G

has a chord (an edge connecting two nodes of

C

which is not an edge of

C

), or in other words there is no induced cycle of length more than

3

Exercise 4.3. Prove that the intersection graph of intervals is chordal.

Exercise 4.4. Prove that if

Δ (G) \leq k

then

G

is inductively

k

-independent. Prove that if

G

k

-degenerate then

G

is inductively

k

-independent.

The preceding shows that planar graphs are inductively

5

-independent. In fact, one can show something stronger, that they are inductively

3

-independent. Given a graph

G

one can ask whether there is an algorithm that checks whether

G

is inductively

k

-independent. There is such an algorithm that runs in time

O (k^{2} n^{k + 2})

^[3:1]. A classical result shows how to recognize chordal graphs

(k = 1)

in linear time. However, most of the useful applications arise by showing that a certain class of graphs are inductively

k

-independent for some small value of

k

. See ^[3:2] for several examples.

Exercise 4.5. Prove that the Greedy algorithm that considers the vertices in the inductive

k

-independent order gives a

\frac{1}{k}

-approximation for

MIS

Interestingly one can obtain a

\frac{1}{k}

-approximation for the maximum weight independent set problem in inductively

k

-independent graphs. The algorithm is simple and runs in linear time but is not obvious. To see this consider the weighted problem for intervals. The standard algorithm to solve this is via dynamic programming. However, one can obtain an optimum solution for all chordal graphs (given the ordering). We refer the reader to ^[3:3] for the algorithm and proof (originally from ^[2:1]). Showing a

Ω (1 / k)

-approximation is easier.

4.2 The efficacy of the Greedy algorithm for a class of Independence Families

The Greedy algorithm can be defined easily for an arbitrary independence system. It iteratively adds the best element to the current independent set while maintaining feasibility. Note that the implementation of the algorithm requires having an oracle to find the best element to add to a current independent set

S

\underline{Greedy (N, I)}

$S \leftarrow \emptyset$
While (TRUE)

A.Let $A \leftarrow {e \in N ∖ S ∣ S + e \in I}$
B.If $A = \emptyset$ break
C. $e \leftarrow {argmax}_{e \in A} w (e)$
D. $S \leftarrow S \cup {e}$

Output $S$

Exercise 4.6. Prove that the Greedy algorithm gives a

1 / 2

-approximation for the maximum weight matching problem in a general graph. Also prove that this bound is tight even in bipartite graphs. Note that max weight matching can be solved exactly in polynomial time.

Remark 4.4. It is well-known that the Greedy algorithm gives an optimum solution when

(N, I)

is a matroid. Kruskal's algorithm for min/max weight spanning tree is a special case of this fact.

It is easy to see that Greedy does poorly for

MIS

problem in general graphs. A natural question is what properties of

I

enable some reasonable performance guarantee for Greedy. A very general result in this context has been established due to Jenkyn's generalizing several previous results. In order to state the result we set up some notation. Given an independence system

(N, I)

we say that a set

A \in I

is a base if it is a maximal independent set. It is well-known that in a matroid

M

all bases have the same cardinality. However this is not true in general independence system.

Definition 4.5. An independence system

(N, I)

is a

k

-system if for any two bases

A, B \in I, | A | \leq k | B |

. That is, the ratio of the cardinality of a maximum base and the cardinality of a minimum base is at most

k

The following theorem is not too difficult but not so obvious either.

Theorem 4.6. Greedy gives a

1 / k

-approximation for the maximum weight independent set problem in a

k

-system.

The above theorem generalizes and unifies several examples that we have seen so far including

MIS

in bounded degree graphs, matchings, matroids etc. How does one see that a given independence system is indeed a

k

-system for some parameter

k

? For instance matchings in graphs form a

2

-system. The following simple lemma gives an easy way to argue that a given system is a

k

-system.

Lemma 4.1. Suppose

(N, I)

is an independence system with the following property: for any

A \in I

and

e \in N ∖ A

there is a set

Y \subset A

such that

| Y | \leq k

and

(A ∖ Y) \cup {e} \in I

. Then

I

is a

k

-system.

We leave the proof of the above as an exercise.

We refer the reader to ^[4],^[5] for analysis of Greedy in

k

-systems and other special cases.

4.3 Randomized Rounding with Alteration for Packing Problems

The purpose of this section to highlight a technique for rounding

LP

relaxations for packing problems. We will consider a simple example, namely the maximum weight independent set problem in interval graphs. Recall that we are given

n

intervals

I_{1}, I_{2}, \dots, I_{n}

with non-negative weights

w_{1}, \dots, w_{n}

and the goal is to find a maximum weight subset of them which do not overlap. Let

I_{i} = [a_{i}, b_{i}]

and let

p_{1}, p_{2}, \dots, p_{m}

be the collection of end points of the intervals. We can write a simple

LP

relaxation for this problem. For each interval

i

we have a variable

x_{i} \in [0, 1]

to indicate whether

I_{i}

is chosen or not. For each point

p_{j}

, among all intervals that contain it, at most one can be chosen. These are clique constraints in the underlying interval graph.

\begin{aligned} maximize \sum_{i = 1}^{n} w_{i} x_{i} \\ subject to \sum_{i : p_{j} \in I_{i}} x_{i} & \leq 1 1 \leq j \leq m \\ x_{i} & \in [0, 1] 1 \leq i \leq n \end{aligned}

Note that it is important to retain the constraint that

x_{i} \leq 1

. Interestingly it is known that the

LP

relaxation defines an integer polytope and hence one can solve the integer program by solving the

LP

relaxation! This is because the incidence matrix defining the

LP

is totally unimodular (

TUM

). We refer the reader to books on combinatorial optimization for further background on this topic. Here we assume that we do not know the integer properties of the

LP

. We will round it via a technique that is powerful and generalizes to

NP

-Hard variants of the interval scheduling problem among many others.

Suppose we solve the

LP

and obtain an optimum fraction solution

x^{*}

. We have

\sum_{i} w_{i} x_{i}^{*} \geq OPT

. How do we round to obtain an integer solution whose value is close to that of

OPT

? Suppose we randomly choose

I_{i}

with probablility

c x_{i}^{*}

for some

c \leq 1

. Let

R

be the random set of chosen intervals. Then the expected weight of

R

, by linearity of expectation, is

c \sum_{i} w_{i} x_{i}^{*} \geq c \cdot OPT

. However, it is highly likely that the random solution

R

is not going to be feasible. Some constraint will be violated. The question is how we can fix or alter

R

to find a subset

R^{'} \subseteq R

such that

R^{'}

is a feasible solution and the expected value of

R^{'}

is not too much smaller than that of

R

. This depends on the independence structure.

Here we illustrate this via the interval problem. Without loss of generality we assume that

I_{1}, \dots, I_{n}

are sorted by their right end point. In other words the order is a perfect elimination order for the underlying interval graph.

\underline{Rounding-With-Alteration}

Let $x$ be an optimum fractional solution
Round each $i$ to $1$ independently with probability $x_{i} / 2$ . Let $x^{'}$ be rounded solution.
$R \leftarrow {i ∣ x_{i}^{'} = 1}$
$S \leftarrow \emptyset$
For $i = n$ down to $1$ do

A.If $(i \in R)$ and ( $S \cup {i}$ is feasible) then $S \leftarrow S \cup {i}$

Output feasible solution $S$

The algorithm consists of two phases. The first phase is a simple selection phase via independent randomized rounding. The second phase is deterministic and is a greedy pruning step in the reverse elimination order. To analyze the expected value of

S

we consider two binary random variables for each

i, Y_{i}

and

Z_{i} . Y_{i}

1

i \in R

and

0

otherwise.

Z_{i}

1

i \in S

and

0

otherwise.

By linearity of expectation,

Claim 4.3.1.

E [w (S)] = \sum_{i} w_{i} E [Z_{i}] = \sum_{i} w_{i} P [Z_{i} = 1]

Via the independent randomized rounding in the algorithm.

Claim 4.3.2.

P [Y_{i} = 1] = x_{i} / 2

How do we analyze

P [Z_{i} = 1]

? The random variables

Z_{1}, \dots, Z_{n}

are not independent and could be highly correlated even though

Y_{1}, \dots, Y_{n}

are independent. For this purpose we try to understand

P [Z_{i} = 0 ∣ Y_{i} = 1]

which is the conditional probability that an interval

I_{i}

that is chosen in the first step is rejected in the pruning phase. We often would not be able to get an exact estimate of this quantity but we can upper bound it as follows. Here the ordering plays a crucial role. Why would

I_{i}

be rejected in the pruning phase? Note that when

I_{i}

is considered in the pruning phase, the only intervals that have been considered have their right end points after the right end point of

I_{i}

. Let

A_{i} = {j ∣ j > i

and

I_{j}

and

I_{i}

intersect at

b_{i}}

be the potential set of intervals that can cause

i

to be rejected. Recall that the

LP

implies the following constraint:

x_{i} + \sum_{j \in A} x_{j} \leq 1

at the point

b_{j}

. Let

E_{1}

be the event that

I_{i}

is rejected in the pruning phase. Let

E_{\in}

be the event that at least one of the intervals in

A

is selected in the first phase. Note that

E_{1}

can happen only if

E_{2}

happens. Thus

P [E_{1}] \leq P [E_{2}]

. In general we try to upper bound

P [E_{2}]

. In this simple case we have an exact formula for it.

P [E_{2}] = 1 - \prod_{j \in A} P [Y_{j} = 0] = 1 - \prod_{j \in A} (1 - x_{j} / 2) .

We claim that

P [E_{2}] \leq \sum_{j \in A} x_{j} / 2 \leq 1 / 2

. One can derive this by showing that

\prod_{j \in A} (1 - x_{j} / 2)

subject to

\sum_{j \in A} x_{j} / 2 \leq 1 / 2

is at least

1 / 2

. Another way of doing this is via Markov's inequality. Let

T = \sum_{j \in A} Y_{j}

be the number of intervals from

A

selected in the first phase.

E [T] \leq \sum_{j \in A} x_{j} / 2 < 1 / 2

. By Markov's inequality

P [T \geq 2 E [T]] \leq 1 / 2

E_{2}

is the event that

P [T \geq 1]

Using the claim,

P [Z_{i} = 1 ∣ Y_{i} = 1] = 1 - P [Z_{i} = 0 ∣ Y_{i} = 1] \geq 1 / 2 .

This allows us to lower bound the expected weight of the solution output by the algorithm, and yields a randomized

1 / 4

approximation.

Claim 4.3.3.

E [w (S)] \geq \sum_{i} w_{i} x_{i} / 4

Proof. We have

E [w (S)] = \sum_{i} w_{i} P [Z_{i} = 1] = \sum_{i} w_{i} P [Y_{i} = 1] P [Z_{i} = 1 ∣ Y_{i} = 1] \geq \sum_{i} w_{i} (\frac{x_{i}}{4} \cdot \frac{1}{2}) \geq \sum_{i} w_{i} x_{i} / 4 .

This type of rounding has applications to a variety of settings - see

[C V Z]

for applications and the general framework called contention resolution schemes.

4.4 Packing Integer Programs (PIPs)

We can express the Knapsack problem as the following integer program. We scaled the knapsack capacity to

1

without loss of generality.

\begin{aligned} maximize \sum_{i = 1}^{n} p_{i} x_{i} \\ subject to \sum_{i} s_{i} x_{i} & \leq 1 \\ x_{i} & \in {0, 1} 1 \leq i \leq n \end{aligned}

More generally if have multiple linear constraints on the "items" we obtain the following integer program.

Definition 4.7. A packing integer program (

PIP

) is an integer program of the form

max {w x ∣ A x \leq 1, x \in {0, 1}^{n}}

where

w

is a

1 \times n

non-negative vector and

A

is a

m \times n

matrix with entries in

[0, 1]

. We call it a

{0, 1} - PIP

if all entries are in

{0, 1}

In some cases it is useful/natural to define the problem as

max {w x ∣ A x \leq

b, x \in {0, 1}^{n}}

where entries in

A

and

b

are required to rational/integer valued. We can convert it into the above form by dividing each row of

A

b_{i}

When

m

the number of rows of

A

(equivalently the constraints) is small the problem is tractable. It is some times called the

m

-dimensional knapsack and one can obtain a

PTAS

for any fixed constant

m

. However, when

m

is large we observe that

MIS

can be cast as a special case of

{0, 1} - PIP

. It corresponds exactly to the simple integer/linear program that we saw in the previous section. Therefore the problem is at least as hard to approximate as

MIS

. Here we show via a clever

LP

-rounding idea that one can generalize the notion of bounded-degree to column-sparsity in

PIP

s and obtain a related approximation. We will then introduce the notion of width of the constraints and show how it allows for improved bounds.

Definition 4.8. A PIP is

k

-column-sparse if the number of non-zero entries in each column of

A

is at most

k

. A PIP has width

W

max_{i, j} A_{i j} / b_{i} \leq 1 / W

4.4.1 Randomized Rounding with Alteration for PIPs

We saw that randomized rounding gave an

O (\log n)

approximation algorithm for the Set Cover problem which is a canonical covering problem. Here we will consider the use of randomized rounding for packing problems. Let

x

be an optimum fractional solution to the natural

LP

relaxation of a

PIP

where we replace the constraint

x \in {0, 1}^{n}

x \in [0, 1]^{n}

. Suppose we apply independent randomized rounding where we set

x_{i}^{'}

1

with probability

x_{i}

. Let

x^{'}

be the resulting integer solution. The expected weight of this solution is exactly

\sum_{i} w_{i} x_{i}

which is the

LP

solution value. However,

x^{'}

may not satisfy the constraints given by

A x \leq b

. A natural strategy to try to satisfy the constraints is to set

x_{1}^{'}

1

with probability

c x_{i}

where

c < 1

is some scaling constant. This may help in satisfying the constraints because the scaling creates some room in the constraints; we now have that the expected solution value is

c \sum_{i} w_{i} x_{i}

, a loss of a factor of

c

. Scaling by itself does not allow us to claim that all constraints are satisfied with good probability. A very useful technique in this context is the technique of alteration; we judiciously fix/alter the rounded solution

x^{'}

to force it to satisfy the constraints by setting some of the variables that are

1

x^{'}

0

. The trick is to do this in such a way as to have a handle on the final probability that a variable is set to

1

. We will illustrate this for the Knapsack problem and then generalize the idea to

k

-sparse

PIP

s. The algorithms we present are from^[6]. See

[C V Z]

for further applications and related problems.

Rounding for Knapsack: Consider the Knapsack problem. It is convenient to think of this in the context of

PIP

s. So we have

a x \leq 1

where

a_{i}

now represents the size of item

i

and the knapsack capacity is

1; w_{i}

is the weight of item. Suppose

x

is a fractional solution. Call an item

i

"big" if

a_{i} > 1 / 2

and otherwise it is "small". Let

S

be the indices of small items and

B

the indices of the big items. Consider the following rounding algorithm.

\underline{Rounding-With-Alteration For Knapsack}

Let $x$ be an optimum fractional solution
Round each $i$ to $1$ independently with probability $x_{i} / 4$ . Let $x^{'}$ be rounded solution.
$x^{''} = x^{'}$
If $(x_{i}^{'} = 1$ for exactly one big item $i)$

A.For each $j \neq i$ set $x_{j}^{''} = 0$

Else If $(\sum_{i \in S} s_{i} x_{i}^{'} > 1$ or two or more big items are chosen in $x^{'})$

A.For each $j$ set $x_{j}^{''} = 0$

Output feasible solution $x^{''}$

In words, the algorithm alters the rounded solution

x^{'}

as follows. If exactly one big item is chosen in

x^{'}

then the algorithm retains that item and rejects all the other small items. Otherwise, the algorithm rejects all items if two or more big items are chosen in

x^{'}

or if the total size of all small items chosen in

x^{'}

exceeds the capacity.

The following claim is easy to verify.

Claim 4.4.1. The integer solution

x^{''}

is feasible.

Now let us analyze the probability of an item

i

being present in the final solution. Let

E_{1}

be the event that

\sum_{i \in S} a_{i} x_{i}^{'} > 1

, that is the sum of the sizes of the small items chose in

x^{'}

exceeds the capacity. Let

E_{2}

be the event that at least one big item is chosen in

x^{'}

Claim 4.4.2.

P [E_{1}] \leq 1 / 4

Proof. Let

X_{s} = \sum_{i \in S} a_{i} x_{i}^{'}

be the random variable that measures the sum of the sizes of the small items chosen. We have, by linearity of expectation, that

E [X_{s}] = \sum_{i \in S} a_{i} E [x_{i}^{'}] = \sum_{i \in S} a_{i} x_{i} / 4 \leq 1 / 4 .

By Markov's inequality,

P [X_{s} > 1] \leq E [X_{s}] / 1 \leq 1 / 4

Claim 4.4.3.

P [E_{2}] \leq 1 / 2

Proof. Since the size of each big item in

B

is at least

1 / 2

, we have

1 \geq \sum_{i \in B} a_{i} x_{i} \geq

\sum_{i \in B} x_{i} / 2

. Therefore

\sum_{i \in B} x_{i} / 4 \leq 1 / 2

. Event

E_{2}

happens if some item

i \in B

is chosen in the random selection. Since

i

is chosen with probability

x_{i} / 4

, by the union bound,

P [E_{2}] \leq \sum_{i \in B} x_{i} / 4 \leq 1 / 2

Lemma 4.2. Let

Z_{i}

be the indicator random variable that is

1

x_{i}^{''} = 1

and

0

otherwise. Then

E [Z_{i}] = P [Z_{i} = 1] \geq x_{i} / 16

Proof. We consider the binary random variable

X_{i}

which is

1

x_{i}^{'} = 1

. We have

E [X_{i}] = P [X_{i} = 1] = x_{i} / 4

. We write

P [Z_{i} = 1] = P [X_{i} = 1] \cdot P [Z_{i} = 1 ∣ X_{i} = 1] = \frac{x_{i}}{4} P [Z_{i} = 1 ∣ X_{i} = 1] .

To lower bound

P [Z_{i} = 1 ∣ X_{i} = 1]

we upper bound the probability

P [Z_{i} =

0 ∣ X_{i} = 1]

, that is, the probability that we reject

i

conditioned on the fact that it is chosen in the random solution

x^{'}

First consider a big item

i

that is chosen in

x^{'}

. Then

i

is rejected iff if another big item is chosen in

x^{'}

; the probability of this can be upper bounded by

P [E_{1}]

. If item

i

is small then it is rejected if and only if

E_{2}

happens or if a big item is chosen which happens with

P [E_{1}]

. In either case

P [Z_{i} = 0 ∣ X_{i} = 1] \leq P [E_{1}] + P [E_{2}] \leq 1 / 4 + 1 / 2 = 3 / 4 .

Thus,

P [Z_{i} = 1] = P [X_{i} = 1] \cdot P [Z_{i} = 1 ∣ X_{i} = 1] = \frac{x_{i}}{4} (1 - P [Z_{i} = 0 ∣ X_{i} = 1]) \geq \frac{x_{i}}{16} .

One can improve the above analysis to show that

P [Z_{i} = 1] \geq x_{i} / 8

Theorem 4.9. The randomized algorithm outputs a feasible solution of expected weight at least

\sum_{i = 1}^{n} w_{i} x_{i} / 16

Proof. The expected weight of the output is

E [\sum_{i} w_{i} x_{i}^{''}] = \sum_{i} w_{i} E [Z_{i}] \geq \sum_{i} w_{i} x_{i} / 16

where we used the previous lemma to lower bound

E [Z_{i}]

Rounding for

k

-sparse PIPs: We now extend the rounding algorithm and analysis above to

k

-sparse PIPs. Let

x

be a feasible fractional solution to

max {w x ∣ A x \leq 1, x \in [0, 1]^{n}}

. For a column index

i

we let

N (i) = {j ∣ A_{j, i} > 0}

be the indices of the rows in which

i

has a non-zero entry. Since

A

k

column-sparse we have that

| N (i) | \leq k

for

1 \leq i \leq n

. When we have more than one constraint we cannot classify an item/index

i

as big or small since it may be big for some constraints and small for others. We say that

i

is small for constraint

j \in N (i)

A_{j, i} \leq 1 / 2

otherwise

i

is big for constraint

j

. Let

S_{j} = {i ∣ j \in N (i)

, and

i

small for

j}

be the set of all small columns for

j

and

B_{j} = {i ∣ j \in N (i)

, and

i

small for

j}

be the set of all big columns for

j

. Note that

S_{j} \cap B_{j}

is the set of all

i

with

A_{j, i} > 0

\underline{ROUNDING-WITH-ALTERATION FOR k -SPARSE PIPs}

Let $x$ be an optimum fractional solution
Round each $i$ to 1 independently with probability $x_{i} / (4 k)$ . Let $x^{'}$ be rounded solution.
$x^{''} = x^{'}$
For $j = 1$ to $m$ do

A.If $(x_{i}^{'} = 1$ for exactly one $i \in B_{j})$ 1. For each $h \in S_{j} \cup B_{j}$ and $h \neq i$ set $x_{h}^{''} = 0$
B.Else If $(\sum_{i \in S_{j}} A_{j, i} x_{i}^{'} > 1$ or two or more items from $B_{j}$ are chosen in $x^{'})$ 1. For each $h \in S_{j} \cup B_{j}$ set $x_{h}^{''} = 0$

Output feasible solution $x^{''}$

The algorithm, after picking the random solution

x^{'}

, alters it as follows: it applies the previous algorithm's strategy to each constraint

j

separately. Thus an element

i

can be rejected at different constraints

j \in N (i)

. We need to bound the total probability of rejection. As before, the following claim is easy to verify.

Claim 4.4.4. The integer solution

x^{''}

is feasible.

Now let us analyze the probability of an item

i

being present in the final solution. Let

E_{1} (j)

be the event that

\sum_{i \in S_{j}} A_{j, i} x_{i}^{'} > 1

, that is the sum of the sizes of the items that are small for

j

x^{'}

exceed the capacity. Let

E_{2} (j)

be the event that at least one big item for

j

is chosen in

x^{'}

. The following claims follow from the same reasoning as the ones before with the only change being the scaling factor.

Claim 4.4.5.

P [E_{1} (j)] \leq 1 / (4 k)

Claim 4.4.6.

P [E_{2} (j)] \leq 1 / (2 k)

Lemma 4.3. Let

Z_{i}

be the indicator random variable that is

1

x_{i}^{''} = 1

and

0

otherwise. Then

E [Z_{i}] = P [Z_{i} = 1] \geq x_{i} / (16 k)

Proof. We consider the binary random variable

X_{i}

which is

1

x_{i}^{'} = 1

after the randomized rounding. We have

E [X_{i}] = P [X_{i} = 1] = x_{i} / (4 k)

. We write

P [Z_{i} = 1] = P [X_{i} = 1] \cdot P [Z_{i} = 1 ∣ X_{i} = 1] = \frac{x_{i}}{4 k} P [Z_{i} = 1 ∣ X_{i} = 1] .

We upper bound the probability

P [Z_{i} = 0 ∣ X_{i} = 1]

, that is, the probability that we reject

i

conditioned on the fact that it is chosen in the random solution

x^{'}

. We observe that

P [Z_{i} = 0 ∣ X_{i} = 1] \leq \sum_{j \in N (i)} (P [E_{1} (j)] + P [E_{2} (j)] \leq k (1 / (4 k) + 1 / (2 k)) \leq 3 / 4 .

We used the fact that

N (i) \leq k

and the claims above. Therefore,

P [Z_{i} = 1] = P [X_{i} = 1] \cdot P [Z_{i} = 1 ∣ X_{i} = 1] = \frac{x_{i}}{4 k} (1 - P [Z_{i} = 0 ∣ X_{i} = 1]) \geq \frac{x_{i}}{16 k} .

The theorem below follows by using the above lemma and linearity of expectation to compare the expected weight of the output of the randomized algorithm with that of the fractional solution.

Theorem 4.10. The randomized algorithm outputs a feasible solution of expected weight at least

\sum_{i = 1}^{n} w_{i} x_{i} / (16 k)

. There is

1 / (16 k)

-approximation for

k

-sparse PIPs.

Larger width helps: We saw during the discussion on the Knapsack problem that if all items are small with respect to the capacity constraint then one can obtain better approximations. For

PIP

s we defined the width of a given instance as

W

max_{i, j} A_{i j} / b_{i} \leq 1 / W

; in other words no single item is more than

1 / W

times the capacity of any constraint. One can show using a very similar algorithm and anaylisis as above that the approximation bound improves to

Ω (1 / k^{[W]})

for instance with width

W

. Thus if

W = 2

we get a

Ω (1 / \sqrt{k})

approximation instead of

Ω (1 / k)

-approximation. More generally when

W \geq c \log k / ϵ

for some sufficiently large constant

c

we can get a

(1 - ϵ)

-approximation. Thus, in the setting with multiple knapsack constraints, the notion of small with respect to capacities is that in each constraint the size of the item is

\leq \frac{c ϵ}{\log k}

times the capacity of that constraint.

Johan Hastad. “Clique is hard to approximate within n/sup 1-/spl epsiv”. In: Proceedings of 37th Conference on Foundations of Computer Science. IEEE. 1996, pp. 627–636. ↩︎
Karhan Akcoglu, James Aspnes, Bhaskar DasGupta, and Ming-Yang Kao. “Opportunity cost algorithms for combinatorial auctions”. In: Computational Methods in Decision-Making, Economics and Finance. Springer, 2002, pp. 455–479. ↩︎ ↩︎
Yuli Ye and Allan Borodin. “Elimination graphs”. In: ACM Transactions on Algorithms (TALG) 8.2 (2012), pp. 1–23. ↩︎ ↩︎ ↩︎ ↩︎
Moran Feldman, Joseph Seffi Naor, Roy Schwartz, and Justin Ward. “Improved approximations for k-exchange systems”. In: European Symposium on Algorithms. Springer. 2011, pp. 784–798. ↩︎
Julián Mestre. “Greedy in approximation algorithms”. In: European Symposium on Algorithms. Springer. 2006, pp. 528–539. ↩︎
Nikhil Bansal, Nitish Korula, Viswanath Nagarajan, and Aravind Srinivasan. “Solving packing integer programs via randomized rounding with alterations”. In: Theory of Computing 8.1 (2012), pp. 533–565. ↩︎

Approximation Algorithms: Packing Problems

4.1 Maximum Independent Set Problem in Graphs

4.1.1 Elimination Orders and MIS

4.2 The efficacy of the Greedy algorithm for a class of Independence Families

4.3 Randomized Rounding with Alteration for Packing Problems

4.4 Packing Integer Programs (PIPs)

4.4.1 Randomized Rounding with Alteration for PIPs

Recommended for you

Report Article