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

When
Start: 02/03/2016 - 4: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