tag:blogger.com,1999:blog-3722233.post9074690520555026417..comments2023-09-25T11:29:10.548-05:00Comments on Computational Complexity: BREAKTHROUGH in algorithms: Improved algorithm for Metric TSP!!!!!!!!Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger40125tag:blogger.com,1999:blog-3722233.post-45000061567887162662011-01-18T06:31:00.105-06:002011-01-18T06:31:00.105-06:00Hello! Yesterday I found one new great book “Trave...Hello! Yesterday I found one new great book “Traveling Salesman Problem, Theory and Applications”<br />Book is free to download, or you just can read it on online reading platform here: http://www.intechopen.com/books/show/title/traveling-salesman-problem-theory-and-applications This book is a collection of current research in the application of evolutionary algorithms and other optimal algorithms to solving the TSP problem. It brings together researchers with applications in Artificial Immune Systems, Genetic Algorithms, Neural Networks and Differential Evolution Algorithm. Hybrid systems, like Fuzzy Maps, Chaotic Maps and Parallelized TSP are also presented. Most importantly, this book presents both theoretical as well as practical applications of TSP, which will be a vital tool for researchers and graduate entry students in the field of applied Mathematics, Computing Science and Engineering.Brian Smithhttps://www.blogger.com/profile/02532521410786281786noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-86096347081510769822011-01-04T21:23:16.256-06:002011-01-04T21:23:16.256-06:00My understanding is that for an awful lot of speci...My understanding is that for an awful lot of special cases, TSP has better approximation factors. The unweighted metric case seems to be quite less interesting than other metric cases, such as Eucledian metric case (for which there is a ptas).<br /><br />Looking at the paper, no significant new techniques are introduced either. So the value of the paper is a bit doubtful.<br /><br />The paper is surely of the standard of SODA but for STOC/FOCS, I would have given it a weak acceptance (and may be even borderline or weak reject given the raised expectation by this blog post).<br /><br />This blog post is just hype. An opinion of a single professor, who first sold how difficult the metric TSP is and then talked about a very special unweighted metric case. Hajiaghayi needs to mention the past attempts on this special case in his blog post before even talking about the result or calling it a breakthrough. Otherwise the blog post is not even credible.<br /><br />I hope the hype posts do not inflate the value of a paper, because that would be a bad precedence.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-26436132275347552262011-01-03T10:06:59.506-06:002011-01-03T10:06:59.506-06:00I have added a LINK to the Wikipedia post
and a LI...I have added a LINK to the Wikipedia post<br />and a LINK to the paper that contains<br />the lower bound result. The Wikipedia post<br />helped me find the paper.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-24588443900052996112011-01-03T09:55:36.510-06:002011-01-03T09:55:36.510-06:00(Anonymous tried to post this fine comment on Dec ...(Anonymous tried to post this fine comment on Dec 24 but our moderator thing<br />blocked it for some reason. Here it is. Sorry about that.)<br /><br /><br />If this is a breakthrough algorithm, so also is Abhiram Ranade's less<br />well known result <br /><i>Precedence Constrained Scheduling in (2-7/3p+1)*Optimal</i><br />It is a different matter that Abhiram does not trumpet his result nor<br />does he have any friends who do it for him.<br />Link:<br /><a href="http://www.cse.iitb.ac.in/~ranade/pcs.pdf" rel="nofollow">here</a><br />or<br />here:<br /> //www.cse.iitb.ac.in/~ranade/pcs.pdfGASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-22926606120600242012010-12-28T00:09:55.037-06:002010-12-28T00:09:55.037-06:00If we had a voting system for new results (either ...If we had a voting system for new results (either equal votes for everyone or weighted votes based on area and reputation), then identifying what is a break-through would probably be much easier. I think it is time for adding the commenting, endorsement, and voting capabilities (other suggestions?) to ECCC and arXiv.<br /><br />Lance/Bill, could you write a post on what new capabilities people would like to see on ECCC and arXiv. I think that can be a very fruitful discussion and if implemented can save us considerable time.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-34875401465888440112010-12-25T11:25:55.919-06:002010-12-25T11:25:55.919-06:00I agree with Anonymous 29. But it would have been ...I agree with Anonymous 29. But it would have been good to have a blog title "A Nice Result On Algorithms", rather than "BREAKTHROUGH in Algorithms". It looks like trying to gain too much publicity for a work, while there are several others which also deserve equal attention. It would have been appropriate if the blogger had said that it is a nice result and had discussed the algorithm, technique etc. that would have been much more enlightening.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-66850054398674710642010-12-23T13:28:35.201-06:002010-12-23T13:28:35.201-06:00Anonymous 30:
If 1) http://www.eccc.uni-trier.de/r...Anonymous 30:<br />If 1) http://www.eccc.uni-trier.de/report/2010/200 and 2)http://www.eccc.uni-trier.de/report/2010/199 are breakthroughs, then I can list 5000 other breakthroughs of the last year.<br /><br />As a matter of fact, there are no more new results. There are only breakthroughs.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-9638031743421352432010-12-23T12:25:13.094-06:002010-12-23T12:25:13.094-06:00Yes, we need to redefine the word "breakthrou...Yes, we need to redefine the word "breakthrough".<br /><br />btw, if Lance/ Gasarch/ GuestBlogger can go through the 55 page paper that Amin has uploaded and give an overview of the ideas like Lipton does in his blog, that will be good!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-24057206144941816002010-12-23T08:13:33.045-06:002010-12-23T08:13:33.045-06:00Some more breakthrough results:
1) http://www.eccc...Some more breakthrough results:<br />1) http://www.eccc.uni-trier.de/report/2010/200<br />2)http://www.eccc.uni-trier.de/report/2010/199<br />3) http://www.eccc.uni-trier.de/report/2010/198<br /><br />and finally, the next two are perhaps most important, will certainly be in Lance's new list of favorite theorems of this decade:<br />4) http://www.eccc.uni-trier.de/report/2010/197 and <br />5) http://www.eccc.uni-trier.de/report/2010/196<br /><br />Just doing my part to make everyone aware of the new breakthroughs. By the way, can we now re-define the word "breakthrough." It does not seem to mean what it used to any more... at least in complexity and algorithms.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-58321085442785120332010-12-23T00:06:14.744-06:002010-12-23T00:06:14.744-06:00The paper is now on Amin's webpage:
http://www...The paper is now on Amin's webpage:<br />http://www.stanford.edu/~saberi/tsp.pdfAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75667590788241850432010-12-22T21:25:12.747-06:002010-12-22T21:25:12.747-06:00I doubt that anonymous 25 is an author of this pap...I doubt that anonymous 25 is an author of this paper. I am not an author of this paper, though I had already found it pretty easily before the last comment (claiming the paper is not available).<br /><br />In case you haven't found it yet, here it is: <a rel="nofollow">http://www.stanford.edu/~saberi/tsp.pdf</a>Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90148925093620421482010-12-22T18:40:23.840-06:002010-12-22T18:40:23.840-06:00It's a pity the entire discussion focuses on t...It's a pity the entire discussion focuses on the issues whether the result is a breakthrough or not, or whether the result is practical or not, etc. The same happened in several blogs on Ryan's result.<br /><br />I have no doubt the result is very nice and I would prefer to see some comments about the algorithm itself, techniques they use, their analysis.<br /><br />BTW: the paper is available on Amin's web page (http://www.stanford.edu/~saberi/).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-74243407724430492452010-12-22T18:35:58.249-06:002010-12-22T18:35:58.249-06:00I am a new Anonymous..
Anonymous 25 seems to be a...I am a new Anonymous..<br /><br />Anonymous 25 seems to be a author of this paper (which is not up yet) :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-27121662043577964282010-12-22T10:41:04.809-06:002010-12-22T10:41:04.809-06:00To Anonymous 25
Yes, I am totally aware of the re...To Anonymous 25<br /><br />Yes, I am totally aware of the restrictions of the other problems I cite. For makespan minimization on unrelated parallel machines, the author gives a proof of a better than 2 integrality gap for a configuration LP for the restricted version, not an algorthm. But that was not my point. My point was that like this result, those were also equally interesting results.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-34777713762509568862010-12-22T10:16:36.107-06:002010-12-22T10:16:36.107-06:00Typo! I meant anonymous #23Typo! I meant anonymous #23Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-23695157542551470872010-12-22T10:12:50.634-06:002010-12-22T10:12:50.634-06:00To Anonymous #21, I find it interesting that you a...To Anonymous #21, I find it interesting that you are complaining that the new result is for the shortest path metric of an unweighted graph. <br /><br />Yet the other results that you cite, you have mis-stated the main result. <br /><br />The result on max-flow is for undirected graphs, and is also approximate max flow. Certainly the real problem in this domain is directed, and exact. <br /><br />You also cite the improvement to scheduling unrelated parallel machines, but this result is not for the full generalized assignment problem, and is actually for the restricted assignment problem (where each job has some absolute size and for all machines, this job either costs its intrinsic cost, or infinity). <br /><br />In fact, the only result that you correctly state is the improved approximation guarantee for k-densest subgraph which is indeed for the k-densest subgraph problem in its full generality. If you are complaining about a paper not handling the fully general case, you should at least properly cite other results you mention.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-41598993875890973772010-12-22T06:00:08.759-06:002010-12-22T06:00:08.759-06:00Where's the paper? Not on the authors' web...Where's the paper? Not on the authors' web pages as far as I can see. "Tomorrow" was yesterday. Where is the paper posted?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47542431742015506482010-12-22T02:48:03.180-06:002010-12-22T02:48:03.180-06:00I agree with Anonymous 10. The result is not for g...I agree with Anonymous 10. The result is not for general metric but for shortest path metric and the improvement "c" is so tiny that authors even don't want to mention--This is certainly a very interesting result. But is this a breakthrough ? If this is indeed a breakthrough, then there are many others that should also be termed as breakthroughs--faster algorithm for maxflow, better than 2 approximation algorithm for makespan minimization on unrelated parallel machine, n^{1/4+epsilon} approximation for densest k subgraph etc. Calling this result a breakthrough and writing a blog like this appears to be a bit extreme to me.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-9052481520867685592010-12-22T02:35:51.574-06:002010-12-22T02:35:51.574-06:00I find this result very interesting, as I did Ryan...I find this result very interesting, as I did Ryan's and Mikkel's and Mihai's. Whether they are complexity or algorithms, both or neither, is not a fruitful discussion.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10710892754323611222010-12-21T21:15:23.436-06:002010-12-21T21:15:23.436-06:00Am I not able to have my own opinion?
Everyone...<i>Am I not able to have my own opinion?</i><br /><br />Everyone's entitled to their own opinion, no matter how wrong it is.<br /><br /><i>Its all algorithms. Some more theoretical, some more applied. </i><br /><br />There's no reason why you can't define algorithms this way if you choose, but it's a very broad definition, and likely to mislead the 90% of computer scientists who think algorithms research is generally more practical than complexity research. (I can't help suspecting that the broad definitions are designed to let super-theoretical algorithms researchers work on whatever they want while enjoying better job prospects than equally theoretical complexity researchers.)<br /><br /><i>Wikipedia is not a recognized source for academia, and uses an NP process through the use of pipe-lining servers, to collapse academia and media.</i><br /><br />You win the comment thread!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90268637774804491412010-12-21T17:44:49.115-06:002010-12-21T17:44:49.115-06:00That's right, I too demand that the Wikipedia ...That's right, I too demand that the Wikipedia reference be REMOVED. Wikipedia is not a recognized source for academia, and uses an NP process through the use of pipe-lining servers, to collapse academia and media.<br /><br />Again if TSP is NP, whether n! or "2 to the power of n", there is NO BREAKTHROUGH. Pascal's Triangle did the trick for me; therefore, pop up the paper.<br /><br />Still NP. Let me know when it's P. Let's get real, Google is violating the foundation of computer science ethics every second as I write this.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-18621012719569033112010-12-21T16:27:53.427-06:002010-12-21T16:27:53.427-06:00"solving some problem that was open for 34 ye..."solving some problem that was open for 34 years despite many attempts is a breakthrough"<br /><br />exactly what was "solved" here?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-66668021346547461282010-12-21T15:43:55.104-06:002010-12-21T15:43:55.104-06:00Michael -
Your definition of algorithms is quite n...Michael -<br />Your definition of algorithms is quite narrow, and it is no coincidence that it corresponds almost exactly to the subset of algorithms in which you work: "applied algorithms", per se. It is clear to me, and doubtless to many others, that you are suffering from the common though understandable psychological phenomenon that can be caricatured as: "Only what I do is real algorithms. Everything else is esoteric complexity.". Similarly, someone on the other end of the spectrum would say: "Only what I do is deep algorithmic theory, what michael does is not far removed from hacking shell scripts in your mom's basement.".<br /><br />Its all algorithms. Some more theoretical, some more applied. Stop with the bickering.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-15198888455355313122010-12-21T14:29:50.457-06:002010-12-21T14:29:50.457-06:00@Michael: where you see a "troll", and w...@Michael: where you see a "troll", and where I've relied on your comment? Am I not able to have my own opinion? Opinion that time and readers must decide what is a breakthrough, not Bill and Lance alone.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11539595882099186522010-12-21T14:13:58.203-06:002010-12-21T14:13:58.203-06:00Anon #13: You are one of those trolls that insist...Anon #13: You are one of those trolls that insists on ascribing statements to me that I didn't say. Please read what I said. <br /><br />I didn't say the result presented wasn't a breakthrough. Just that it wasn't an algorithmic breakthrough, in the sense that (as described) it didn't seem to be an algorithm that had been implemented or would be implemented in the near future, to improve some real-world computing process (or our understanding of that process). I think that was quite clear. <br /><br />The only statement I made regarding quality was "If it's a breakthrough..." Let me be clear that the "If" simply expressed my ignorance; it's not my area of study, and the paper apparently is not out yet, so I can't really judge. <br /><br />You can certainly read my comment on tabulation based hashing -- which, to be clear, is not my work, and is a work that ANOTHER THEORY BLOGGER recommended before me -- in the same light. It is in my area, and I think it's quite reasonable to me to express that it's interesting, and contrasts in many ways with the work reported here. I certainly didn't express any idea that hashing was algorithms and everything else was complexity. <br /><br />(Indeed, to be clear, and I think is clear in my original comment, some work on approximation algorithms is quite "algorithmic", in the sense that the algorithms developed are used in real systems, or the analysis is of algorithms used in real systems.)<br /><br />Finally, to be clear, anyone who uses the phrase, "...if I were you, I was [sic] more careful" is being quite unpleasant, as they're trying to sound threatening. Be polite. Or at least stand by your comments. <br /><br />Bill -- while I wouldn't say that having an algorithm coded up is either necessary or sufficient for "algorithms" work, it's a pretty good starting clue. Quite a bit of SODA (in my opinion) is complexity, not algorithms. Not that there's anything wrong with that; people should just be aware.Michael Mitzenmacherhttps://www.blogger.com/profile/02161161032642563814noreply@blogger.com