%% ToC#313 Chekuri - Pal au.bib 10-04-07 ed: LB 10-04-07 ed: DB 10-08-07

@Book{networkflowbook,
  author = {Ravindra K. Ahuja and Thomas L. Magnanti and James B. Orlin},
  title = {Network Flows},
  year = {1993},
  publisher = {Prentice Hall}
}


@InProceedings{BachrachCHMRS05,
  author = {Abraham Bachrach and Kevin Chen and Chris Harrelson and
            Radu Mihaescu and Satish Rao and Apurva Shah},
  title = {Lower Bounds for Maximum Parsimony with Gene Order Data},
  booktitle = {Proc. 3rd RECOMB Satellite Workshop on Comparative Genomics (RCG'05)}, 
  publisher = "Springer",
  series = {LNCS},
  pages = {1--10},
  year = 2005,
  eprint="springer:761n756g03752l46"
}



@InProceedings{Bansaletal,
  author = {Nikhil Bansal and Avrim Blum and Shuchi Chawla and Adam Meyerson},
  title = {Approximation Algorithms for Deadline-{TSP} and Vehicle Routing with
           Time-Windows},
  booktitle =   {Proc. 36th STOC},
  publisher = {ACM Press},
  pages = {166-174},
  year = 2004,
  eprint="stoc:10.1145/1007352.1007385"
}



@InProceedings{Blaser02,
  author = {Marcus Bl\"aser},
  title = {A New Approximation Algorithm for the Asymmetric {TSP} with 
          Triangle Inequality},
 booktitle = {Proc. 13th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA'02)},
  pages = {638-645}, 
  publisher = "SIAM",
  year = 2002,
  eprint="soda:644213"
}


@Article{Blumetal,
  author = {Avrim Blum and Shuchi Chawla and David Karger and Terran Lane and  
            Adam Meyerson and Maria Minkoff},
  title = {Approximation Algorithms for Orienteering and Discounted-Reward {TSP}},
  journal = {SIAM Journal on Computing},
  volume = 37,
  issue = 2,
  year = 2007,
  pages = {653--670},
  eprint = "sicomp:10.1137/050645464"
}


@InProceedings{CharikarMRS97,
  author = {Moses Charikar and Rajeev Motwani and Prabhakar Raghavan and 
            Craig Silverstein},
  title = {Constrained {TSP} and lower power computing},
  year = 1997,
  pages = {104--115},
  booktitle = {Proc. First Workshop on Algorithms and Data Structures (WADS'97)},
  eprint = "wads:d5764136r2147633"
}


@InProceedings{CharikarGK04,
  author = {Moses Charikar and Michel Goemans and Howard Karloff},
  title = {On the Integrality Ratio for Asymmetric {TSP}},
  year = 2004,
  pages = {101--107},
  booktitle = "Proc. 45th FOCS",
  publisher = "IEEE Computer Society",
  eprint = "FOCS:10.1109/FOCS.2004.45"
}


@InProceedings{ChekuriP05,
  author = {Chandra Chekuri and Martin P\'al},
  title = {A Recursive Greedy Algorithm for Walks in Directed Graphs},
  year = 2005,
  pages = {245--253},
  booktitle = "Proc. 46th FOCS",
  publisher = "IEEE Computer Society",
  eprint = "FOCS:10.1109/SFCS.2005.9"
}


@InProceedings{ChekuriKP07,
  author = {Chandra Chekuri and  Nitish Korula and Martin P\'al},
  title = {Improved Algorithms for Orienteering and Related Problems},
  year = 2008,
 booktitle = {Proc. 19th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA'08)},
  publisher = "SIAM",
  note = {To appear.}
}


@TechReport{Christofides76,
  author = {Nicos Christofides},
  title = {Worst-case analysis of a new heuristic for the traveling
           salesman problem},
  booktitle = {GSIA Technical report}, 
  institution = {CMU},
  year = 1976
}


@Article{Chvatal79,
  author = {Va\v{s}ek Chv\'atal},
  title = {A greedy heuristic for the set-covering problem},
  journal = {Mathematics of Operations Research}, 
  volume = 4,
  pages = {233--235},
  year = 1979
}


@InProceedings{FeigeS07,
  author = {Uriel Feige and Mohit Singh},
  title = {Improved approximation ratios for traveling salesperson 
           tours and paths in directed graphs},
  booktitle = {Proc. 10th Internat. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'07)},
  publisher = {Springer},
  series = {LNCS},
  volume = {4627},
  year = 2007,
  pages = {104--118},
  eprint="springer:u201633r5096547w"
}


@Article{FriezeGM82,
  author = {Alan Frieze and G. Galbiati and M. Maffioli},
  title = {On the worst-case performance of some algorithms for
           the asymmetric traveling salesman problem},
  journal = {Networks},
  volume = 12,
  pages = {23--39},
  year = 1982,
  doi = "10.1002/net.3230120103"
}


@Book{TSP_book2,
  editor = {G. Gutin and A.P. Punnen},
  title = {Traveling Salesman Problem and Its Variations},
  publisher = {Springer-Verlag},
  address = {Berlin},
  year = 2002
}


@Article{GHKR98,
  author = {N. Guttmann-Beck and R. Hassin and S. Khuller and B. Raghavachari},
  title = {Approximation Algorithms with Bounded Performance Guarantees for 
           the Clustered Traveling Salesman Problem},
  journal = {Algorithmica},
  volume = 28,
  pages = {422--437},
  year =  2000,
  note = {Preliminary version in {\em Proc.\ of FSTTCS}, 1998.},
  eprint="algorithmica:38vtl0dhpg55l0au"
}


@Article{Hoogeveen91,
  author = {J. Hoogeveen},
  title = {Analysis of {Christofides'} heuristic: Some paths are more 
           difficult than cycles},
  journal = {Operations Research Letters}, 
  volume = 10,
  number = 5,
  pages = {291--295}, 
  year = 1991,
  eprint="elsevier:10.1016/0167-6377(91)90016-I"
}


@Article{KaplanLSS03,
  author = {H. Kaplan and M. Lewenstein and N. Shafir and M. Sviridenko},
  title = {Approximation Algorithms for Asymmetric {TSP} by Decomposing Directed Regular Multidigraphs},
  journal = {Journal of the ACM},
  volume = 52,
  year = 2005,
  pages = {602--626},
  eprint = "JACM:10.1145/1082036.1082041"
}


@Unpublished{KleinbergW98,
  title = {Unpublished note},
  author = {Jon Kleinberg and David Williamson},
  year = 1998
}


@Article{LamN05,
  author = 	 {Fumei Lam and Alantha Newman},
  title = 	 {Traveling salesman path problems},
  journal = 	 {Mathematical Programming A},
  year = 	 {2006},
  note = 	 {Online publication date 1 Nov 2006},
  eprint="springer:7773743425mx673l"
}



@Book{TSP_book1,
  editor = {E. Lawler and {J.\,K.} Lenstra and {A.\,H.\,G. Rinnooy} Kan and D. Shmoys},
  title = {The Traveling Salesman Problem: A Guided Tour of
           Combinatorial Optimization},
  publisher = {John Wiley \& Sons Ltd.},
  year = 1985
}


@InProceedings{NagarajanR07,
  author = {V. Nagarajan and R. Ravi},
  title = {Poly-logarithmic Approximation Algorithms for Directed 
           Vehicle Routing Problems},
  booktitle = {Proc. 10th Internat. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'07)},
  publisher = {Springer},
  series = {LNCS},
  volume = {4627},
  year = 2007,
  pages = {257--270},
  eprint="springer:vn2516l2l015u7u1"
}


@Book{vehicle_book,
  title = {The Vehicle Routing Problem},
  editor = {P. Toth and D. Vigo},
  series = {SIAM Monographs on Discrete Mathematics and Applications},
publisher = {SIAM},
  address = {Philadelphia},
  year =  2002
}


@MastersThesis{Williamson90,
  author = {David Williamson},
  title = {Analysis of the Held-Karp heuristic for the traveling
           salesman problem},
  school = {MIT Computer Science Department}, 
  year = 1990,
  url="http://www.lcs.mit.edu/publications/specpub.php?id=1046"
}


@TechReport{Williamson99,
  author = {David Williamson},
  title = {Lecture Notes on Approximation Algorithms},
  booktitle = {IBM Research Report},
  institution = {IBM},
  number = {RC 21273}, 
  month = {February},
  year =  1999
}





@Article{YoungTO91,

  author = {N. Young and R. Tarjan and J. Orlin},

  title = {Faster parametric shortest path and minimum balance algorithms},

  journal = {Networks}, 

  volume = 21,

  number = 2,

  pages = {205--221},

  year = 1991,

  doi = "10.1002/net.3230210206",

  eprint="arxiv:cs/0205041"

}