[Colloquium] Sumer/M.S. Presentation/Feb. 19

[Margaret Jaffey]

This is an announcement of Ozgur Sumer's Master's Presentation.

Date:  Thursday, February 19, 2004

Time:  3:00 p.m.

Place:  Ryerson 251

M.S. Candidate:  Ozgur Sumer

M.S. Paper Title:  Partial Hypergraph Covering

Abstract:

	Let H be a hypergraph, and m = |H|.  The maximum degree of the 
hypergraph is denoted by delta (H).  Given epsilon is greater than or 
equal to 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.
	In this paper we study the performance ratio of the greedy vertex 
cover algorithm and compare it to the random choice and to fractional 
cover.
	Let tau and tau* be the optimal integral and fractional covering 
numbers, respectively.  For epsilon = 0, it is shown in Lovasz [Lov75] 
that tau is less than or equal to tao* 1n delta.  As a corollary, he 
showed that the performance ratio of the greedy vertex cover algorithm 
is less than or equal to 1 n delta.  This work is extended by Chvatal 
to the weighted case.
	For an arbitrary epsilon is greater than or equal to 0, Kearns [Kea90] 
proved that the performance ratio of the greedy algorithm for weighted 
hypergraphs is not more than 2 1n m.  Later, Slavik [Sla97a] improved 
the bound to 1n delta.
	We prove that the ratio of the greedy cover and optimal complete 
fractional cover of a hypergraph is constant for unweighted 
hypergraphs.  As a corollary, the greedy algorithm has a constant 
performance ratio in the unweighted case if the hypergraph is regular 
and uniform.  This special case has significant applications.  On the 
other hand, we present examples in which the performance ratio reaches 
1n delta if either one of the conditions of regularity and uniformity 
is dropped.
	If a regular and uniform hypergraph is randomly covered, then the 
expected size of the cover is less than 1n (1/epsilon) tao*.  We 
compare the bounds attained by the greedy algorithm with random choice. 
  We established a gap of 1n (1/epsilon) between the greedy and the 
random choice covers.
	Keywords: Partial set cover, partial hypergraph cover, greedy algorithm

Mr. Sumer's Advisor: Prof. Laszlo Babai

A draft copy of Mr. Sumer's M.S. paper is available for review in Ry 
161A.

Margaret
-- 
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
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
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: text/enriched
Size: 2711 bytes
Desc: not available
Url : http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20040205/4a3fb84d/attachment.bin