YAPC::NA 2007

June 25-27, Houston, TX

Approximation algorithms in Perl

Approximation algorithms in Perl

By Walt Mankowski (‎waltman‎) from Philadelphia.pm
Date: Monday, June 25, 2007 01:30 PM
Duration: 20 minutes
Language:

You can find more information on the speaker's site:


Your boss has given you a new assignment. Remembering back to that intro to programming course you took when you were in college, you
realize that the problem he's asked you to solve is NP-complete. People smarter that you have been working on this since before you were born and haven't been able to come with any good solutions, so chances are you won't, either. So what do you do? It turns out that many NP-complete problems have approximate solutions that are surprisingly close to optimal. Even better, many of them are really easy to code in Perl. This talk begins with a brief introduction to NP-completeness, then shows several simple approximate solutions to
famous NP-complete problems.