Sökning: "Mikael Goldmann"

Hittade 1 avhandling innehållade orden Mikael Goldmann.

1. 1. On Approximating Asymmetric TSP and Related Problems

   Författare :Anna Palbom; Mikael Goldmann; Lars Engebretsen; Peter Jonsson; KTH; []
   Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Komplexity theory; algorithms; approxiamtion; Computer science; Datalogi;

   Sammanfattning : In this thesis we study problems related to approximation of asymmetric TSP. First we give worst case examples for the famous algorithm due to Frieze, Gabiati and Maffioli for asymmetric TSP with triangle inequality. Some steps in the algorithm consist of arbitrary choices. To prove lower bounds, these choices need to be specified. LÄS MER