Linear Programming Outline 1 Linear Programming Formulate Set Cover Problem Solving Linear Programs 2 Rounding of LP Set Cover 3 Primal-Dual Schema Se...

0 downloads 2 Views 316KB Size

Loading...

Oct.09, 2012

Chihao Zhang ([email protected])

Linear Programming & Primal-Dual Schema

Oct.09, 2012

1 / 32

Linear Programming

Outline

1

Linear Programming Formulate Set Cover Problem Solving Linear Programs

2

Rounding of LP Set Cover

3

Primal-Dual Schema Set Cover Feedback Vertex Set

Chihao Zhang ([email protected])

Linear Programming & Primal-Dual Schema

Oct.09, 2012

2 / 32

Linear Programming

Formulate Set Cover Problem

Example:Set Cover

Input:

Problem:

A Universe E = {e1 , . . . , en }; a family of subsets S1 , . . . , Sm where each Sj ⊆ E ; a nonnegative weight wj ≥ 0 for each Sj . Find a minimum-weight collection of subsets that covers all of E

Chihao Zhang ([email protected])

Linear Programming & Primal-Dual Schema

Oct.09, 2012

3 / 32

Linear Programming

Formulate Set Cover Problem

Integer Program

minimize

m P

wj xj

j=1

subject to

P

xj ≥ 1, i = 1, . . . , n,

j:ei ∈Sj

xj ∈ {0, 1},

xj ∈ {0, 1} :

Chihao Zhang ([email protected])

j = 1, . . . , m.

indicate whether Sj is in the solution.

Linear Programming & Primal-Dual Schema

Oct.09, 2012

4 / 32

Linear Programming

Formulate Set Cover Problem

Linear Program Relaxation

minimize

m P

wj xj

j=1

subject to

P

xj ≥ 1, i = 1, . . . , n,

j:ei ∈Sj

xj ≥ 0,

Chihao Zhang ([email protected])

j = 1, . . . , m.

Linear Programming & Primal-Dual Schema

Oct.09, 2012

5 / 32

Linear Programming

Solving Linear Programs

Canonical Form

maximize cT x subject to A x ≤ b x≥0 A = (ai,j ) :

An m × n matrix

b = (b1 , . . . , bm ) :

A vector of m entries

c = (c1 , . . . , cn ) :

A vector of n entries

Chihao Zhang ([email protected])

Linear Programming & Primal-Dual Schema

Oct.09, 2012

6 / 32

Linear Programming

Solving Linear Programs

Canonical Form

maximize cT x subject to A x ≤ b x≥0 A = (ai,j ) :

An m × n matrix

b = (b1 , . . . , bm ) :

A vector of m entries

c = (c1 , . . . , cn ) :

A vector of n entries

Every LP can be transformed to canonical form efficiently. Chihao Zhang ([email protected])

Linear Programming & Primal-Dual Schema

Oct.09, 2012

6 / 32

Linear Programming

Solving Linear Programs

Algorithms to Solve LP

Simplex Algorithm Ellipsoid Method

Chihao Zhang ([email protected])

Linear Programming & Primal-Dual Schema

Oct.09, 2012

7 / 32

Linear Programming

Solving Linear Programs

Dual of Linear Program

Consider the following linear program:

maximize x1 + 6x2 x1 ≤ 200 (1) x2 ≤ 300 (2) x1 + x2 ≤ 400 (3) x1 , x2 ≥ 0

Chihao Zhang ([email protected])

Linear Programming & Primal-Dual Schema

Oct.09, 2012

8 / 32

Linear Programming

Solving Linear Programs

Dual of Linear Program

Consider the following linear program:

maximize x1 + 6x2 x1 ≤ 200 (1) x2 ≤ 300 (2) x1 + x2 ≤ 400 (3) x1 , x2 ≥ 0 The optimal solution is at (x1 , x2 ) = (100, 300), with objective value 1900.

Chihao Zhang ([email protected])

Linear Programming & Primal-Dual Schema

Oct.09, 2012

8 / 32

Linear Programming

Solving Linear Programs

Dual of Linear Program (cont’d)

(1) + 6 × (2) :

Chihao Zhang ([email protected])

x1 + 6x2 ≤ 2000.

Linear Programming & Primal-Dual Schema

Oct.09, 2012

9 / 32

Linear Programming

