tag:blogger.com,1999:blog-8890204.post4645885066528274002..comments2024-06-14T02:45:02.104-04:00Comments on My Biased Coin: Conference Reviewing: Another Rant on Competitive AnalysisMichael Mitzenmacherhttp://www.blogger.com/profile/06738274256402616703noreply@blogger.comBlogger14125tag:blogger.com,1999:blog-8890204.post-74341088409905182542008-06-14T05:15:00.000-04:002008-06-14T05:15:00.000-04:00The author of this blog appears to believe that im...The author of this blog appears to believe that improving constant factors in case of approx. algorithms is may not be particularly interesting or useful. Yet, is it not in this type of work, where it becomes harder and harder to improve the algorithm, that novel and creative techniques are discovered? Surely then, such work is worthy of effort.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-18348400373283584042008-03-05T09:57:00.000-05:002008-03-05T09:57:00.000-05:00Anonymous 12: I can understand the reasoning that...Anonymous 12: I can understand the reasoning that it's potentially complexity-theoretically interesting to know if a problem has a constant-competitive algorithm or a PTAS. This fits with my possible motivation 3. If the problem's mathematically pretty, perhaps also motivation 1. If the competitive algorithm being studied is a "real" algorithm for the problem, motivation 2 would come into play. Or if the study gave some real insight into how to design algorithms for the problem, motivation 4. <BR/><BR/>I think it pays to be skeptical of all lines of research and question their value. (That's a way to figure out what YOU want to work on.) But yes, I think I've been on record as stating I'm skeptical about work in approximation algorithms when I feel it doesn't seem well-motivated (using one of the above motivations, or some other motivation).Michael Mitzenmacherhttps://www.blogger.com/profile/02161161032642563814noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-4766767172302304332008-03-05T09:20:00.000-05:002008-03-05T09:20:00.000-05:00If 3.5-approximations are not so interesting and P...If 3.5-approximations are not so interesting and PTAS take time that has functions of 1/epsilon in the exponent... does that imply that we should be skeptical about a large majority of the work in approximation algorithms?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-66300525020091530712008-03-02T23:33:00.000-05:002008-03-02T23:33:00.000-05:00I felt that competitive analysis is a natural way ...<I>I felt that competitive analysis is a natural way to analyze such online problems.<BR/></I><BR/><BR/>If you think about it, what competitive analysis is doing is measuring the performance of an online algorithm in a manner proportional to the complexity of the input. The proxy for "complexity of the input" is the performance of the offline optimum on said input, but there is nothing magical or indeed particularly natural about this measure of difficulty. Others make equal or more sense. Have a look at the survey quoted above for a sample of alternatives.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-47436051676903423772008-02-26T14:36:00.000-05:002008-02-26T14:36:00.000-05:00You raised some interesting points. But I am wonde...You raised some interesting points. But I am wondering what are the other ways to analyze problems which are inherently online in nature, and where you dont know all the input parameters in advance? I felt that competitive analysis is a natural way to analyze such online problems.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-42361000058671613312008-02-25T07:43:00.000-05:002008-02-25T07:43:00.000-05:00Anonymous #7: I also have some skepticism regardi...Anonymous #7: I also have some skepticism regarding approximation algorithms, primarily in cases where there's motion in the form of a 6-approximation to a 4-approximation to a 3.5-approximation and so on. (That is, there's just improvements in the constant.) Usually such problems are amenable to local search algorithms in practice, and nobody ever uses any of the approximation algorithms.<BR/><BR/>Again, other motivations (like those I gave in my post) may still apply.Michael Mitzenmacherhttps://www.blogger.com/profile/02161161032642563814noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-59080418401143685372008-02-21T13:12:00.000-05:002008-02-21T13:12:00.000-05:00Competitive analysis sounds like an engineering pr...Competitive analysis sounds like an engineering problem, not a theoretical problem.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-37628088732432750332008-02-21T07:09:00.000-05:002008-02-21T07:09:00.000-05:00I think hn has a point. Do you think the same way ...I think hn has a point. Do you think the same way about approximation algorithms? At least, in an off-line scenario you may even be able to find the optimal solution in reasonable time for virtually every problem instance appearing in practice. Usually, you cannot hope for something like that for an on-line problem.<BR/><BR/>I'm not saying that competitive analysis is the right thing all the time. I'm just saying that if competitive analysis is not the way to go, approximation algorithms aren't either.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-9392051628623692612008-02-21T04:56:00.000-05:002008-02-21T04:56:00.000-05:00"So you are saying an algorithm is still considere...<I>"So you are saying an algorithm is still considered to be good if it is reaching 10% of the optimal solution?"</I><BR/><BR/>Or what is worst, we know of a very good online algorithm, in the sense that it compares positively with every other <I>online</I> algorithm, but the competitive ratio gives it a low score because it compares badly against the idealized, unachievable <I>offline</I> optimum.<BR/><BR/>AlexAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-50059445178682711072008-02-21T01:49:00.000-05:002008-02-21T01:49:00.000-05:00I found it interesting to explain the concept of c...I found it interesting to explain the concept of competitive ratio to non-CS folk (from high school kids to EE PhDs). They cannot be more confused on such a "meaningless" definition if this is the first time they hear about it - "So you are saying an algorithm is still considered to be good if it is reaching 10% of the optimal solution?"Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-69297216678760662342008-02-20T17:08:00.000-05:002008-02-20T17:08:00.000-05:00For many problems, competitive analysis isn't real...<I>For many problems, competitive analysis isn't really well motivated.</I><BR/><BR/>This is more or less commonly known with the on-line community. We have put pen to paper on this, in two survey papers which summarize work on the field: <BR/><BR/><A HREF="http://www.cs.uwaterloo.ca/~alopez-o/cspap/online_survey/" REL="nofollow">A Survey of Performance Measures for On-line Algorithms.</A> Reza Dorrigiv and A. López-Ortiz. SIGACT News, Vol. 36, No. 3, September 2005. <BR/><BR/>Reza Dorrigiv, Alejandro López-Ortiz: <A HREF="http://www.springerlink.com/content/vm545256m634q571/" REL="nofollow">Closing the Gap Between Theory and Practice.</A> New Measures for On-Line Algorithm Analysis. WALCOM 2008: 13-24<BR/><BR/><BR/>AlexAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-62508604804739246192008-02-20T14:50:00.000-05:002008-02-20T14:50:00.000-05:00Oh, please. Yes, you can make the same high-level...Oh, please. Yes, you can make the same high-level argument for any algorithms paper -- the paper should actually have some motivation. But just on the criteria I raised (mathematical niceness/interestingness, applicability + insight into practice, never mind its role in complexity) worst-case analysis of algorithms has proven and in my mind actually is much more valuable, robust, whatever you want to call it compared to competitive analysis. <BR/><BR/>So yes, you could make the same argument against worst-case analysis, but it would be a much, much weaker argument. And yes, we should have the recognition that there are times when worst-case analysis isn't necessarily all that well-motivated, but as a community I think we already do that. (Individuals may vary.) As a community, I think we've failed to exercise restraint and say that for many problems, competitive analysis isn't really well motivated.Michael Mitzenmacherhttps://www.blogger.com/profile/02161161032642563814noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-10245629986541155472008-02-20T14:25:00.000-05:002008-02-20T14:25:00.000-05:00If I understand you correctly, everything you say ...If I understand you correctly, everything you say would apply to *any* algorithms paper, not just those dealing with competitive analysis. Turning this around, I think competitive analysis is just as well-motivated as worst-case analysis (and different people may have different opinions as to whether worst-case analysis is well-motivated or not).Jonathan Katzhttps://www.blogger.com/profile/07362776979218585818noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-12433736668857985372008-02-20T13:40:00.000-05:002008-02-20T13:40:00.000-05:00Hi Michael,You can make exactly the same argument ...Hi Michael,<BR/><BR/>You can make exactly the same argument for (off-line) approximation algorithms, and worst-case analysis (on time, space, solution quality, etc.) in general.<BR/><BR/>Some non-theory people have expressed thoughts that TCS is useless in practice using this line.Anonymousnoreply@blogger.com