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.