tag:blogger.com,1999:blog-786333285568106173.post6391271424144424298..comments2015-09-30T06:04:24.828-04:00Comments on WebDiarios de Motocicleta: Balkan Olympiad (Day 2)Mihaihttp://www.blogger.com/profile/11599372864611039927noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-786333285568106173.post-72384045585968143062011-07-25T17:28:57.298-04:002011-07-25T17:28:57.298-04:00yay, this made my day! Thanks for posting interest...yay, this made my day! Thanks for posting interesting stuff and see you at wads in three weeks. best, timAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-77997999421529753572011-07-25T12:41:54.954-04:002011-07-25T12:41:54.954-04:00Yes, eternal glory for you. :)
Too bad you didn&#...Yes, eternal glory for you. :)<br /><br />Too bad you didn't sign, we don't know whom the glory goes to. But feel free to correct this.Mihaihttp://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-77909302989953787662011-07-25T03:47:41.754-04:002011-07-25T03:47:41.754-04:00A first guess about the first problem: By the geom...A first guess about the first problem: By the geometry of the objective, observe that there is some 0 <= s <= 1 such that minimizing (total A-cost)*(total B-cost) is equivalent to minimizing s*(total A-cost) + (1-s)*(total B-cost). However, trying "all" s does not work, but we can iteratively increase s and update the spanning tree whenever necessary. Every time we update, we also compute (total A-cost)*(total B-cost). Its not clear that we only have to update a polynomial number of times. To see this, recall that a minimum spanning tree can be constructed via a simple greedy procedure (always add the smallest outgoing edge). On the other hand, for any pair of edges a and b, there is exactly one "breakpoint" s' such that we prefer edge a for s <= s' and b for s > s'. This gives that there are at most n^2 breakpoints. Eternal glory?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-50343800155525125812011-07-23T11:08:06.268-04:002011-07-23T11:08:06.268-04:00Yes, Bob's queries are adaptive.
Not being an...Yes, Bob's queries are adaptive.<br /><br /><i>Not being an algorithms person, I'm curious how often publishable results of form "Problem X is in poly-time" appear</i><br /><br />Very often in certain areas, e.g. approximation algorithms and fixed-parameter tractability. As an algorithms person myself, I often don't find such results interesting, since most algorithmic work is hidden inside a few big hammers that get used.<br /><br />Here I'm stating the goal as "poly time" to make the difficulty close to the Olympiad problem. In the Olympiad, you could get full score by doing "something reasonable" without analyzing the run time (of course).Mihaihttp://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-17414217714518870212011-07-22T20:17:00.765-04:002011-07-22T20:17:00.765-04:00Interesting stuff. Two questions:
1) in Compare,...Interesting stuff. Two questions:<br /><br />1) in Compare, Bob's queries are adaptive, right?<br /><br />2) On the TimeIsMoney problem: Not being an algorithms person, I'm curious how often publishable results of form "Problem X is in poly-time" appear. Of course, you should try to optimize the runtime, but how often is just placing in poly-time a real achievement? And how many open problems of this type get solved in a given year? I'd be curious to hear anyone's impressions on this.Anonymousnoreply@blogger.com