## Invited Session Tue.1.H 3008

#### Tuesday, 10:30 - 12:00 h, Room: H 3008

**Cluster 2: Combinatorial optimization** [...]

### LP based approximation algorithms for location and routing

**Chair: Viswanath Nagarajan**

**Tuesday, 10:30 - 10:55 h, Room: H 3008, Talk 1**

**JarosÅ‚aw Byrka**

Fault-tolerant facility location: A randomized dependent LP-rounding algorithm

**Coauthors: Aravind Srinivasan, Chaitanya Swamy**

**Abstract:**

We give a new randomized LP-rounding 1.725-approximation

algorithm for the metric Fault-Tolerant Uncapacitated Facility Location

problem. This improves on the previously best known 2.076-approximation

algorithm of Swamy & Shmoys. To the best of our knowledge, our work

provides the first application of a dependent-rounding technique in the

domain of facility location. The analysis of our algorithm benefits from, and extends, methods developed for Uncapacitated Facility Location; it also helps uncover new properties of the dependent-rounding approach. An important concept that we develop is a novel, hierarchical clustering scheme. Typically, LP-rounding approximation algorithms for facility location problems are based on partitioning facilities into disjoint clusters and opening at least one facility in each cluster. We extend this approach and construct a laminar family of clusters, which then guides the rounding procedure: this allows us to exploit properties of dependent rounding, and provides a quite tight analysis resulting in the improved approximation ratio.

**Tuesday, 11:00 - 11:25 h, Room: H 3008, Talk 2**

**Anna Blasiak**

Improved approximation algorithms for the minimum latency problem via prize-collecting paths

**Coauthor: Aaron Archer**

**Abstract:**

The minimum latency problem (MLP) is a well-studied variant of the traveling salesman problem. In it, the server's goal is to minimize average latency of clients prior to being served, rather than total latency of the server.

%

Unlike most combinatorial optimization problems, the MLP is NP-hard even on trees (Sitters 2001). Furthermore, all MLP approximation algorithms known for general metrics are based on trees, and the best ratio known for both cases was *3.59*, prior to our work.

We give a *3.03*-approximation algorithm for trees, the first improvement since 1996. Our *3.03*-approximation algorithm works for any class of graphs in which the related prize-collecting path problem is solvable in polynomial time, like graphs of constant treewidth. More generally, for any class of graphs that admit a Lagrangian-preserving *β*-approximation algorithm for the prize-collecting path problem, we can use our algorithm as a black box to achieve a *3.03β*-approximation for the MLP.

%

Our analysis uses a solution of an infinite-dimensional linear program to analyze a finite-dimensional factor-revealing linear program.

**Tuesday, 11:30 - 11:55 h, Room: H 3008, Talk 3**

**Zachary Lorne Friggstad**

A logarithmic approximation for the directed latency problem

**Coauthors: Mohammad R. R. Salavatipour, Zoya Svitkina**

**Abstract:**

In the directed latency problem, we are given an asymmetric metric and a start node *s*. The goal is to find a Hamiltonian path starting at *s* that minimizes the average distance of the nodes from the start of the path. An *O(**log* n) approximation for this problem will be presented whose analysis also bounds the integrality gap of an LP relaxation by the same factor. This improves on the previous best approximation of *O(n*^{1/2 + ε}) by Nagarajan and Ravi. Our approach requires bounds on integrality gaps of LP relaxations for the asymmetric traveling salesman path problem and a variant using two paths.