I think there is a 4^k kernel for TSP .. On Sat, Mar 14, 2009 at 4:49 PM, Miroslav Balaz <gpsla...@googlemail.com>wrote:
> 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 >>>>>> >>>>>> >>>>>> >>>>>> >>>>>> >>>>> >>>>> >>>>> >>>>> >>>> >>> >>> >>> >> >> >> > > > > -- 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 -~----------~----~----~----~------~----~------~--~---
