tag:blogger.com,1999:blog-6555947.post7846898756789180823..comments2024-08-05T05:53:31.445-06:00Comments on The Geomblog: SoCG 2009: Local search, geometric approximations and PTASsSuresh Venkatasubramanianhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-6555947.post-41436219850630616982009-07-07T04:53:50.064-06:002009-07-07T04:53:50.064-06:00The local search idea for such geometric problems ...The local search idea for such geometric problems was first presented in the paper of Agarwal and Mustafa (Independent set of intersection graphs of convex objects in 2D), where they do constant-sized swaps to get a constant factor approximation for independent set of rectangles, making the connection to properties of planar graphs.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-39466763687576061122009-06-22T02:01:35.902-06:002009-06-22T02:01:35.902-06:00> There's some room for improvement
> in...> There's some room for improvement<br />> in the running time perhaps, at<br />> least down to a linear dependence<br />> on 1/epsilon in the exponent. We<br />> can't get a poly dependence because<br />> of strong-NP-completeness<br /><br />It is known that we cannot even get an EPTAS for these problems (PTAS with running time of the form f(epsilon)*poly(n) ), that is, epsilon cannot be removed from the exponent:<br /><br />http://www.cs.bme.hu/~dmarx/papers/marx-esa2005.pdf<br /><br />And at least for the independent set problems, linear dependence on epsilon in the exponent seems to be optimal:<br /><br />http://www.cs.bme.hu/~dmarx/papers/marx-focs2007-ptas.pdf<br /><br />It is not directly related, but let me mention that on planar graphs you can do k-local search for many graph problems much better then the n^k brute force algorithm (if I see it correctly, the papers mentioned in the post do local search on nonplanar graphs, although planar graphs appear in the analysis):<br /><br />http://www.ii.uib.no/~daniello/papers/LocalSearch.pdf<br /><br />Daniel MarxAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-51497681171538785812009-06-21T11:46:32.145-06:002009-06-21T11:46:32.145-06:00Hmmm. The connection to network flow is cute...
T...Hmmm. The connection to network flow is cute...<br /><br />The requirement of the planarity of the underlying graph is quite restrictive. It is natural to look for more general family of graphs that has a separator and thus work with local search. I would like to see more applications...<br /><br />What makes analysing local search hard is that you have to correlate somehow the local solutions with the optimal solution. <br /><br />--SarielAnonymousnoreply@blogger.com