[Colloquium] Revised: Sumer/M.S. Presentation/Feb.23

[Margaret Jaffey]

This is a revised announcement of Ozgur Sumer's Master's Presentation.  
The date of his presentation has been changed to Monday, February 23rd 
at 4:00 p.m. (the former date was Thurs. Feb. 19th).  In addition, the 
title and abstract have been revised.

Date:  Monday, February 23, 2004

Time:  4:00 p.m.

Place:  Ryerson 251

M.S. Candidate:  Ozgur Sumer

M.S. Paper Title:  Partial Covering of Hypergraphs

Abstract:
Let H be a hypergraph with m edges and maximum degree d. Given epsilon
> = 0, a (1-epsilon)-vertex-cover is a collection T of vertices such that
a (1-epsilon) fraction of the edges contain at least one vertex of T.
We denote min|T| by t_epsilon.

In this paper we study the performance ratio of the greedy cover
algorithm for this "partial vertex cover" problem and compare it to
random choice and to optimal complete fractional cover.

Let t* be the optimal fractional covering number (epsilon = 0). Lovasz
showed that t_0 <= ln(d)t* using the greedy cover algorithm; it follows
that the greedy cover algorithm has performance ratio <= ln(d). These
results were extended by Chvatal to the weighted case.

Kearns introduced the partial vertex cover problem. He proved that
the performance ratio of the greedy cover algorithm for the partial
vertex cover problem for weighted hypergraphs is <= 2 ln(m) regardless
of epsilon >= 0. Later, Slavik improved this bound to ln(d).

Our main contribution is that for epsilon > 0, the ratio of the greedy
cover and the optimal complete fractional cover of an unweighted
hypergraph is <= 1 / epsilon, i.e. t_epsilon <= t* / epsilon. As a
corollary, the greedy cover algorithm has a performance ratio 1 /
epsilon in the unweighted case if the hypergraph is regular and
uniform. This special case has significant applications.

We use Payley Graphs to construct new families of hypergraphs that have
the integrality gap t_0 / t* = Omega(ln(d)). We present examples that
have integrality gap >= 1/2 log(1/epsilon) and performance ratio >=
ln(1/epsilon) for partial vertex covering. Our examples are based on
Vazirani's and Slavik's examples.

If a regular and uniform hypergraph is randomly covered, then the
expected size of the cover is <= t* \ ln(1/epsilon). We compare the
bounds attained by the greedy cover algorithm with the random choice. We
establish a gap of ln(1/epsilon) in favor of random choice.

Advisor: Prof. Laszlo Babai


-- 
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Margaret P. Jaffey				margaret at cs.uchicago.edu
Department of Computer Science
Student Support Rep (Ry 161A)		(773) 702-6011
The University of Chicago		http://www.cs.uchicago.edu
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-