__Claremont Graduate University__ | __Claremont McKenna__ | __Harvey Mudd__ | __Pitzer__ | __Pomona__ | __Scripps__

Proudly Serving Math Community at the Claremont Colleges Since 2007

Copyright © 2011 Claremont Center for the Mathematical Sciences

When

Start: 02/03/2016 - 4:15pm

End : 02/03/2016 - 5:15pm

End : 02/03/2016 - 5:15pm

Category

Colloquium

Speaker

David Morrison

Abstract

The computational notion of 'NP-hardness' is often used as an indication that a problem cannot be solved effectively in practice. However, this is in fact not true. Many real-world instances of NP-hard problems such as the traveling salesman problem, graph coloring, and others, can be solved extremely quickly in practice. In this talk, we discuss reasons for this disconnect between theory and practice, and describe a number of recent results that improve the performance of algorithms for such problems even further.

Where

Argue Auditorium, Millikan, Pomona College