AndrasSebo

Archive of posts with tag 'AndrasSebo'

  • András Sebő, The Salesman’s Improved Paths
    The Salesman’s Improved Paths
    András Sebő
    CNRS, Laboratoire G-SCOP, Université Grenoble-Alpes, France
    2016/05/04 Wed 4PM-5PM
    A new algorithm will be presented for the path tsp, with an improved analysis and ratio. After the starting idea of deleting some edges of Christofides’ trees, we do parity correction and eventual reconnection, taking the salesman to travel through a linear program determining the conditional probabilities for some of his choices; through matroid partition of a set of different matroids for a better choice of his initial spanning trees; and through some other adventures and misadventures.
    The proofs proceed by global and intuitively justified steps, where the trees do not hide the forests.
    One more pleasant piece of news is that we get closer to the conjectured approximation ratio of 3/2, and a hopefully last misadventure before finishing up this problem is that we still have to add 1/34 to this ratio, and also for the integrality gap. (The previous result was 8/5 with slight improvements.)
    This is joint work with Anke van Zuylen.
    Tags:

  • (Colloquium) András Sebő, Classical tools and recent advances in combinatorial optimization

    FYI: Colloquium of Dept. of Mathematical Sciences.

    Classical tools and recent advances in combinatorial optimization
    András Sebő
    CNRS, Laboratoire G-SCOP, Université Grenoble-Alpes, France
    2016/04/28 Thu 4:15PM-5:15PM (Room 1501, Bldg. E6-1)
    Combinatorial optimization has recently discovered new usages of probability theory, information theory, algebra, semidefinit programming, etc. This allows addressing the problems arising in new application areas such as the management of very large networks, which require new tools. A new layer of results make use of several classical methods at the same time, in new ways, combined with newly developed arguments.
    After a brief panorama of this evolution, I would like to show the new place of the best-known, classical combinatorial optimization tools in this jungle: matroids, matchings, elementary probabilities, polyhedra, linear programming.
    More concretely, I try to demonstrate on the example of the Travelling Salesman Problem, how strong meta-methods may predict possibilities, and then be replaced by better suited elementary methods. The pillars of combinatorial optimization such as matroid intersection, matchings, T-joins, graph connectivity, used in parallel with elements of freshmen’s probabilities, and linear programming, appropriately merged with newly developed ideas tailored for the problems, may not only replace difficult generic methods, but essentially improve the results. I would like to show how this has happened with various versions of the TSP problem in the past years (see results of Gharan, Saberi, Singh, Mömke and Svensson, and several recent results of Anke van Zuylen, Jens Vygen and the speaker), essentially improving the approximation ratios of algorithms.
    Tags:

Monthly Archives