MIT Department of Electrical Engineering & Computer Science

E E C S

A Structural View of Approximation

Sanjeev Khanna
Stanford University

Friday, April 26, 1996
2:30 PM (2:15 refreshments)
Room NE43-518
EECS Special Seminar

Abstract

Traditionally intractable NP Optimization (NPO) problems have been classified as per their polynomial-time approximability. For instance, APX (log-APX) is the class of NPO problems polynomial-time approximable to within a constant factor (log factor). This classification scheme does not yield insight into questions such as: What inherent properties of optimization problems determine their approximability? What is the structure of the hardest problems in an approximation class? Our work is concerned with developing a better structural understanding of NPO problems.

We begin by showing that all problems in the class APX are reducible to problems in MAX SNP. That is, we establish that the core of this computationally-defined class can be identified in purely syntactic terms. A similar characterization is shown to hold for other classes such as log-APX and poly-APX.

Next, we seek a similar characterization for PTAS -- the class of NPO problems with poly-time approximation schemes. Generalizing Baker's work, we show that certain syntactic classes restricted to instances exhibiting a planar structure capture a large sub-class of PTAS. Our work gives a unified framework to explain most known PTAS results and discover new PTAS results.

Finally, we consider the question: Can we provide a precise structural demarcation between "easy" and "hard" optimization problems? We study this question in the context of boolean constraint satisfaction problems and show that there is a surprisingly succinct structural characterization that precisely determines the complexity of each such problem.

HOST: Prof. Nancy Lynch

URL of this page: http://www-eecs.mit.edu/AY95-96/events/53.html
Created: Apr 22, 1996 | Modified: Jun 25, 1997
This announcement is from the MIT EECS 1995-96 archive. | Current events
To MIT EECS home page | Your comments and inquiries are welcome.