MIT Department of Electrical Engineering & Computer Science
The Approximability of Constraint Satisfaction Problems
Madhu Sudan
IBM T.J. Watson
Thursday, April 10, 1997
4:00 PM (3:45 refreshments)
Room NE43-518
EECS Special Seminar
Abstract
Determining the computational complexity of optimization
problems is a central goal of theoretical computer
science. Over the last decade a significant amount of attention
has successfully focussed on the complexity of finding
"approximate" (near-optimal) solutions. Among the major successes
are several new algorithmic paradigms to find approximate
solutions, as well as the development of the theory of
probabilistically checkable proofs and its consequences about the
intractibility of obtaining approximation solutions.
In this talk, I will survey some of these developments, as well as
more recent work whose goal is to develop a uniform framework to
classify approximation problems according to their computational
complexity. We consider classes of optimization problems that can
be presented as Boolean constraint satisfaction problems. We
characterize the approximability of every optimization problem
that can be presented in this way; and describe some noteworthy
trends that the characterization reveals about approximability.
URL of this page:
http://www-eecs.mit.edu/AY96-97/events/36.html
Created: Apr 2, 1997
|
Modified: Jun 24, 1997
This announcement is from the MIT EECS 1996-97 archive.
|
Current events
To MIT EECS home page
|
Your comments
and inquiries are welcome.
