Date:Tue, 13 Oct 2009
From:George Jay Tucker
Subject:SPAMS this Thursday, 5PM, 2-105
Hi everyone,

This week we have Po-Ru speaking about approximation algorithms for NP-hard
problems.  Dinner will follow in the applied math common room.  See you at the
talk.

Remember to join the SPAM seminar mailing list by visiting:
http://mailman.mit.edu/mailman/listinfo/spamslist

George

Speaker: Po-Ru

Title: How Hard is NP-Hard?

Abstract:
Mathematicians know that the traveling salesman problem is NP-complete, which
oftentimes is equated with being "unsolvable."  But what if you're a traveling
salesman?  "It's NP-complete" doesn't cut it when you have gas to buy and goods
to sell.

In this talk, I'll discuss a few approximation algorithms and heuristics for
attacking NP-hard problems.  I'll also provide some demonstrations of how well
(or poorly) they work.