## 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**

**Abstract:**

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**

**Abstract:**

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**

**Abstract:**

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.