The world is flat: algorithms for classical optimization problems restricted to planar graphs

Speaker: Prof. Philip Klein , Brown University Department of Computer Science

Date: Tuesday, October 08, 2013

Time: 4:15 PM to 5:15 PM Note: all times are in the Eastern Time Zone

Refreshments: 3:45 PM

Public: Yes

Location: 32-G449

Event Type:

Room Description:

Host: Constantinos Daskalakis and Dana Moshkovitz

Contact: Holly A Jones, hjones01@csail.mit.edu

Relevant URL: http://toc.csail.mit.edu/node/366

Speaker URL: None

Speaker Photo:
None

Reminders to: toc@csail.mit.edu

Reminder Subject: TALK: The world is flat: algorithms for classical optimization problems restricted to planar graphs

For a variety of classical optimization problems in graphs---e.g., maximum
flow, shortest paths, traveling salesman, Steiner tree, and
multiterminal cut---new techniques become applicable when the input
graph is restricted to be planar. Under the restriction,
approximation schemes become possible for problems that are APX-hard
in general. Linear-time algorithms or near-linear-time algorithms
emerge for problems for which no such fast algorithms are yet known
for general graphs. This talk will survey some of the recent
developments on these problems and indicate some of the techniques
involved.

Research Areas:

Impact Areas:

See other events that are part of the Theory of Computation Colloquium - 2013.

Created by Holly A Jones Email at Friday, October 04, 2013 at 12:42 PM.