Seminars in April 2016

  • (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:

  • Hyung-Chan An (안형찬), LP-based Algorithms for Capacitated Facility Location
    LP-based Algorithms for Capacitated Facility Location
    Hyung-Chan An (안형찬)
    Department of Computer Science, Yonsei University, Seoul
    2016/4/6 Wed 4PM-5PM (Room 3433 of Bldg. E6-1)
    Linear programming has played a key role in the study of algorithms for combinatorial optimization problems. In the field of approximation algorithms, this is well illustrated by the uncapacitated facility location problem. A variety of algorithmic methodologies, such as LP-rounding and primal-dual method, have been applied to and evolved from algorithms for this problem. Unfortunately, this collection of powerful algorithmic techniques had not yet been applicable to the more general capacitated facility location problem. In fact, all of the known algorithms with good performance guarantees were based on a single technique, local search, and no linear programming relaxation was known to efficiently approximate the problem.
    In this paper, we present a linear programming relaxation with constant integrality gap for capacitated facility location. We demonstrate that the fundamental theories of multi-commodity flows and matchings provide key insights that lead to the strong relaxation. Our algorithmic proof of integrality gap is obtained by finally accessing the rich toolbox of LP-based methodologies: we present a constant factor approximation algorithm based on LP-rounding.
    Joint work with Mohit Singh and Ola Svensson.
    Tags:

Monthly Archives