May 13, 2016 Comments Off on Open problems
May 9, 2016 Comments Off on Schedule
Schedule
April 10 (Sun)
15:00-19:00 Check-in
19:00-21:00 Welcome Banquet
April 11 (Mon)
9:00-11:00 Introductions
11:00-12:00 2 long talks
- Laszlo Vegh: Rescaled coordinate descent methods for linear programming
- R. Ravi: Sending secrets swiftly [slide (pdf)]
14:00-15:00 Introductions
16:00-18:00 4 long talks
- Alina Ene: Routing under balance
- Debmalya Panigrahi: Online algorithms for multi-commodity network design [slide (pdf)]
- Tobias Momke: Airports and railways: facility location meets network design [slide (pdf)]
- Kristof Berczi: Degree-sequences of highly-connected digraphs
[slide (pdf)]
April 12 (Tue)
9:00-10:30 2 long talks + 2 short talks
- Alantha Newman: The alternating stock size problem and the gasoline puzzle (long)
- Yutaro Yamaguchi: How to make a bipartite graph DM-irreducible by adding edges (long) [slide (pdf)]
- Tamas Kiraly: Minimizing submodular functions on diamonds via generalized fractional matroid matchings (short) [slide (pdf)]
- Neil Olver: On the integrality gap of the cut LP for prize-collecting Steiner forest (short)
11:00-12:00 2 long talks
- Friedrich Eisenbrand: Max-sum diversity via convex programming
- Tasuku Soma: Non-convex compressed sensing with the sum-of-squares method [slide (pdf)]
14:00-15:00 2 long talks
- Andras Sebo: The salesman’s improved paths
- Anupam Gupta: The independent set problem on sparse graphs [slide (pdf)]
16:00-17:30 2 long talks + 2 short talks
- Seeun William Umboh: Recovering decompositions from noisy planar graphs (long)
- Bundit Laekhanukit: Approximating directed Steiner problems via tree embedding (long) [slide (pdf)]
- Yasushi Kawase: The secretary problem with a choice function (short)
- Zachary Friggstad: Local search yields a PTAS for k-means in doubling metrics (short)
April 13 (Wed)
9:00-10:30 2 long talks + 2 short talks
- Gyula Pap: Blocking arborescences (long) [slide (pdf)]
- Karthekeyan Chandrasekaran: Stabilizing unstable graphs through minimum modification (long)
- Naonori Kakimura: Threshold influence model for allocating advertising budgets (short) [slide (pdf)]
- Satoru Fujishige: A solution to the random assignment problem with a matroidal family of goods (short) [slide (pdf)]
11:00-12:00 2 long talks
- Seffi Naor: Multi-label classification with pairwise relations
- Sanjeev Khanna: Approximate matchings in dynamic graph streams [slide (pdf)]
13:30- Excursion & Banquet
April 14 (Thu)
9:00-10:30 2 long talks + 2 short talks
- Jakub Tarnawski: Constant-factor approximation for ATSP with two edge weights (long) [slide (pdf)]
- Venkatesan Guruswami: Coloring low-discrepancy hypergraphs and promise constraint satisfaction (long) [slide (pdf)]
- Nikhil Bansal: An improve approximation for weighted completion time on unrelated machines (short) [slide (pdf)]
- Hiroshi Hirai: Combinatorial algorithms for some multiflow problems and related network designs (short) [slide (pdf)]
11:00-12:00 2 long talks
- Viswanath Nagarajan: Approximation algorithms for inventory problems with submodular or routing costs [slide (pdf)]
- Jannik Matuschke: Recent developments in robust network flows
[slide (pdf)] (this file is locked by the same password as the open problems
14:00-16:00 Wrap-up
April 15 (Fri)
9:00-12:00 Free discussion
(for participants who wish to continue discussion)
Mar 28, 2016 Comments Off on Access to Shonan Village Center
Access to Shonan Village Center
- Access information can be found at http://www.shonan-village.co.jp/svc/access.html
- Jordan Train Route Finder http://www.jorudan.co.jp/english/
There are several routes from Narita airport, Haneda airport, or Tokyo area. In most of the cases, it is better to move by a train to either Zushi (JR) or Shin-Zushi (Keikyu) first, and then take a bus or a taxi.
From Narita airport to Zushi
A recommendation is to take JR Narita Express. To go to Zushi (JR), change at Musashi-Kosugi station to Shonan Shinjuku line, or change at Yokohama station to Yokosuka line. Be careful that all seats of Narita Express are reserved and you require an express ticket. Refer to time table of Narita Express.
From Haneda airport to Zushi or Shin-Zushi
There are several routes to go to Shin-Zushi (Keikyu) and Zushi (JR). Any routes require a few changes. Search the routes by Jordan Train Route Finder.
From Zushi (JR) or Shin-Zuhi (Keikyu) to Shonan Village Center
Take a bus or a taxi. As for the bus, take no. 16 for Shonan Village, which leaves from bus stop number 1 at both Zushi (JR) and Shin-Zushi (Keikyu). A one way bus ticket costs JPY 350. See the time tables at Zushi (JR) here and at Shin-Zushi (Keikyu) here (right column is the schedule on Sunday).
Mar 24, 2016 Comments Off on Participants
Participants
- Hyung-Chan An (Yonsei University)
- Satoru Iwata (University of Tokyo)
- Zachary Friggstad (University of Alberta)
- Sanjeev Khanna (University of Pennsylvania)
- Alina Ene (University of Warwick)
- Seeun William Umboh (TU Eindhoven)
- Anupam Gupta (Carnegie Mellon University)
- Neil Olver (VU Amsterdam)
- Andras Sebo (CNRS, Laboratoire G-SCOP, Grenoble)
- Hiroshi Hirai (Univerity of Tokyo)
- Kenjiro Takazawa (Kyoto University)
- Alantha Newman (CNRS, Grenoble)
- Viswanath Nagarajan (University of Michigan)
- Tobias Mömke (Saarland University)
- Bundit Laekhanukit (Weizmann Institute of Science)
- Debmalya Panigrahi (Duke University)
- Seffi Naor (Technion)
- Nikhil Bansal (TU Eindhoven)
- Friedrich Eisenbrand (EPFL)
- Tamás Király (ELTE Budapest)
- Gyula Pap (Eötvös University)
- Venkatesan Guruswami (Carnegie Mellon University)
- Karthekeyan Chandrasekaran (University of Illinois, Urbana-Champaign)
- Jannik Matuschke (TU Berlin)
- Naonori Kakimura (University of Tokyo)
- Kristóf Bérczi (MTA-ELTE, Budapest)
- Jakub Tarnawski (EPFL)
- Satoru Fujishige (Kyoto University)
- Tasuku Soma (University of Tokyo)
- Yasuhi Kawase (Tokyo Institute of Technology)
- Yutaro Yamaguchi (University of Tokyo)
- Ken-ichi Kawarabayashi (NII)
Jun 22, 2015 Comments Off on Organizers
Organizers
- Takuro Fukunaga (National Institute of Informatics)
- R. Ravi (Carnegie Mellon University)
- László Végh (London School of Economics)
Jun 22, 2015 Comments Off on Overview
Overview
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(log^2 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.