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
of
subsets of X. (For example X could be elements {1,2,3,4,5}
and
could be
.
The set cover problem is to find a minimum-size subset
whose members contain all the elements of X.
(In the example, the first and second sets in
(
)
form a set cover because all 5 elements are included in at least one
of these sets.)
- Give a 0/1 integer programming formulation of
this problem.
- Describe (or write pseudo-code for) a branch-and-bound procedure
for finding a minimum set cover that uses the linear
programming relaxation of the integer program as a basis
for pruning the search.
- 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.
.) 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: About this document ...
Ashish Sabharwal
2000-11-03