@inbook {IOPORT.06065672,
    author       = {Bl\"aser, Markus and Panagiotou, Konstatinos and Rao, B.V.Raghavendra},
    title        = {A probabilistic analysis of Christofides' algorithm.},
    year         = {2012},
    booktitle    = {Algorithm theory -- SWAT 2012. 13th Scandinavian symposium and workshops, Helsinki, Finland, July 4--6, 2012. Proceedings},
    isbn         = {978-3-642-31154-3},
    pages        = {225-236},
    publisher    = {Berlin: Springer},
    doi          = {10.1007/978-3-642-31155-0_20},
    abstract     = {Summary: Christofides' algorithm is a well known approximation algorithm for the metric travelling salesman problem. As a first step towards obtaining an average case analysis of Christofides' algorithm, we provide a probabilistic analysis for the stochastic version of the algorithm for the Euclidean traveling salesman problem, where the input consists of $n$ randomly chosen points in $[0,1]^{d }$. Our main result provides bounds for the length of the computed tour that hold almost surely. We also provide an experimental evaluation of Christofides's algorithm.},
    identifier   = {06065672},
}