next up previous
Next: About this document ...

`|= `@=


Applied Algorithms Anna Karlin, 426C Sieg
CSE 589, Autumn 2000

Homework # 6
Due November 10




1.
Prove that the first-fit algorithm for binpacking uses at most twice the optimal number of bins. (The binpacking problem: Let x1, x2,...,xn be a set of real numbers each between 0 and 1. Partition the numbers into as few subsets (bins) as possible so that the sum of numbers in each subset is at most one. The first-fit algorithm: Put x1 into the first bin, and then, for each i, put xi in the first bin that has room for it, or start a new bin if there is no room in any of the used bins and put xi in it.)

2.
Set Cover: An instance of the set cover problem consists of a finite set of elements X and a family $\cal F$ of subsets of X. (For example X could be elements {1,2,3,4,5} and $\cal F$ could be $(\{1,3\},\{1,2,4,5\},\{2,3\},\{2,5\})$. The set cover problem is to find a minimum-size subset $\cal C$ $\subseteq$ $\cal F$ whose members contain all the elements of X. (In the example, the first and second sets in $\cal F$ ( $\{1,3\},\{1,2,4,5\}$) form a set cover because all 5 elements are included in at least one of these sets.)

3.
Will not be graded. An Euler tour of a connected, undirected graph G=(V,E) is a cycle that traverses each edge of G exactly once, although it may visit a vertex more than once.

(a)
Show that G has an Euler tour if and only if every node has even degree.
(b)
Give an efficient algorithm for finding an Euler tour of a graph if one exists. What is the running time of your algorithm?

4.
One can prove that the Vertex Cover problem is NP-hard by showing that Clique polynomially reduces to it as follows. Given an instance of Clique, a graph G=(V,E) and an integer k (such that we're asking if G contains a clique of size at least k), construct the complement graph Gc = (V, Ec). (The edge set Ec of Gc consists of precisely those edges which don't exist in E, i.e. $E^c = \{(u,v) \mbox{ such that }(u,v) \mbox{ not in }E\}$.) The output of the reduction is an instance Gc, |V|-k of the vertex cover problem. (Is there a vertex cover of size at most |V|-k in Gc?). [Convince yourself that this reduction works!]

In class we saw an approximation algorithm for vertex cover that finds a vertex cover of size at most twice the minimum size. Does this relationship imply that there is an approximation algorithm with constant ratio bound for the clique problem? Justify your answer!




next up previous
Next: About this document ...
Ashish Sabharwal
2000-11-03