tag:blogger.com,1999:blog-4068183698747623113.post5332183402134878151..comments2023-10-29T10:40:34.638-04:00Comments on A CS Professor's blog: Approximation Algorithms and Structural ComplexityClaire Mathieuhttp://www.blogger.com/profile/10957755706440077623noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-4068183698747623113.post-49883917452242311392011-01-13T22:09:32.416-05:002011-01-13T22:09:32.416-05:00I think it's useful to keep both points of vie...I think it's useful to keep both points of view in mind. Recently I have done some work with a more algorithmic flavor than usual, trying to figure out the complexity of some specific problem (let's call it problem A). Initially I was not even sure whether it was a "hard" or "easy" problem. I first tried to give an efficient algorithm, and after some effort noticed some connections with problem B, a problem which looked easier to study. So the goal became to give an efficient algorithm for problem B, and then hopefully to adapt it to problem A. But that didn't work, and after a while I realized that problem B was likely to be ocmputationally hard. So now the goal became to give a reduction from B to A, thereby establishing the hardness of A.Pascalhttps://www.blogger.com/profile/14201150679841329835noreply@blogger.comtag:blogger.com,1999:blog-4068183698747623113.post-20135136586635375372011-01-10T09:36:54.507-05:002011-01-10T09:36:54.507-05:00Set Cover (cheapest family of sets, from input col...Set Cover (cheapest family of sets, from input collection, covering all elements of input universe) has an O(ln n) approximation algorithm, and an Omega(log n) hardness result assuming P is not equal to NP. Another way in which the two sides meet: it has a 1*ln(n) greedy approximation algorithm, and a 1*ln(n) hardness result with a slightly stronger assumption (Feige 1998).<br /><br />Plus, there are all the problems for which SDP algorithms give the optimal approximation ratio assuming the unique game conjecture.Claire Mathieuhttps://www.blogger.com/profile/10957755706440077623noreply@blogger.comtag:blogger.com,1999:blog-4068183698747623113.post-47076083292683557912011-01-09T12:31:59.742-05:002011-01-09T12:31:59.742-05:00Not really familiar with set cover, in what sense ...Not really familiar with set cover, in what sense do the two sides meet?Yaroslav Bulatovhttps://www.blogger.com/profile/06139256691290554110noreply@blogger.comtag:blogger.com,1999:blog-4068183698747623113.post-4768962034325170022011-01-08T14:57:03.912-05:002011-01-08T14:57:03.912-05:00Set cover? Or is that not "interesting" ...Set cover? Or is that not "interesting" on the algorithm side?Claire Mathieuhttps://www.blogger.com/profile/10957755706440077623noreply@blogger.comtag:blogger.com,1999:blog-4068183698747623113.post-12511730414956533422011-01-07T21:03:48.263-05:002011-01-07T21:03:48.263-05:00one example of such meeting point is complexity of...one example of such meeting point is complexity of weighted independent set counting, reached from tractability side in 2006 by Weitz and from intractability side in 2010 by Sly, I wonder if there are other interesting cases where the two sides have metYaroslav Bulatovhttps://www.blogger.com/profile/06139256691290554110noreply@blogger.com