I found a number of real life applications for the problem, like garbage collection, a version of postman problem, gas system construction.. I am looking for applications for the problem in networks, if any one can help.
On 3/14/09, Miroslav Balaz <gpsla...@googlemail.com> wrote: > > > NP what? > 2009/3/13 Amina Maarouf <amina.maar...@gmail.com> > >> this problem was proved to be NP in a conference paper published recently. >> >> >> >> On Fri, Mar 13, 2009 at 10:44 AM, Miroslav Balaz <gpsla...@googlemail.com >> > wrote: >> >>> maybe you are not wrong. but with high probability you are wrong. In >>> general case, this problem cannot ba approximated for any polynomialy >>> computable function f. >>> You can tell me the algorithm >>> or give me reason why trirvial reduction from TSP does not work here? >>> >>> 2009/3/13 Ajinkya Kale <kaleajin...@gmail.com> >>> >>> If i am not wrong there is a parameterized algorithm for this which is in >>>> P >>>> >>>> On Fri, Mar 13, 2009 at 3:40 AM, Miroslav Balaz < >>>> gpsla...@googlemail.com> wrote: >>>> >>>>> Ok this is NP-comlete... so no fast algorithm is known........ >>>>> >>>>> 2009/3/12 Amina Maarouf <amina.maar...@gmail.com> >>>>> >>>>> Dear All; >>>>>> >>>>>> I need some help on the following problem: >>>>>> >>>>>> Given a weighted graph ( v, e) and a set of marked vertices v' subset >>>>>> to v and a source node n. Find a cycle to that visits all vertices in v' >>>>>> and >>>>>> returns to n, such that the total cost is minimum. >>>>>> >>>>>> if anyone has ideas of algorithms, or applications that may map to >>>>>> this problem, it will be a great help to me. >>>>>> >>>>>> thanks >>>>>> >>>>>> amiiina >>>>>> >>>>>> >>>>>> >>>>> >>>>> >>>>> >>>>> >>>> >>>> >>>> >>>> -- >>>> >>>> Ciao, >>>> Ajinkya >>>> >>>> >>>> >>>> >>>> >>> >>> >>> >>> >> > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
