tag:blogger.com,1999:blog-6555947.post5635227258225540964..comments2023-11-23T00:34:43.496-07:00Comments on The Geomblog: The concept of an approximationSuresh Venkatasubramanianhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-6555947.post-21723609723936123752008-07-25T03:56:00.001-06:002008-07-25T03:56:00.001-06:00We're always searching for new ways to communicate...We're always searching for new ways to communicate cool ideas in theoryCS to the outside world, and the list gets more and more esoteric each time one thinks about it <a title="интернет-салон фотографии" href="http://www.printgallery.ru"></a>redpetrehttps://www.blogger.com/profile/08657873430656478962noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-8040198446057734212008-07-24T11:11:00.000-06:002008-07-24T11:11:00.000-06:00but it seems to me that there's something about th...<I>but it seems to me that there's something about the adversarial nature of approximation ratios that's quintessentially a CS notion</I><BR/><BR/>Funny you mention that, as I was just thinking that a problem with our approach to heuristics in TCS is that we are over-trained in adversarial arguments.<BR/><BR/>If someone comes up with a heuristic we can almost instinctively find the case where it will fail. What if we also provided our students with techniques through the curriculum that would allow them to equally instinctively find a subset of the inputs on which the heuristic is optimal?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-39004143177073617362008-07-23T16:00:00.000-06:002008-07-23T16:00:00.000-06:00Andy: I've learnt 'regret ratio' as 'competitive r...Andy: I've learnt 'regret ratio' as 'competitive ratio', and in fact I've used that (in the classic ski vs rent formulation) to explain approximations as well. The difference in my mind which almost makes it easier is that you can imagine the oracle as someone who tells the future, and somehow it almost seems more palatable. <BR/><BR/>Daniel/Alex: I think what I wanted to point out (which Michael cottoned on to) was not so much that "everyone should use approximations", which I definitely don't believe for the reasons you both outline. What is more important is the very idea that an approximation is in fact possible at all. <BR/><BR/>p.s Daniel, I've actually talked with mathematicians who get hung up on this whole 'global optimum' thing and don't register the possibility of approximations. I'm aware of approximation theory in general, but it seems to me that there's something about the adversarial nature of approximation ratios that's quintessentially a CS notion (and don't get me started on PCPs).Suresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-25186129539324726992008-07-23T14:11:00.000-06:002008-07-23T14:11:00.000-06:00We do worst case complexity analysis because exper...We do worst case complexity analysis because experience shows that the worst case running time of an algorithm is in most cases a good proxy for the actual running time of the algorithm. In the case of approximation algorithms, worst case analysis is generally a substantial overestimation of the average case performance, so if we hope to get applied people to use approximation algorithm results we need to give them a better measure. For example we can try to characterize where exactly the heuristic fails and parameterize on this, e.g. works best on graphs of low degree. This way if the user has reason to believe that the graphs are of low degree in practice they get a much better picture of actual performance.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-6083308361818861572008-07-23T13:41:00.000-06:002008-07-23T13:41:00.000-06:00I think we're lucky that this useful notion of app...I think we're lucky that this useful notion of approximation is as straightforward as it is; other areas have it much worse. <BR/><BR/>For example, I remember a Scientific American puzzle column by Dennis Shasha, that made an audacious attempt to introduce readers to the concept of regret ratios (a widely-used if not uncontroversial notion of approximation for 'online algorithms'):<BR/><BR/>http://tinyurl.com/628n8r<BR/><BR/>A good attempt (and a neat area for puzzles), but how many readers would've absorbed the idea?Andy Dhttps://www.blogger.com/profile/03897281159810085972noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-9508237131397067892008-07-23T07:37:00.000-06:002008-07-23T07:37:00.000-06:00There is an entire field outside theoretical compu...There is an entire field outside theoretical computer science called "approximation theory". And yes, they care very much about worst case bounds. And yes, they approximate function that are hard to evaluate or for which no closed form is known. <BR/><BR/>Similarly, in numerical analysis, they have a priori bounds.<BR/><BR/>Of course, these bounds are not "computational" bounds, but the idea is the same.<BR/><BR/>However, there are many, many, many very important and practical problems where this bound-based research is just not very productive. What people care about is what happens on "real" data. It is very difficult to model this "real" data in a way that will allow theoretical investigation.<BR/><BR/>This is not to say that theoretical models are not useful, but they have to relate to your actual experiments.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-88950929860192373002008-07-23T07:17:00.000-06:002008-07-23T07:17:00.000-06:00I agree that the concept of an approximation algor...I agree that the <I>concept</I> of an approximation algorithm is very important, and should be taught as part of standard theory. (I have 1+ lecture for approximation algorithms, and 1 lecture for heuristic algorithms, in my undergraduate algorithms class.) The DFS-MST for TSP is one of my standard examples, and it is really nice to teach. Students should understand that the question "Is there a good approximation algorithm?" should be one of their standard responses to "This problem is NP-hard?" <BR/><BR/>In practice, my experience is most people don't care about worst-case guarantees; they care about performance on their instances. (The real problem with most approximation algorithms is <I>not</I> that the guarantees are too weak or that claimed bounds don't match empirical performance; it's that they suck compared even to easy heuristics, precisely because they're designed for the worst case. A general exception is greedy algorithms, where bounds don't generally match actual performance, but often greedy algorithms provide a reasonable baseline performance.) So it's no wonder that approximations aren't part of the usual conversation.Michael Mitzenmacherhttps://www.blogger.com/profile/02161161032642563814noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-36177012503310485822008-07-23T06:55:00.000-06:002008-07-23T06:55:00.000-06:00I don't think the notion of an approximation is CS...I don't think the notion of an approximation is CS theory specific. The concept of showing upper and lower bounds exists in other fields too, and if these bounds are close, then we have an approximation. (although its possible that outside CS, people don't usually care much about approximations that are as bad as an arbitrary constant factor (or even say, O(\sqrt{n})) away from what we are looking for!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-59844170902789311782008-07-23T01:48:00.000-06:002008-07-23T01:48:00.000-06:00Person: Oh this problem is NP-hard so we ran this ...Person: Oh this problem is NP-hard so we ran this heuristic<BR/>Me: Have you tried approximating it ? <BR/>P: Sure, there's an old linear-time PTAS. If we mentioned it, we couldn't have written papers about the heuristic.<BR/>Results are nothing, technique is everything.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-37745954165865063872008-07-23T00:59:00.000-06:002008-07-23T00:59:00.000-06:00I died at the end there, sorry; most people ignore...I died at the end there, sorry; most people ignore the log(1/eps) in convex so it's fun to point out. but that wasn't an example of what I meant by the ALSOAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-84798007107924727092008-07-23T00:54:00.000-06:002008-07-23T00:54:00.000-06:00it's very useful to give a concrete approach. For...it's very useful to give a concrete approach. For instance, the most typical is to analyze the optimal and tease out a lower bound. As in the case of metric TSP, this lower bound can be very intuitive, and getting factor 2 can be done to someone with no background in just a couple minutes and no paper or whiteboard (and people are happy to see that the elementary tools DFS and MST go so far).<BR/><BR/>What's even nicer is, if the person seems interested, giving the 1.5 factor solution is hardly more work. <BR/><BR/>AND THEN you can even very easily talk about how dropping the metric property destroys things by giving the resulting hamilton path oracle.<BR/><BR/>The first time someone was confused by approximation algorithms, this is what I went through, and they seemed very happy.<BR/><BR/>ALSO it is fun to talk about approximation algorithms for problems which are NOT NP-hard. For instance, convex solvers only guarantee getting epsilon close..Anonymousnoreply@blogger.com