tag:blogger.com,1999:blog-786333285568106173.post7241072240485458046..comments2024-01-25T01:05:59.968-05:00Comments on WebDiarios de Motocicleta: Morse meets HammingMihaihttp://www.blogger.com/profile/11599372864611039927noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-786333285568106173.post-33022672527240257632009-02-09T11:26:00.000-05:002009-02-09T11:26:00.000-05:00You can see, that I've mentioned, that it is easy ...You can see, that I've mentioned, that it is easy case. :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-45241946407098795702009-02-02T00:37:00.000-05:002009-02-02T00:37:00.000-05:00ilyaraz, the problem you mention assumes the proba...ilyaraz, the problem you mention assumes the probabilities are uniform, so it is quite different.<BR/><BR/>Chandra, a PTAS is known:<BR/>http://www.cse.ust.hk/~golin/pubs/LOP_PTAS_STOC.pdfMihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-36425378917325479282009-02-01T09:10:00.000-05:002009-02-01T09:10:00.000-05:00this is the easy case of this problem:http://proje...this is the easy case of this problem:<BR/><BR/>http://projecteuler.net/index.php?section=problems&id=219Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-74280397154241361242009-01-31T19:11:00.000-05:002009-01-31T19:11:00.000-05:00What is known if we settle for a code that is with...What is known if we settle for a code that is within say (1+\eps) of the optimal code?<BR/><BR/>thanksChandrahttps://www.blogger.com/profile/00057069075567569157noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-53775303080744520422009-01-31T18:32:00.000-05:002009-01-31T18:32:00.000-05:00I was working on this with Mordecai for a while. W...I was working on this with Mordecai for a while. We were trying to prove it's NP-hard. We have another problem P' such that if P' is NP-hard, then the problem you showed in the post is probably NP-hard, and P' is much simpler and it should be reasonable to prove it's NP-hard (we didn't manage to). I won't post here what P' is, but anyone reading this should be free to email me and I'll tell them what the problem is.Anonymousnoreply@blogger.com