tag:blogger.com,1999:blog-10560800.post574649679618068310..comments2017-10-16T21:58:03.846-07:00Comments on Machine Learning, etc: Linear Programming for Maximum Independent SetYaroslav Bulatovhttp://www.blogger.com/profile/06139256691290554110noreply@blogger.comBlogger14125tag:blogger.com,1999:blog-10560800.post-17472943492252207822017-09-22T17:31:22.433-07:002017-09-22T17:31:22.433-07:00Why does the LP relaxation work on perfect graphs?...Why does the LP relaxation work on perfect graphs?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-10560800.post-80104132423681633532016-11-15T21:32:35.651-08:002016-11-15T21:32:35.651-08:00I want a program for this.
I want a program for this. <br />Nishi Shahhttps://www.blogger.com/profile/16084284739117475456noreply@blogger.comtag:blogger.com,1999:blog-10560800.post-52912539546886035942016-09-20T06:14:38.761-07:002016-09-20T06:14:38.761-07:00This is a awesome blog post.This is a awesome blog post.Can Crusherhttp://www.cancrusher.usnoreply@blogger.comtag:blogger.com,1999:blog-10560800.post-36026810380918998012016-06-17T23:43:47.042-07:002016-06-17T23:43:47.042-07:00Great technology of the best electronic machine -
...Great technology of the best electronic machine -<br /><br /><a href="http://cancrusher.us/" rel="nofollow">Can Crusher</a><br /><a href="http://cancrusher.us/" rel="nofollow">Can Recycling</a><br /><a href="http://swiftpcoptimizer.com/" rel="nofollow">PC Optimizer Free</a><br /><a href="http://swiftpcoptimizer.com/" rel="nofollow">Best PC Optimizer</a><br /><a href="http://swiftpcoptimizer.com/"Can Crushershttp://cancrusher.us/noreply@blogger.comtag:blogger.com,1999:blog-10560800.post-77459548539622864772016-06-01T23:56:23.731-07:002016-06-01T23:56:23.731-07:00Jayati Tools Private Limited is a trusted company ...Jayati Tools Private Limited is a trusted company which is Manufacturer and Supplier of scaffolding equipment all over the world. We are manufactur the Scaffolding Accessories, composite die holder, scaffolding socket, Tuff Scaffolding Machine and all types of Scaffolding equipments. www.scaffoldingmachines.com<br />Scaffolding Machineshttps://www.blogger.com/profile/07556396537089523659noreply@blogger.comtag:blogger.com,1999:blog-10560800.post-83999160584979245862015-07-04T01:28:03.295-07:002015-07-04T01:28:03.295-07:00For Roman's question, the 1/2-solutions propos...For Roman's question, the 1/2-solutions proposed are not basic solutions since they are the convex combination of other solutions (in particular, the alternative integer solutions). So, as long as your LP algorithm returns basic solutions (for instance the simplex algorithm; interior point methods have approaches that force basic solutions but that is not required), you will not get the 1/2 Mikehttps://www.blogger.com/profile/06565924216653271386noreply@blogger.comtag:blogger.com,1999:blog-10560800.post-16042627408246067322013-03-08T23:02:29.012-08:002013-03-08T23:02:29.012-08:00Hi there, awesome site. I thought the topics you p...Hi there, awesome site. I thought the topics you posted on were very interesting. I tried to add your RSS to my feed reader <br /><br />and it a few. take a look at it, hopefully I can add you and follow.<br /><br /><a href="http://www.the-village.in/sky-villas.html" rel="nofollow">Independent Villas</a>kambanhttps://www.blogger.com/profile/04952904123588851721noreply@blogger.comtag:blogger.com,1999:blog-10560800.post-73414510207417974482012-11-05T08:53:30.360-08:002012-11-05T08:53:30.360-08:00The possible sets of nonintegral values in optimal...The possible sets of nonintegral values in optimal LP solutions are closed under intersection (Picard&Queyranne: On the integer-valued variables in the linear vertex packing problem, 1977, http://dx.doi.org/10.1007/BF01593772). Thus, there is a unique optimal LP solution with the minimum number of fractional values, and you can find it for example by trying to fix each variable to 1 and Falk Hüffnernoreply@blogger.comtag:blogger.com,1999:blog-10560800.post-67675321851576875662012-10-02T10:13:05.854-07:002012-10-02T10:13:05.854-07:00In my example with the bowtie graph, there's n...In my example with the bowtie graph, there's no maximum independent set that contains middle node, yet it gets value 1/2Yaroslav Bulatovhttps://www.blogger.com/profile/06139256691290554110noreply@blogger.comtag:blogger.com,1999:blog-10560800.post-9564064880107153402012-10-02T06:34:35.135-07:002012-10-02T06:34:35.135-07:00I think the reason of 1/2 solution is that the var...I think the reason of 1/2 solution is that the variable takes value 1 in some of the maximum independent sets and 0 in others. In easy cases of Independent-Set, e.g. on Erdos-Renyi random graphs with average connectivity smaller than 2.71828..., leaf-removal algorithm gives an optimal solution, then I guess LP will give a tight solution. In hard cases, when leaf-removal core exists, no efficient 张潘https://www.blogger.com/profile/17393195142155657815noreply@blogger.comtag:blogger.com,1999:blog-10560800.post-66528731603296268062011-03-16T07:00:06.681-07:002011-03-16T07:00:06.681-07:00Concerning Roman's question I think it is poss...Concerning Roman's question I think it is possible to add random small epsilons (either positive or negative) to the right parts of constaints in LP relaxation. We will seem to loose the property of half-integrality but in such unlikely case when there are several solutions we will definitely converge to the integer one.Dmitry P. Vetrovnoreply@blogger.comtag:blogger.com,1999:blog-10560800.post-77173038319367282172011-03-16T00:34:02.451-07:002011-03-16T00:34:02.451-07:00Roman - Good question, I actually don't know w...Roman - Good question, I actually don't know why integer solution was chosen in that case. There are quite a few cases like that, with non-unique maximum, yet the solver choosing an integer solution, perhaps it's a side effect of the simplex method<br /><br />Danny - that sounds like a promising approach -- here you could see which regions of the graph produce non-integer solutions, add Yaroslavhttps://www.blogger.com/profile/06139256691290554110noreply@blogger.comtag:blogger.com,1999:blog-10560800.post-6772871542598678412011-03-16T00:07:30.917-07:002011-03-16T00:07:30.917-07:00Look at, say, graph on (4, 5) position in the firs...Look at, say, graph on (4, 5) position in the first big picture. It is not the only optimal LP solution, an off-the-shelf LP algorithm can assign 1/2 to the both nodes in the left column, and to the both nodes in the right column. So, should one use some technique that prefers integral solutions? Is it the common case when there are several optimums, and integral among them?Roman V. Shapovalovhttps://www.blogger.com/profile/01422787855469629259noreply@blogger.comtag:blogger.com,1999:blog-10560800.post-46285765312448010452011-03-06T11:03:08.370-08:002011-03-06T11:03:08.370-08:00Cool post.
So in a practical setting, if we wante...Cool post.<br /><br />So in a practical setting, if we wanted to solve large maximum independent set problems with this approach, we could imagine starting with the basic set of edge constraints, running the LP, checking to see if we have an integral solution, and if not, intelligently adding new constraints.<br /><br />Do you have any ideas about good ways to choose which additional constraints Danny Tarlowhttps://www.blogger.com/profile/14670021337844708633noreply@blogger.com