DIMACS Theoretical Computer Science Seminar

Title: Rare approximation ratios

Speaker: Guy Kortsarz, Rutgers University

Date: February 14, 2006 2:00-3:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ


Some ratios in approximation algorithms appear quite often. 
For example, constant ratios, logarithmic ratios for minimization 
problems, polynomial ratios (like sqrt n) and PTAS (namely, (1+eps) 
for every epsilon ratios).

In this talk we discuss some problems that admit seemingly more 
rare ratios.  The talk does not attempt to be comprehensive for 
rare ratios (I may not know all such results).  We will concentrate 
on cases where the approximation status of the problem is rather 
clear (so the current ratio really reflects on the problem and not 
merely on the current state of knowledge).

The talk is a survey type and will not go deep into technical details.
It will try to give some intuitive explanations for the reasons the 
problems do not behave in the more common way.

The problems discussed are:

1) Problems that admit a +1 additive approximation

2) The domatic number problem (log n ratio for a maximization problem)
and the unique set coverage problem

3) The group Steiner problem on trees and the minimum time radio 
broadcast problem (polylogarithmic upper and lower bounds)

4) The asymmetric k-center problem (log* n tight ratio)

5) The complete partition problem (a tight sqrt log n ratio),
the cycle packing problem and the minimum congestion paths 

No knowledge beyond basic knowledge in algorithms and complexity 
is assumed.

The talk surveys many papers. Proper citations will be given in the