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.