讲解CIS 410/510、辅导java/Python设计、讲解integer program、辅导Python/CS

Assignment 4

CIS 410/510: Selected Topics on Optimization

Problem 1 (10 points) For the graph G = (U, E), where U is the set of vertices and E is the set of edges, we

define the following nonlinear integer program, where wi,j ≥ 0, ?(i, j) ∈ E and k is a nonnegative integer:

max

(i,j)∈E

wi,j (xi + xj 2xixj )

s.t.

i∈U

xi = k ,

xi ∈ {0, 1}, i ∈ U .

Show that the following linear program is a relaxation of the above problem:

max

(i,j)∈E

wi,jzi,j

s.t. zi,j ≤ xi + xj , (i, j) ∈ E ,

zi,j ≤ 2 xi xj , (i, j) ∈ E ,

i∈U

xi = k ,

0 ≤ xi ≤ 1, i ∈ U ,

0 ≤ zi,j ≤ 1, (i, j) ∈ E .

Let F(x) = (i,j)∈E wi,j (xi + xj 2xixj ) be the objective function of the nonlinear integer program. Show

that for any (x, z) that is feasible to the linear program, F(x) ≥ 1

(i,j)∈E wi,jzi,j .

Show that for a given fractional solution x, using “pipage rounding” to convert fractional variables xi and xj

into integers does not decrease F(x), and also, based on this and the above arguments, design a 1

2 -approximation

algorithm for the nonlinear integer program.

Problem 2 (10 points) For the directed graph G = (U, E), where U is the set of vertices and E is the set of

directed edges, we want to partition U into two sets V and W = U \ V in order to maximize the total weight of

the edges going from V to W (i.e., the edges (i, j) with i ∈ V and j ∈ W).

Give a randomized 1

4 -approximation algorithm for this problem.

Show that the following linear program is a relaxation of this problem:

max

(i,j)∈E

wi,jzi,j

s.t. zi,j ≤ xi, (i, j) ∈ E ,

zi,j ≤ 1 xj , (i, j) ∈ E ,

0 ≤ xi ≤ 1, i ∈ U ,

0 ≤ zi,j ≤ 1, (i, j) ∈ E .

For the above linear program, give a randomized 1

2 -approximation algorithm based on rounding xi, ?i ∈ U to

1 with the probability of 1

2xi + 1

4 .