Posts Tagged ‘colloquium’

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

Monday, April 4th, 2016

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.

[Colloquium] Jinwoo Shin (신진우), Belief Propagation for Combinatorial Optimization

Tuesday, November 10th, 2015
(FYI: Colloquium)
Belief Propagation for Combinatorial Optimization
Jinwoo Shin (신진우)
Department of Electrical Engineering, KAIST
2015/11/19 4:15PM-5:15PM (Room 1501, Bldg. E6)
Belief propagation (BP) is a popular message-passing algorithm for computing a maximum-a-posteriori assignment in a graphical model. It has been shown that BP can solve a few classes of Linear Programming (LP) formulations to combinatorial optimization problems including maximum weight matching and shortest path. However, it has been not clear what extent these results can be generalized to. In this talk, I first present a generic criteria that BP converges to the optimal solution of given LP, and show that it is satisfied in LP formulations associated to many classical combinatorial optimization problems including maximum weight perfect matching, shortest path, network flow, traveling salesman, cycle packing and vertex cover. Using the criteria, we also construct the exact distributed algorithm, called Blossom-BP, solving the maximum weight matching problem over arbitrary graphs. In essence, Blossom-BP offers a distributed version of the celebrated Blossom algorithm (Edmonds 1965) jumping at once over many sub-steps of the Blossom-V (most recent implementation of the Blossom algorithm due to Kolmogorov, 2011). Finally, I report the empirical performance of BP for solving large-scale combinatorial optimization problems. This talk is based on a series of joint works with Sungsoo Ahn (KAIST), Michael Chertkov (LANL), Inho Cho (KAIST), Dongsu Han (KAIST) and Sejun Park (KAIST).

[Colloquium] Choongbum Lee (이중범), Ramsey numbers of graphs

Thursday, September 3rd, 2015
Ramsey numbers of graphs
Choongbum Lee
Department of Mathematics, UCSD, San Diego, CA, USA
2015/09/10 Thu 4:15PM-5:15PM
The Ramsey number of a graph G is the minimum integer n for which every edge coloring of the complete graph on n vertices with two colors admits a monochromatic copy of G. It was first introduced in 1930 by Ramsey, who proved that the Ramsey number of complete graphs are finite, and applied it to a problem of formal logic. This fundamental result gave birth to the subfield of Combinatorics referred to as Ramsey theory which informally can be described as the study of problems that can be grouped under the common theme that “Every large system contains a large well-organized subsystem.”
In this talk, I will review the history of Ramsey numbers of graphs and discuss recent developments.

[Colloquium] Jang Soo Kim, Combinatorics of orthogonal polynomials

Wednesday, March 25th, 2015
Combinatorics of orthogonal polynomials
Jang Soo Kim (김장수)
Department of Mathematics, Sungkyunkwan University, Suwon
2015/4/9 Thu 4:30PM-5:30PM (E6, Room 1501)
Orthogonal polynomials are a family of polynomials which are orthogonal with respect to certain inner product. The n-th moment of orthogonal polynomials is an important quantity, which is given as an integral. In 1983 Viennot found a combinatorial expression for moments using lattice paths. In this talk we will compute the moments of several important orthogonal polynomials using Viennot’s theory. We will also see their connections with continued fractions, matchings, set partitions, and permutations.

(Colloquium) Matt DeVos, On the structure of very small product sets

Monday, September 1st, 2014

FYI (Colloquium)

On the structure of very small product sets
Matt DeVos
Simon Fraser University, Canada
2014/09/25 Thursday 4:30PM – 5:30PM
Room 1501


Let A and B be finite nonempty subsets of a multiplicative group G, and consider the product set AB = { ab | a in A and b in B }. When |G| is prime, a famous theorem of Cauchy and Davenport asserts that |AB| is at least the minimum of {|G|, |A| + |B| – 1}. This lower bound was refined by Vosper, who characterized all pairs (A,B) in such a group for which |AB| < |A| + |B|. Kneser generalized the Cauchy-Davenport theorem by providing a natural lower bound on |AB| which holds in every abelian group. Shortly afterward, Kemperman determined the structure of those pairs (A,B) with |AB| < |A| + |B| in abelian groups. Here we present a further generalization of these results to arbitrary groups. Namely we generalize Kneser’s Theorem, and we determine the structure of those pairs with |AB| < |A| + |B| in arbitrary groups.