Solving Linear Programs

Dual of Linear Program (cont’d)

(1) + 6 × (2) :

x1 + 6x2 ≤ 2000.

0 × (1) + 5 × (2) + 1 × (3) :

x1 + 6x2 ≤ 1900

Chihao Zhang ([email protected])

Linear Programming & Primal-Dual Schema

Oct.09, 2012

9 / 32

Linear Programming

Solving Linear Programs

Dual of Linear Program (cont’d)

(1) + 6 × (2) :

x1 + 6x2 ≤ 2000.

0 × (1) + 5 × (2) + 1 × (3) :

x1 + 6x2 ≤ 1900

Multiplier y1 y2 y3

Chihao Zhang ([email protected])

x1 x1

Inequality ≤ x2 ≤ + x2 ≤

Linear Programming & Primal-Dual Schema

200 300 400

Oct.09, 2012

9 / 32

Linear Programming

Solving Linear Programs

Dual of Linear Program (cont’d)

minimize 200y1 + 300y2 + 400y3 y1 + y3 ≥ 1 y2 + y3 ≥ 6 y1 , y2 , y3 ≥ 0

Chihao Zhang ([email protected])

Linear Programming & Primal-Dual Schema

Oct.09, 2012

10 / 32

Linear Programming

Solving Linear Programs

Dual of Linear Program (cont’d)

Dual LP:

Primal LP:

minimize yT b

maximize cT x Ax ≤ b x≥0

Chihao Zhang ([email protected])

Linear Programming & Primal-Dual Schema

y T A ≥ cT y≥0

Oct.09, 2012

11 / 32

Linear Programming

Solving Linear Programs

Dual of Linear Program (cont’d)

Dual LP:

Primal LP:

minimize yT b

maximize cT x

y T A ≥ cT y≥0

Ax ≤ b x≥0 weak duality property: cT x ≤ y T b

Chihao Zhang ([email protected])

Linear Programming & Primal-Dual Schema

Oct.09, 2012

11 / 32

Linear Programming

Solving Linear Programs

Dual of Linear Program (cont’d)

Dual LP:

Primal LP:

minimize yT b

maximize cT x

y T A ≥ cT y≥0

Ax ≤ b x≥0 strong duality property: cT x∗ = (y∗ )T b

Chihao Zhang ([email protected])

Linear Programming & Primal-Dual Schema

Oct.09, 2012

11 / 32

Rounding of LP

Outline

1

Linear Programming Formulate Set Cover Problem Solving Linear Programs

2

Rounding of LP Set Cover

3

Primal-Dual Schema Set Cover Feedback Vertex Set

Chihao Zhang ([email protected])

Linear Programming & Primal-Dual Schema

Oct.09, 2012

12 / 32

Rounding of LP

Set Cover

A Simple Rounding Algorithm for Set Cover

Recall the linear programming relaxation for set cover:

minimize

Pm

subject to

P

j=1

wj xj

j:ei ∈Sj

xj ≥ 0,

Chihao Zhang ([email protected])

xj ≥ 1, i = 1, . . . , n, j = 1, . . . , m.

Linear Programming & Primal-Dual Schema

Oct.09, 2012

13 / 32

Rounding of LP

Set Cover

A Simple Rounding Algorithm for Set Cover

Recall the linear programming relaxation for set cover:

minimize

Pm

subject to

P

j=1

wj xj

j:ei ∈Sj

xj ≥ 0,

xj ≥ 1, i = 1, . . . , n, j = 1, . . . , m.

Consider the optimal solution of the LP. Intuitively, the set with larger xj is more likely to be in a good solution of set cover (or the IP).

Chihao Zhang ([email protected])

Linear Programming & Primal-Dual Schema

Oct.09, 2012

13 / 32

Rounding of LP

Set Cover

A Simple Rounding Algorithm for Set Cover (cont’d)

1. Let x∗ be the solution of LP. 2. Let I = {j | xj∗ ≥ 1/f }, where f = max |{j | ei ∈ Sj }|. i=1,...,n

3. Output I .

Chihao Zhang ([email protected])

Linear Programming & Primal-Dual Schema

Oct.09, 2012

14 / 32

Rounding of LP

Set Cover

A Simple Rounding Algorithm for Set Cover (cont’d)

