NP-Hardness: You keep using that term---I do not think it means what you think it means.

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


David Morrison


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. 


Argue Auditorium, Millikan, Pomona College

Claremont Graduate University | Claremont McKenna | Harvey Mudd | Pitzer | Pomona | Scripps
Proudly Serving Math Community at the Claremont Colleges Since 2007
Copyright © 2018 Claremont Center for the Mathematical Sciences