Aproksymacja asymetrycznych wariantow problemu komiwojazera

Prelegent(ci)

Marcin Mucha

Afiliacja

Uniwersytet Warszawski

Termin

26 października 2006 12:15

Pokój

p. 5870

Seminarium

Seminarium "Algorytmika"

---

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.

---