1. Let x∗ be the solution of LP. 2. Let I = {j | xj∗ ≥ 1/f }, where f = max |{j | ei ∈ Sj }|. i=1,...,n

3. Output I . Lemma S is a set cover.

Chihao Zhang ([email protected])

Linear Programming & Primal-Dual Schema

Oct.09, 2012

14 / 32

Rounding of LP

Set Cover

Analysis Lemma The rounding algorithm is an f -approximation algorithm for the set cover problem.

Chihao Zhang ([email protected])

Linear Programming & Primal-Dual Schema

Oct.09, 2012

15 / 32

Rounding of LP

Set Cover

Analysis Lemma The rounding algorithm is an f -approximation algorithm for the set cover problem.

X j∈I

wj ≤

m X

wj · (f · xj∗ )

j=1 m X

=f

wj xj∗

j=1

= f · OPT

Chihao Zhang ([email protected])

Linear Programming & Primal-Dual Schema

Oct.09, 2012

15 / 32

Primal-Dual Schema

Outline

1

Linear Programming Formulate Set Cover Problem Solving Linear Programs

2

Rounding of LP Set Cover

3

Primal-Dual Schema Set Cover Feedback Vertex Set

Chihao Zhang ([email protected])

Linear Programming & Primal-Dual Schema

Oct.09, 2012

16 / 32

Primal-Dual Schema

Set Cover

A Primal-Dual Algorithm for Set Cover Recall the LP relaxation for Set Cover:

minimize

Pm

subject to

P

j=1

wj xj

j:ei ∈Sj

xj ≥ 0,

xj ≥ 1, i = 1, . . . , n, j = 1, . . . , m.

and its dual:

maximize

Pn

subject to

P

i=1 yi

i:ei ∈Sj

yi ≥ 0, Chihao Zhang ([email protected])

yi ≤ wj , j = 1, . . . , m, i = 1, . . . , n.

Linear Programming & Primal-Dual Schema

Oct.09, 2012

17 / 32

Primal-Dual Schema

Set Cover

Vertex Cover

Vertex cover problem is the special case of set cover problem when f = 2.

Chihao Zhang ([email protected])

Linear Programming & Primal-Dual Schema

Oct.09, 2012

18 / 32

Primal-Dual Schema

Set Cover

Vertex Cover

Vertex cover problem is the special case of set cover problem when f = 2. The dual of vertex cover problem is maximum matching problem.

Chihao Zhang ([email protected])

Linear Programming & Primal-Dual Schema

Oct.09, 2012

18 / 32

Primal-Dual Schema

Set Cover

Vertex Cover

Vertex cover problem is the special case of set cover problem when f = 2. The dual of vertex cover problem is maximum matching problem. The duality theorem implies maximum matching ≤ minimum vertex cover

Chihao Zhang ([email protected])

Linear Programming & Primal-Dual Schema

Oct.09, 2012

18 / 32

Primal-Dual Schema

Set Cover

Vertex Cover (cont’d)

Consider the following algorithm:

1. M ← ∅ 2. S ← ∅ 3. while G is not empty do 3.1 Choose an edge e = {u, v } ∈ E (G ) and let M ← M ∪ {e} 3.2 S ← S ∪ {u, v } 3.3 G ← G [V \ {u, v }] (Remove isolated nodes)

4. return S

Chihao Zhang ([email protected])

Linear Programming & Primal-Dual Schema

Oct.09, 2012

19 / 32

Primal-Dual Schema

Set Cover

Vertex Cover (cont’d)

Consider the following algorithm:

1. M ← ∅ 2. S ← ∅ 3. while G is not empty do 3.1 Choose an edge e = {u, v } ∈ E (G ) and let M ← M ∪ {e} 3.2 S ← S ∪ {u, v } 3.3 G ← G [V \ {u, v }] (Remove isolated nodes)

4. return S This is the combinatorial interpretation of a primal-dual algorithm.

Chihao Zhang ([email protected])

Linear Programming & Primal-Dual Schema

Oct.09, 2012

19 / 32

Primal-Dual Schema

Set Cover

The Algorithm

1. y ← 0 2. I ← ∅ S 3. while there exists ei 6∈ Sj do j∈I

3.1 Increase the dual variable yi until there is some ` such that P yj = w ` j:ej ∈S`

3.2 I ← I ∪ {`}

4. return I .

