tag:blogger.com,1999:blog-4115025577315673827.post61427214086507069..comments2019-10-08T12:02:40.465+05:30Comments on CSE Blog - quant, math, computer science puzzles: Sweet Heart Mix TapeUnknownnoreply@blogger.comBlogger8125tag:blogger.com,1999:blog-4115025577315673827.post-24468037609185986442010-02-26T10:50:47.132+05:302010-02-26T10:50:47.132+05:30Elegant proof. Thanx. You proved that the problem ...Elegant proof. Thanx. You proved that the problem is atleast as hard as travelling salesman problem.<br /><br />Thanx!Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-49394206837369133342010-02-24T02:34:11.648+05:302010-02-24T02:34:11.648+05:30Yes. Traveling Salesman Path Problem (not returnin...Yes. Traveling Salesman Path Problem (not returning to first node) is also in NP. We can reduce it via regular TSP.<br /><br />First, model the TSPP problem as finding a path starting at a given vertex(s), visiting all vertices and ending at given vertex(t). Our Sweet-heart-mix-tape problem can use multiple calls to TSPP involving all combinations of s,t vertices to find the best solution.<br /><br />Now we will prove TSPP is NP via a reduction from TSP. Given a TSP problem instance convert to TSPP instance as follows. Take a random single vertex(v) and split it into two vertices(a,b) and distance a->b = b->a = 0. Now finding the TSPP involving source as 'a' and dest as 'b', will give solution for TSP.<br /><br />So TSPP is equally hard as TSP. As TSP in NP, TSPP is also in NP.<br /><br />I also think the asymmetric price function (price(si,sj) may not be same as price(sj,si)) in our problem does not play much role.<br /><br />Let me know your views.Rajendran Thirupugalsamyhttps://www.blogger.com/profile/13019807581860813459noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-55727746909350318972010-02-23T17:25:40.811+05:302010-02-23T17:25:40.811+05:30@Ramdas.. finding the solution with dynammic progr...@Ramdas.. finding the solution with dynammic programming is easy.. (The solution by Nikhil)<br /><br />The point where I am not clear is that is this problem at least as hard as TSP? Can one prove some relation between this problem and TSP?Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-43955589538226327722010-02-22T03:23:12.080+05:302010-02-22T03:23:12.080+05:30isnt this a pretty normal-ish problem? i think we ...isnt this a pretty normal-ish problem? i think we discussed this at work once, and i got it in a while...Ya, I Am A Dastardhttps://www.blogger.com/profile/04386601441575337262noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-34442125075525222442010-02-20T21:29:25.126+05:302010-02-20T21:29:25.126+05:30Thanx Nikhil, Rajendran and "inexorable"...Thanx Nikhil, Rajendran and "inexorable" for the solution<br /><br />I too solved it in the same way. But is it really the travelling salesman problem? Not returning to the first node makes a difference. Can someone prove that this problem is indeed as hard as TSP.Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-83390554421862387882010-02-20T05:58:11.989+05:302010-02-20T05:58:11.989+05:30This is travelling salesman problem. you would nee...This is travelling salesman problem. you would need to add an additional start vertex whose distance to & from all given vertices is 0. TSP can be done O((n^2)*(2^n)) using dynamic programming.inexorablehttps://www.blogger.com/profile/00282410997215304376noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-86524249234291757612010-02-20T00:17:38.693+05:302010-02-20T00:17:38.693+05:30You are right Nikhil.
Another similar problem is ...You are right Nikhil.<br /><br />Another similar problem is finding n*n*2^n solution for Travelling Salesman Problem using dynamic programming.<br /><br />Infact, we can model this problem as a directed graph wherein, each song creates a vertex and the price value makes the distance. Now, what we need is solution to asymmetric TSP (except salesperson does not need to visit the starting city).<br /><br />The dynamic programming solution for this follows the same way as Nikhil described and can be found <a href="http://www.lsi.upc.edu/~mjserna/docencia/algofib/P07/dynprog.pdf" rel="nofollow">here</a>.Rajendran Thirupugalsamyhttps://www.blogger.com/profile/13019807581860813459noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-82104119088511032582010-02-19T23:10:39.426+05:302010-02-19T23:10:39.426+05:30Consider the subproblem of finding the best schedu...Consider the subproblem of finding the best schedule when we have a subset say S of songs available to play. <br /><br />Denote by best(i,S) as best cost of arranging songs of set S with ith song as the first element. <br />Our final aim is max over i ( best (i,U) )<br />where U is the universal set of songs.<br /><br />Now we can easily compute best(i,S) in terms of smaller such values :<br /><br />if i does not belong to S<br /> best(i,S)= -INF <br />else <br /> best(i,S)= max over j ( best(j,S-{i} )+cost(i,j) <br /><br />with appropriate base cases .<br /><br />We have n*2^n subproblem to solve & each one requires O(n) time. Hence the solution.Nikhil Garghttps://www.blogger.com/profile/00137167173637522039noreply@blogger.com