I don't know any concrete real life problem, of course everyting real life problem that is in NP can be reducet to this problem. That includes timetable sheduling. | think there is no such problem in networks, because you need to know topology ad it has to be fixed. And if you want to make multicast, than it is faster if you do it in parallel way. There is still to few people in this group, you should encourage more people to yoin, if you want it to be usefull.
The metric TSP is somewhat approximable, and euclidean has PTAS 2009/3/14 Amina Maarouf <amina.maar...@gmail.com> > 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 -~----------~----~----~----~------~----~------~--~---