Chihao Zhang ([email protected])

Linear Programming & Primal-Dual Schema

Oct.09, 2012

20 / 32

Primal-Dual Schema

Set Cover

Analysis

The primal-dual algorithm is an f -approximation algorithm for the set cover problem.

Chihao Zhang ([email protected])

Linear Programming & Primal-Dual Schema

Oct.09, 2012

21 / 32

Primal-Dual Schema

Set Cover

Analysis

The primal-dual algorithm is an f -approximation algorithm for the set cover problem. X X X wj = yi j∈I i:ei ∈Sj

j∈I

=

n X

yi · |{j ∈ I | ei ∈ Sj }|

i=1

≤ f · OPT

Chihao Zhang ([email protected])

Linear Programming & Primal-Dual Schema

Oct.09, 2012

21 / 32

Primal-Dual Schema

Set Cover

Complementary Slackness

The following property is called complementary slackness. n X

yi ≤

i=1

Chihao Zhang ([email protected])

n X i=1

yi

X j:ei ∈Sj

xj =

m X j=1

xj

X

yi ≤

i:ei ∈Sj

Linear Programming & Primal-Dual Schema

m X

xj wj .

j=1

Oct.09, 2012

22 / 32

Primal-Dual Schema

Set Cover

Complementary Slackness

The following property is called complementary slackness. n X

yi ≤

i=1

n X i=1

yi

X

xj =

j:ei ∈Sj

m X j=1

xj

X

yi ≤

i:ei ∈Sj

m X

xj wj .

j=1

Let x ∗ and y ∗ be the optimal solution of primal and dual LP respectively, then P ∗ xj = 1, yi∗ > 0 =⇒ j:ei ∈Sj

xj∗

> 0 =⇒

P i:ei ∈Sj

Chihao Zhang ([email protected])

yi∗ = wj .

Linear Programming & Primal-Dual Schema

Oct.09, 2012

22 / 32

Primal-Dual Schema

Set Cover

Analysis (revisited)

X

wj =

X X

yi

j∈I i:ei ∈Sj

j∈I

=

n X

yi · |{j ∈ I | ei ∈ Sj }|

i=1

≤ f · OPT

Chihao Zhang ([email protected])

Linear Programming & Primal-Dual Schema

Oct.09, 2012

23 / 32

Primal-Dual Schema

Set Cover

Analysis (revisited)

X

wj =

X X

yi

j∈I i:ei ∈Sj

j∈I

=

n X

yi · |{j ∈ I | ei ∈ Sj }|

i=1

=

n X i=1

yi ·

X

xj

j:ei ∈Sj

≤ f · OPT where xj ∈ {0, 1} and xj = 1 if and only if j ∈ I .

Chihao Zhang ([email protected])

Linear Programming & Primal-Dual Schema

Oct.09, 2012

23 / 32

Primal-Dual Schema

Set Cover

Discussion The primal-dual algorithm ensures xj > 0 =⇒

X

yi = wj

i:ei ∈Sj

Chihao Zhang ([email protected])

Linear Programming & Primal-Dual Schema

Oct.09, 2012

24 / 32

Primal-Dual Schema

Set Cover

Discussion The primal-dual algorithm ensures xj > 0 =⇒

X

yi = wj

i:ei ∈Sj

In general, we cannot hope yi > 0 =⇒

X

xj = 1

j:ei ∈Sj

Chihao Zhang ([email protected])

Linear Programming & Primal-Dual Schema

Oct.09, 2012

24 / 32

Primal-Dual Schema

Set Cover

Discussion The primal-dual algorithm ensures xj > 0 =⇒

X

yi = wj

i:ei ∈Sj

In general, we cannot hope yi > 0 =⇒

X

xj = 1

j:ei ∈Sj

We want to show it is not too slack, i.e. X yi > 0 =⇒ xj ≤ α j:ei ∈Sj

Chihao Zhang ([email protected])

Linear Programming & Primal-Dual Schema

Oct.09, 2012

24 / 32

Primal-Dual Schema

Feedback Vertex Set

Feedback Vertex Set Problem

Input: Problem:

A undirected graph G = (V , E ) and nonnegative weights wi > 0 for i ∈ V . Find a set S ⊆ V of minimum weight such that G [V \ S] is a forest

Chihao Zhang ([email protected])

