{"id":1726,"date":"2012-11-04T15:32:20","date_gmt":"2012-11-04T19:32:20","guid":{"rendered":"http:\/\/mat.tepper.cmu.edu\/blog\/?p=1726"},"modified":"2012-11-04T15:32:20","modified_gmt":"2012-11-04T19:32:20","slug":"the-cutting-plane-method-for-matching-is-polynomial","status":"publish","type":"post","link":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/2012\/11\/04\/the-cutting-plane-method-for-matching-is-polynomial\/","title":{"rendered":"The cutting plane method for matching is polynomial"},"content":{"rendered":"

Michael Mitzenmacher<\/a> is a computer scientist at Harvard with a blog My Biased Coin<\/a>. \u00a0As you might expect from the title, Michael works in the area of randomized algorithms, and even has a book on the subject<\/a>. \u00a0His blog is an extremely useful guide to the what is happening in algorithms in CS (and what is happening in CS at Harvard, which is also quite interesting). \u00a0He often provides a summary of talks given at the big theory conferences (FOCS\/STOC\/etc.). \u00a0He just posted on this year’s FOCS (here<\/a> and here<\/a>).<\/p>\n

There was one talk that caught my eye, summarized by a doctoral student:<\/p>\n

[Editor: Fourth-year grad student\u00a0Justin Thaler\u00a0<\/a>of Harvard contributes a summary of two unrelated talks.]<\/p>\n

Paper Title: The Cutting Plane Method is Polynomial for Perfect Matchings.<\/div>\n
Harvard’s own\u00a0Karthekeyan Chandrasekaran\u00a0<\/a>talked about joint work with Laszlo A. Vegh and Santosh S. Vempala on cutting plane algorithms for matching problems. The cutting plane method is a popular algorithm for solving integer programs (IPs), used in commercial solvers. It works by starting with an LP relaxation of the given IP to obtain basic optimal solution x_0, and then iteratively adding constraints that are valid for integer solutions but violated by the basic optimum. It continues until the basic optimum is integral. The goal of this paper is to take a step toward explaining the practical efficiency of cutting plane methods, by giving an efficient cutting-plane algorithm for min-cost perfect matching (MWPM) –MWPM is known to be in P, but it was open (apparently for 30 years) whether there was a polynomial-time cutting-plane algorithm for this problem.<\/div>\n
<\/div>\n
A brief summary of how they achieve this is as follows. They start with a natural, well-known LP relaxation of the MWPM problem, called the bipartite relaxation. This relaxation has the nice property that all basic optima x are half-integral, and the support of x is a disjoint union of edges and odd cycles. This makes it easy to find cuts (the cuts correspond to what are called blossom inequalities, see the paper for details). A major challenge, though, is that naively adding cuts will not preserve the half-integrality of intermediate LPs, so at each iteration they throw away some of the old cuts that were added earlier in the execution. They need to take considerable care in choosing which cuts to keep in order to guarantee half-integrality of intermediate LPs (and to ensure that their algorithm makes progress at a sufficiently high rate).<\/div>\n<\/blockquote>\n
\u00a0This is pretty amazing. \u00a0First, it is wonderful that they were able to prove polynomiality. \u00a0It had bothered me that it seemed you might need an exponential number of cuts, even for something like matching. \u00a0I had looked at this 25 years ago when doing my doctorate, but didn’t have any particularly insightful ideas.<\/div>\n
<\/div>\n
But the really amazing thing is that they were able to arrange their algorithm so they never had to work with anything worse than half-integral solutions. \u00a0This is astounding! \u00a0A bane of cutting plane approaches is the weird fractions that keep popping up, leading to numerical stability problems. \u00a0Here, they were able to keep things well under control. \u00a0And, by keeping to half-integral, maybe some old ideas I had about using generalized networks (networks with multipliers) might come back into play. \u00a0 The approach certainly avoids the need for Gomory-Hu cut tree approaches to finding violated inequalities: \u00a0violated inequalities come straight out of \u00a0connected components. \u00a0This also harkens back to my dissertation where I had treated matching as a generalized network with side constraints.<\/div>\n
<\/div>\n
So I checked out the paper that underlies the talk at arXiv<\/a>, thinking I might try to implement some things this week and see how it works (CS theory people rarely implement: \u00a0you could make an entire career out of simply implementing what CS people suggest). \u00a0On the plus side, they reference my dissertation, so at least I am in the right ballpark. \u00a0On the down side: \u00a0it is looking a bit complicated! \u00a0Looks like I will have to reel in one of the bright doctoral students around to plow through this with me.<\/div>\n
<\/div>\n
And I wonder what else this might be used for?<\/div>\n
<\/div>\n
<\/div>\n
<\/div>\n","protected":false},"excerpt":{"rendered":"

Michael Mitzenmacher is a computer scientist at Harvard with a blog My Biased Coin. \u00a0As you might expect from the title, Michael works in the area of randomized algorithms, and even has a book on the subject. \u00a0His blog is an extremely useful guide to the what is happening in algorithms in CS (and what … Continue reading “The cutting plane method for matching is polynomial”<\/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":[6,46],"tags":[],"class_list":["post-1726","post","type-post","status-publish","format-standard","hentry","category-blogs-and-web","category-research"],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/1726","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=1726"}],"version-history":[{"count":0,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/1726\/revisions"}],"wp:attachment":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=1726"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=1726"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=1726"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}