### 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

Abstract:

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
problem.
No knowledge beyond basic knowledge in algorithms and complexity
is assumed.
The talk surveys many papers. Proper citations will be given in the
talk.