{"id":1751,"date":"2013-01-02T15:22:13","date_gmt":"2013-01-02T19:22:13","guid":{"rendered":"http:\/\/mat.tepper.cmu.edu\/blog\/?p=1751"},"modified":"2013-01-02T15:22:13","modified_gmt":"2013-01-02T19:22:13","slug":"easy-and-hard-problems-in-practice","status":"publish","type":"post","link":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/2013\/01\/02\/easy-and-hard-problems-in-practice\/","title":{"rendered":"Easy and Hard Problems in Practice"},"content":{"rendered":"

David Eppstein<\/a> of the blog 0xde<\/a> has a list of his top 10 preprints in algorithms in 2012<\/a>. \u00a0One particularly caught my eye:<\/p>\n

Clustering is difficult only when it does not matter<\/strong>, Amit Daniely, Nati Linial, and Michael Saks, \u00a0arXiv:1205.4891<\/a>. […] this represents a move from worst-case complexity towards something more instance-based. The main idea here is that the only hard instances for clustering problems (under traditional worst-case algorithms) are ones in which the input is not actually clustered very well. Their definition of a “good clustering” seems very sensitive to outliers or noisy data, but perhaps that can be a subject for future work.<\/p><\/blockquote>\n

This paper really hit home for me. \u00a0I have taught data mining quite often to the MBAs at the Tepper School<\/a> and clustering is one topic I cover (in fact, research on clustering<\/a> got me interested in data mining in the first place). \u00a0I generally cover k-means clustering<\/a> (easy to explain, nice graphics, pretty intuitive), and note that the clustering you end up with depends on the randomly-generated starting centroids. \u00a0This is somewhat bothersome until you play with the method for a while and see that, generally, k-means works pretty well and pretty consistently as long as the data actually has a good clustering (with the correct number of clusters). \u00a0It is only when the data doesn’t cluster well that k-means depends strongly on the starting clusters. \u00a0This makes the starting centroid issue much less important: \u00a0if it is important, then you shouldn’t be doing clustering anyway.<\/p>\n

There are other operations research algorithms where I don’t think similar results occur. \u00a0In my work in practice with integer programming, most practical integer programs turn out to be difficult to solve. \u00a0There are at least a couple of reasons for this (in addition to the explanation “Trick is bad at solving integer programs”). \u00a0Most obviously, easy problems typically don’t get the full “operations research” treatment. \u00a0If the solution to a problem is obvious, it is less likely to require more advanced analytics (like integer programming and similar).<\/p>\n

More subtly, \u00a0there is a problem-solving dynamic at work. \u00a0If an instance is easy to solve, then the decision maker will do something to make it harder. \u00a0Constraints will be tightened (“What if we require at least 3 weeks between consecutive visits instead of just two?”) or details will be added (“Can we add the lunch breaks?”) until the result becomes a challenge to solve. \u00a0I have not yet had a real-world situation where we exhausted the possibilities to add details to models or to further explore the possible sets of constraints. \u00a0Eventually, we get to something that we can’t solve in a reasonable amount of time and we back up to something we can (just) solve. \u00a0So we live on the boundary of what can be done. \u00a0Fortunately, that boundary gets pushed back every year.<\/p>\n

I am sure there is a lot of practical work in operations research that does not have this property. \u00a0But I don’t think I will wake up one morning to see a preprint: “Integer programming is difficult only when it doesn’t matter”.<\/p>\n","protected":false},"excerpt":{"rendered":"

David Eppstein of the blog 0xde has a list of his top 10 preprints in algorithms in 2012. \u00a0One particularly caught my eye: Clustering is difficult only when it does not matter, Amit Daniely, Nati Linial, and Michael Saks, \u00a0arXiv:1205.4891. […] this represents a move from worst-case complexity towards something more instance-based. The main idea … Continue reading “Easy and Hard Problems in Practice”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4,29,46],"tags":[],"class_list":["post-1751","post","type-post","status-publish","format-standard","hentry","category-applications","category-integer-programming","category-research"],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/1751","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/comments?post=1751"}],"version-history":[{"count":0,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/1751\/revisions"}],"wp:attachment":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=1751"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=1751"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=1751"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}