[Colloquium] Talk by Julia Chuzhoy on Monday, February 19, 2007

[Margery Ishmael]

DEPARTMENT OF COMPUTER SCIENCE - TALK

Date: Monday, February 19, 2007
Time: 2:30 p.m.
Place: Ryerson 251

-------------------------------------------

Speaker: JULIA CHUZHOY

From:  Institute for Advanced Study, Princeton

Title:  New Thresholds of Approximability: Problems and Techniques

Abstract:

A standard approach to deal with computationally hard optimization
problems is to settle for near-optimal or approximate solutions. The
approximability threshold of an optimization problem is the best
approximation ratio achievable by any efficient approximation
algorithm for it. The past two decades have seen major progress in
understanding the approximability of fundamental problems as well as
the behavior of the NP-hard optimization problems as a whole.

In spite of this progress, some fundamental issues about
approximability are still unexplored. For instance, until recently,
the approximability of natural NP-hard optimization problems seemed
to fall within only few categories, having either constant or
logarithmic and higher approximability thresholds. In this talk we
will describe our research that reveals, for the first time, natural
problems whose approximability lies strictly between the constant
and the logarithmic classes. Establishing the approximability of
these problems requires close interaction between the techniques
used for designing approximation algorithms and the techniques used
for showing hardness results. We illustrate some of these techniques
on a hardness of approximation proof for the asymmetric k-center
problem and an approximation algorithm for a resource minimization
scheduling problem.

***The talk will be followed by refreshments in Ryerson 255***

-------------------------------------------------------

Host:  Laci Babai

People in need of assistance should call 773-834-8977 in advance.

For information on future CS talks: http://www.cs.uchicago.edu/events



-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20070212/aa93fbe6/attachment.htm