COMS 482: unofficial class blog

Can’t get up at 8:00 AM to get to class? Do you keep falling asleep to the lullaby of “NP….?” Do you look like:

If you answered yes to any of the above, then this blog is for YOU! Get all your CS 482: Algorithms notes here, free, always!

In the previous lecture we showed an approximation to the Knapsack algorithm that is fast when v^* = max v_i is small. So, convert a knapsack problem into one where v^* is small by choosing b and converting v_i -> ceil(v_i/b). We want an answer within (1 + e) of the true value, so b = (e/n) * v^*.

Some approximation bounds so far:

• Makespan: 3/2, 4/3
• Center selection: 2
• Vertex cover: 2

The goal is to achieve a (1 + e) approximation.

Knapsack Problem:

We can carry at most W weight. We have n items to choose from, each with weight w_i and a value v_i. Our goal is to maximize value without exceeding weight boundary W. Using Dynamic Programming, we can define:

Opt(i, V) = smallest weight possible using items {1, …, i} and choosing value >= V.

Given the Opt(*, *) function and W, we can search the opt-table to find the largest V for which opt(n, V) <= W:

V = sum(v_i in S) <= sum(v_i for all i) <= nv^*, where v^* = max v_i

Therefore, the algorithm runs in time O(n²v^*).

Algorithm notes:

If the nth item is not in opt solution, then Opt(n, V) = Opt(n-1, V). If the nth item is in the optimal solution, then Opt(n, V) = w_n + Opt(n-1, V-V_n)–so, just take the minimum:

Opt(n, V) = min({Opt(n-1, V), w_n + Opt(n-1, V-V_n})

There are some table bounds to consider:

Opt(1, V) = w₁ if v₁ >= V, else infinity
Opt(k, 0) = 0
Opt(k, < 0) = 0

Finally, we can write the algorithm outline:

Knapsack0Approx(e):
    b = (e/n) * max(v_i)
    for all i v_i^{^} = ceil(v_i/b)
    solve problem with v_i^{^} via DP outline above
    return result set S

Let x_i be 0 if v_i is not in the Vertex Cover, and 1 if v_i is in the Vertex Cover. (v_i, v_j) is an edge such that x_i + x_j >= 1. We want to make the sum of all x_i as small as possible, and still cover the edges.

Linear Programming:

A set of linear inequalities define a feasible region, for example:

x + y >=0
x – y >= 0
x <= 5
y <= 2

Or, in matrix form:

[[1,1][1,-1][1,0][0,1]] * [[x][y]] >= [[0][0][-5][-2]]

The goal is to remain the feasible region while optimizing something. In general, given {Ax = b}, a set of linear inequalities, we want to minimize c*x, i.e. find the minimum {c*x | Ax >= b}. Geometrically, this is finding the extreme point of a polytope. We can write this as a decision problem, too. Given A, b, c, and a bound B, is there a solution x such that Ax >= b and c’*x <= B?

Claim: “LP is in NP”

Given a set of values, we can check the solution in polynomial time. Rational numbers, however, require additional book keeping. Beware! Also, LP is in Co-NP and in P, using an interior point method.

VC as a LP problem:

x_i >= 0
-x_i >= -1
x_i + x_j 7gt;= 1 for all (v_i, v_j)
minimize sum(x_i)

Then, run LP but only allow integer solutions. This is called “Integer Programming” (IP). Claim: “VC <=_p IP.” Rewrite VC as an IP problem, then the solution to one implies the other. Claim: “IP is in NP.” Obvious. Therefore, IP is NP-Complete.

Approximation:

Simply round the LP solution to get integers. S = {i | i >= 1/2}, our approximate vertex cover. Then, |S| = sum(i in S) <= sum(2*x_i in S) = s * sum(x_i in S) <= 2 * sum(x_i from i = 0 to n) <= 2 * |S*|. So, we are within a factor of two of the optimal solution.

Center Selection (CS): Given n towns, place k malls, minimizing the worst driving distance. The CS decision problem can be written: “Given n points, a radius r, and an integer k, can we place k disks of radius r so that all points are covered?”

dist(*,*) must satisfy:

• dist(s, s) = 0 (reflexive)
• dist(s, t) = dist(t, s) (symmetry)
• dist(s, u) <= dist(s, t) + dist(t, u) (triangle inequality)

CS_decision <=_p CS_optimization: Optimization is NP-hard!

Suppose that we know r and want to find a solution, i.e. choosing the centers. If we already know one of the centers, uf we were to use radius 2r then any point within distance r can be used as the center, and all points will still be covered. So, pick any point s in the disk; the circle with center s and radius 2r covers all the same points.

If there is a technique that produce an answer where radius <= (2 – epsilon)r*, then p = NP. In the plane, using Euclidean distance, if radius <= (1.89 …)r*, then P = NP.

Greedy Algorithm: Let S be the set of sites and C be the set of centers. We are given r.

C = {}
while S != {}
    choose s in S
    C = C + {s}
    delete all s’ in S within 2r of s
end
if |C| <= k return C
else report “No solution for radius r possible”

Claim: “If there is a solution using k radius-r disks, then the algorithm returns a solution using <= k disks of radius 2r.

Each s chosen by the algorithm is in some disk (c*, r) for some c*. Then the circle (s, 2r) covers all the same points covered by (c*, r) plus some more. Thus, later choices of s are not covered by the circle (c*, r). Each s chosen is covered by a different c* circle. There are at most |c*| = k choices for s. The algorithm produces <= k disks of radius 2r covering all points.

Method: Use a binary search to find the right radius. First, box the set of points and find the maximum seperation between any 2 points. This is R and r <= R. We can actually do better! During the algorithm we need a point at distance >= 2r from chosen site s. Always choose the fathest point. For later steps, choose s_i farthest from existing centers.

New algorithm:

Select any site s in S, let C = {s}
while |c| < k
    select s in S that maximizes that distance from s to any point in C
    C = C + {s}
end
return C

Claim: “If there’s a solution (C*_r, r) where |C*_r|=k, then the algorithm returns a solution (C, 2r) where |c| = k.

Consider the previous algorithm. We know there is an optimal value for r. Let’s use that r. Each s that is chosen in the new algorithm would be a valid s in the previous algorithm. This holds until we eliminate all points in S, therefore we produce a cover (C, 2r).

Credit to Kevin Canini for the notes!