MIT Department of Electrical Engineering & Computer Science
Designing Approximation Algorithms via Techniques from Mathematical Programming
David P. Williamson
IBM Watson
Tuesday, March 11, 1997
4:00 PM (3:45 refreshments)
Room NE43-518
EECS Special Seminar
Abstract
Many problems in combinatorial optimization seem to be hard to solve,
from both a theoretical standpoint (in that they are NP-hard) and a
practical standpoint. We look at one approach to solving such
problems, in which one designs polynomial-time algorithms to find
solutions which are provably near-optimum; these are known as
approximation algorithms. The central problem in the design of such
algorithms is showing that the solution produced is near-optimal when
the optimum value cannot be computed. We will show two examples of
using techniques from mathematical programming to design approximation
algorithms. First, we look at the survivable network design problem,
which arises in the design of low-cost failure-resistant telephone networks,
and we show that a modification of the primal-dual method leads to a good
approximation algorithm. Second, we look at the problem of finding
large cuts in a graph, which arises in various applications, including
minimizing vias in circuit board layout. We show that use of
semidefinite programming leads to solutions that are no more than 13%
away from the optimal. In both cases, experimental results show that
in practice the algorithms are better than their provable worst-case
bounds.
HOSTS: Professor N. Lynch and Professor R. Rivest
URL of this page:
http://www-eecs.mit.edu/AY96-97/events/21.html
Created: Mar 5, 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.
