Handelsresandens problem i asymmetrisk graf
Talare: Anna Palbom, NADA, KTH
Tid: Må 2002-05-27 kl 14.15 - On 2013-10-23 kl 12.00
Plats: room 1537
Abstrakt:
Handelsresandens problem med symmetrisk kostnadsfunktion är ett klassiskt datalogiproblem. Det är NP-svårt att lösa exakt, men när kostnadsfunktionen uppfyller triangelolikheten ger Christofides algoritm (1976) en lösning i polynomisk tid med vikt högst en faktor 3/2 från optimum.
Versionen med asymmetrisk kostnadsfunktion som uppfyller triangelolikheten är inte lika välstuderad. Jag kommer att ge en översiktlig beskrivning av tidigare resultat och diskutera olika möjligheter till forskning kring handelsresandens problem med asymmetrisk kostnadsfunktion. Inga förkunskaper krävs.