Aproksymacja asymetrycznych wariantow problemu komiwojazera

Speaker(s)

Marcin Mucha

Affiliation

Uniwersytet Warszawski

Date

Oct. 26, 2006, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

Na najblizszym seminarium opowiem prace Haim Kaplan, Moshe Lewenstein, Nira Shafrir, Maxim Sviridenko "Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs". J. ACM 52(4): 602-626 (2005) (wczesniej extended abstract na FOCS 2003). Autorzy opracowali bardzo ladna i dosc ogolna technike aproksymacji asymetrycznych (tzn. funcja odleglosci nie jest symetryczna) wariantow problemow minTSP i maxTSP. Technika ta co prawda bazuje na programowaniu liniowym, ale zawiera takze bardzo eleganckie rozumowanie grafowe. Postaram sie aby moja prezentacja byla dostepna dla osob, ktore nie mialy okazji zajmowac sie aproksymacja. W szczegolnosci oznacza to, ze pokaze sporo rzeczy "standardowych" i nie bede wchodzil w bardziej zawile fragmenty omawianej pracy. Serdecznie zapraszam wszystkich zainteresowanych analiza algorytmow i kariera w biznesie taksowkowym.

---