Linear Programming & Primal-Dual Schema

Oct.09, 2012

25 / 32

Primal-Dual Schema

Feedback Vertex Set

LP formulation

minimize

P

wi xi

i∈V

subject to

P

xi ≥ 1,

∀C ∈ C

i∈C

xi ∈ {0, 1}, ∀i ∈ V

xi ∈ {0, 1} :

Chihao Zhang ([email protected])

indicate whether vi is in the solution.

Linear Programming & Primal-Dual Schema

Oct.09, 2012

26 / 32

Primal-Dual Schema

Feedback Vertex Set

LP formulation

minimize

P

wi xi

i∈V

subject to

P

xi ≥ 1, ∀C ∈ C

i∈C

xi ≥ 0,

xi ∈ {0, 1} :

Chihao Zhang ([email protected])

∀i ∈ V

indicate whether vi is in the solution.

Linear Programming & Primal-Dual Schema

Oct.09, 2012

26 / 32

Primal-Dual Schema

Feedback Vertex Set

Dual LP

maximize

P

yC

C ∈C

subject to

P

yC ≤ wi , ∀i ∈ V ,

C ∈C:i∈C

yC ≥ 0,

Chihao Zhang ([email protected])

∀C ∈ C

Linear Programming & Primal-Dual Schema

Oct.09, 2012

27 / 32

Primal-Dual Schema

Feedback Vertex Set

The Algorithm

1. y ← 0 2. S ← ∅ 3. while there exists a cycle C in G do 3.1 Increase P yC until there is some ` ∈ V such that yC 0 = w ` C 0 ∈C:`∈C 0

3.2 S ← S ∪ {`} 3.3 Remove ` from G 3.4 Repeatedly remove vertices of degree one from G

4. return S.

Chihao Zhang ([email protected])

Linear Programming & Primal-Dual Schema

Oct.09, 2012

28 / 32

Primal-Dual Schema

Feedback Vertex Set

Analysis

X i∈S

Chihao Zhang ([email protected])

wi =

X X i∈S C :i∈C

yC =

X

|S ∩ C |yC .

C ∈C

Linear Programming & Primal-Dual Schema

Oct.09, 2012

29 / 32

Primal-Dual Schema

Feedback Vertex Set

Analysis

X i∈S

wi =

X X i∈S C :i∈C

yC =

X

|S ∩ C |yC .

C ∈C

|S ∩ C | may be as large as |V |!

Chihao Zhang ([email protected])

Linear Programming & Primal-Dual Schema

Oct.09, 2012

29 / 32

Primal-Dual Schema

Feedback Vertex Set

Analysis (cont’d)

Observation For any path P of vertices of degree two in graph G , our algorithm will choose at most one vertex from P.

Chihao Zhang ([email protected])

Linear Programming & Primal-Dual Schema

Oct.09, 2012

30 / 32

Primal-Dual Schema

Feedback Vertex Set

Analysis (cont’d)

Observation For any path P of vertices of degree two in graph G , our algorithm will choose at most one vertex from P. Theorem In any graph G that has no vertices of degree one, there is a cycle with at most 2blog2 nc vertices of degree three or more, and it can be found in linear time.

Chihao Zhang ([email protected])

Linear Programming & Primal-Dual Schema

Oct.09, 2012

30 / 32

Primal-Dual Schema

Feedback Vertex Set

Algorithm (revised)

1. 2. 3. 4.

y←0 S ←∅ Repeatedly remove vertices of degree one from G while there exists a cycle C in G do 4.1 Find cycle C with at most 2blog2 nc vertices of degree three or more 4.2 Increase P yC until there is some ` ∈ V such that yC 0 = w ` C 0 ∈C:`∈C 0

4.3 S ← S ∪ {`} 4.4 Remove ` from G 4.5 Repeatedly remove vertices of degree one from G

5. return S. Chihao Zhang ([email protected])

Linear Programming & Primal-Dual Schema

Oct.09, 2012

31 / 32

Primal-Dual Schema

Feedback Vertex Set

Analysis

X i∈S

wi =

X

|S ∩ C |yC ≤ (4blog2 nc)

C ∈C

Chihao Zhang ([email protected])

X

yC ≤ (4blog2 nc)OPT.

c∈C

Linear Programming & Primal-Dual Schema

Oct.09, 2012

32 / 32