Invited Session Thu.3.H 0106

Thursday, 15:15 - 16:45 h, Room: H 0106

Cluster 13: Logistics, traffic, and transportation [...]

Logistics and transportation


Chair: Arash Asadpour



Thursday, 15:15 - 15:40 h, Room: H 0106, Talk 1

Arash Asadpour
Rounding by sampling and an O(log n / log log n) approximation algorithm for ATSP

Coauthors: Michel Goemans, Aleksander Madry, Shayan Oveis Gharan, Amin Saberi


We study the relation between the integer linear programming models for a class of discrete optimization problems and their relaxations. I will introduce a new probabilistic technique for transforming the optimal solutions of these relaxed programs into the near-optimal solutions for the original discrete problems. The technique is based on sampling from maximum entropy distributions over combinatorial structures hidden in such problems.
In order to present the idea, I will go through a generalization of the Traveling Salesman Problem (Asymmetric TSP) and show how we can improve the worst-case performance guarantee for this problem after almost 30 years. We will also see other applications of this technique in assignment problems and fair resource allocation.



Thursday, 15:45 - 16:10 h, Room: H 0106, Talk 2

Nitish Korula
Prize-collecting Steiner network problems on planar graphs

Coauthors: Mohammadhossein Bateni, Chandra Chekuri, Alina Ene, Mohammadtaghi Hajiaghayi, Daniel Marx


In this paper, we reduce Prize-Collecting Steiner TSP (PCTSP), Prize-Collecting Stroll (PCS), Prize-Collecting Steiner Tree (PCST), Prize-Collecting Steiner Forest (PCSF), and more generally Submodular Prize-Collecting Steiner Forest (SPCSF), on planar graphs (and on bounded-genus graphs) to the corresponding problems on graphs of bounded treewidth.
More precisely, for each of the mentioned problems, an α-approximation algorithm for the problem on graphs of bounded treewidth implies an (α + ε)-approximation algorithm for the problem on planar (and bounded-genus) graphs, for any constant ε > 0. PCS, PCTSP, and PCST can be solved exactly on graphs of bounded treewidth and hence we obtain a PTAS for these problems on planar and bounded-genus graphs. In contrast, we show that PCSF is APX-hard on series-parallel graphs, which are planar graphs of treewidth at most 2. Besides ruling out a PTAS for PCSF on planar graphs and bounded-treewidth graphs, this result is also interesting since it gives the first provable hardness separation between the approximability of a problem and its prize-collecting version. (We show similar hardness for Euclidean PCSF.)



Thursday, 16:15 - 16:40 h, Room: H 0106, Talk 3

Mohammadhossein Bateni
PTAS for planar multiway cut

Coauthors: Mohammadtaghi Hajiaghayi, Philip Klein, Claire Mathieu


Given an undirected graph with edge lengths and a subset of nodes (called the terminals), a multiway cut (also called a multi-terminal cut) problem asks for a subset of edges with minimum total length and whose removal disconnects each terminal from the others. It generalizes the min st-cut problem but is NP-hard for planar graphs and APX-hard for general graphs. We give a polynomial-time approximation scheme for this problem on planar graphs. We prove the result by building a novel spanner for multiway cut on planar graphs which is of independent interest.


  There are three major facts that should be watched out for in all payday loans in the United States. In this section we give only a brief summary recommendation for admission of Levitra. Full information can be found in the instructions for receiving medications with vardenafil.