KAIST Discrete Math Seminar

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.

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.

A graph is (d₁, …, d_r)-colorable if its vertex set can be partitioned into r sets V₁, …, V_r where the maximum degree of the graph induced by V_i is at most d_i for each i in {1, …, r}.
Given r and d₁, …, d_r, determining if a (sparse) graph is (d₁, …, d_r)-colorable has attracted much interest.
For example, the Four Color Theorem states that all planar graphs are 4-colorable, and therefore (0, 0, 0, 0)-colorable.
The question is also well studied for partitioning planar graphs into three parts.
For two parts, it is known that for given d₁ and d₂, there exists a planar graph that is not (d₁, d₂)-colorable.
Therefore, it is natural to study the question for planar graphs with girth conditions.
Namely, given g and d₁, determine the minimum d₂=d₂(g, d₁) such that planar graphs with girth g are (d₁, d₂)-colorable. We continue the study and ask the same question for graphs that are embeddable on a fixed surface.
Given integers k, γ, g we completely characterize the smallest k-tuple (d₁, …, d_k) in lexicographical order such that each graph of girth at least g that is embeddable on a surface of Euler genus γ is (d₁, …, d_k)-colorable.
All of our results are tight, up to a constant multiplicative factor for the degrees d_i depending on g.
In particular, we show that a graph embeddable on a surface of Euler genus γ is (0, 0, 0, K₁(γ))-colorable and (2, 2, K₂(γ))-colorable, where K₁(γ) and K₂(γ) are linear functions in γ.This talk is based on results and discussions with H. Choi, F. Dross, L. Esperet, J. Jeong, M. Montassier, P. Ochem, A. Raspaud, and G. Suh.</p>

In this talk, I attempt to provide a comprehensive introduction to the matroid properties that hold for almost all matroids.
Welsh conjectured that almost all matroids are paving, open for nearly 50 years. If true, the properties of paving matroids translate to almost all matroids, such as non-representability, concentrated ranks, high connectivity and so on. We shall see the related properties that are shown to hold for almost all matroids with some of the proofs. An overview of recent progress and possible further directions will also be presented.

Max-product Belief Propagation (BP) is a popular message-passing algorithm for computing a Maximum-A-Posteriori (MAP) assignment over a distribution represented by a Graphical Model (GM). It has been shown that BP can solve a number of combinatorial optimization problems including minimum weight matching, shortest path, network flow and vertex cover under the following common assumption: the respective Linear Programming (LP) relaxation is tight, i.e., no integrality gap is present. However, when LP shows an integrality gap, no model has been known which can be solved systematically via sequential applications of BP. In this paper, we develop the first such algorithm, coined Blossom-BP, for solving the minimum weight matching problem over arbitrary graphs. Each step of the sequential algorithm requires applying BP over a modified graph constructed by contractions and expansions of blossoms, i.e., odd sets of vertices. Our scheme guarantees termination in O(n²) of BP runs, where n is the number of vertices in the original graph. In essence, the Blossom-BP offers a distributed version of the celebrated Edmonds’ Blossom algorithm by jumping at once over many sub-steps with a single BP. Moreover, our result provides an interpretation of the Edmonds’ algorithm as a sequence of LPs.
This is a joint work with Sejun Park, Michael Chertkov, and Jinwoo Shin.