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


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


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


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(n1/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.


  The system of instant Virginia Loans Online allows any adult U.S. citizen. But at the same time, it acts only with sexual arousal. Viagra Online has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.