Combinatorial optimization is a field in the intersection of applied discrete mathematics, operations research, and computer science. The goal in the combinatorial optimization is design of efficient algorithms for computing a good quality solution to problems on discrete structures whose solution space is subject to combinatorial explosion. It has numerous applications in various fields of science, and is regarded as a fundamental technological advance in processing data for optimal solutions and structures. Clearly its importance is increasing with the growing applications of data science, and these algorithmic methods are also gathering much public attention nowadays in fields as diverse as online dating to package routing.

The theory of combinatorial optimization has recorded remarkable developments in the past fifty years. However, many fundamental questions still remain unsolved. An example of such questions is the one related to the traveling salesperson problem (TSP). This is the problem of computing a shortest tour vising all the cities in a map, where the distance between pair of cities is given as input. Since the number of tours corresponds to the number of cyclic permutations of the cities, it is an exponentially large number and hence a victim of combinatorial explosion. Nevertheless, for the TSP with distances that obey the triangle inequality, Christofides presented an elegant 1.5-approximation algorithm in 1976. This method is guaranteed to output a tour of length at most 1.5 times the shortest length of arbitrary feasible solution in time that grows with a polynomial dependence on the number of cities. One of the most popular current questions in combinatorial optimization asks whether there is a polynomial-time 4/3-approximation algorithm for metric TSP. In 2011, several groups made progress for a special case defined by the shortest path hop distances in undirected graphs. They gave approximation algorithms that achieve approximation ratios better than 1.5 for this special case. However there is still no known algorithm that outperforms Christofides’ algorithm in instances with arbitrary metrics.

Another example is the bin packing problem. In the bin packing problem, we are given a set of items whose size are specified by real numbers in [0,1], and we are asked to pack the items into the smallest number of bins of size one. Several groups of researchers proved that various greedy algorithms achieve constant approximation for the problem in 1980’s. Then, in 1982, Karmarkar and Karp presented an algorithm that computes a packing using at most OPT + O(log2 OPT) bins, where OPT denotes the number of bins used by the optimal solutions. Their algorithm is based on a linear programming relaxation of the problem formulated by Gilmore and Gomory in 1961. Their analysis is built on a deep understanding on the structure of the relaxation. Since their work, there was no significant progress for three decades although it is conjectured that the bin packing problem has an algorithm that computes a packing with OPT+1 bins. In 2013, Rothvoß improved the algorithm of Karmarkar and Karp. His algorithm computes a solution with OPT + O(log OPT log log OPT). He improved the rounding phase of method of Karmarker and Karp using recently developed algorithmic tools from discrepancy theory.

Besides these examples, we have numerous combinatorial optimization problems for which technical breakthrough are expected. To advance development of combinatorial optimization further, wide collaboration among researchers is necessary. The purpose of this meeting is to stimulate communication among researchers who are active in this field. To enable this, we plan to invite leading and active researchers, and provide an opportunity to share the most recent information on the new findings in this field.