Approximating ATSP by Relaxing Connectivity

The standard LP relaxation of the asymmetric traveling salesman problem has been conjectured to have a constant integrality gap in the metric case. We prove this conjecture when restricted to shortest path metrics of node-weighted digraphs. Our arguments are constructive and give a constant factor approximation algorithm for these metrics. We remark that the considered case is more general than the directed analog of the special case of the symmetric traveling salesman problem for which there were recent improvements on Christofides' algorithm. The main idea of our approach is to first consider an easier problem obtained by significantly relaxing the general connectivity requirements into local connectivity conditions. For this relaxed problem, it is quite easy to give an algorithm with a guarantee of 3 on node-weighted shortest path metrics. More surprisingly, we then show that any algorithm (irrespective of the metric) for the relaxed problem can be turned into an algorithm for the asymmetric traveling salesman problem by only losing a small constant factor in the performance guarantee. This leaves open the intriguing task of designing a 'good' algorithm for the relaxed problem on general metrics. © 2015 IEEE.

Approximation algorithms for regret minimization in vehicle routing problems

Adrian Aloysius Bock

In this thesis, we present new approximation algorithms as well as hardness of approximation results for NP-hard vehicle routing problems related to public transportation. We consider two different problem classes that also occur frequently in areas such as logistics, robotics, or distribution systems. For the first problem class, the goal is to visit as many locations in a network as possible subject to timing or cost constraints. For the second problem class, a given set of locations is to be visited using a minimum-cost set of routes under some constraints. Due to the relevance of both problem classes for public transportation, a secondary objective must be taken into account beyond a low operation cost: namely, it is crucial to design routes that optimize customer satisfaction in order to encourage customers to use the service. Our measure of choice is the regret of a customer, that is the time comparison of the chosen route with the shortest path to a destination. From the first problem class, we investigate variants and extensions of the Orienteering problem that asks to find a short walk maximizing the profit obtained from visiting distinct locations. We give approximation algorithms for variants in which the walk has to respect constraints on the regret of the visited vertices. Additionally, we describe a framework to extend approximation algorithms for Orienteering problems to consider also a second budget constraint, namely node demands, that have to be satisfied in order to collect the profit. We obtain polynomial time approximation schemes for the Capacitated Orienteering problem on trees and Euclidean metrics. Furthermore, we study variants of the School Bus problem (SBP). In SBP, a given set of locations is to be connected to a destination node with both low operation cost and a low maximum regret. We note that the Orienteering problem can be seen as the pricing problem for SBP and it often appears as subroutine in algorithms for SBP. For tree-shaped networks, we describe algorithms with a small constant approximation factor and complement them by showing hardness of approximation results. We give an overview of the known results in arbitrary networks and we prove that a general variant cannot be approximated unless P = NP. Finally, we describe an integer programming approach to solve School Bus problems in practice and present an improved bus schedule for a private school in the lake Geneva region.

EPFL2014

Applications of Strong Convex Relaxations to Allocation Problems

Christos Kalaitzis

Approximation algorithms are a commonly used tool for designing efficient algorithmic solutions for intractable problems, at the expense of the quality of the output solution. A prominent technique for designing such algorithms is the use of Linear Programming (LP) relaxations. An optimal solution to such a relaxation provides a bound on the objective value of the optimal integral solution, to which we compare the integral solution we return. In this context, when studying a specific problem, two natural questions often arise: What is a strong LP relaxation for this problem, and how can we exploit it? Over the course of the past few decades, a significant amount of effort has been expended by the research community in order to answer these questions for a variety of interesting intractable problems. Although there exist multiple problems for which we have designed LP relaxations that achieve best-possible guarantees, there still exist numerous problems for which we either have no strong LP relaxations, or do not know how to use them. The main focus of this thesis is extending our understanding of such strong relaxations. We focus on designing good approximation algorithms for certain allocation problems, by employing a class of strong LP relaxations, called configuration-LPs. For many such allocation problems, the best-known results are derived by using simple and natural LP relaxations, whereas configuration-LPs have been used successfully on several occasions in order to break pre-existing barriers set by weaker relaxations. However, our understanding of configuration-LPs is far from complete for many problems. Therefore, understanding and using these relaxations to the farthest extent possible is a quite intriguing question. Answering this question could result in improved approximation algorithms for a wide variety of allocation problems. The first problem we address in this thesis is the restricted max-min fair allocation problem. Prior to our work, the best known result provided an

\Omega(1)

-approximation that ran in polynomial time. Also, it was known how to estimate the value of an optimal solution to the problem within a factor of

1/(4+c)

, for any

c>0

, by solving the corresponding configuration-LP. Our first contribution in this thesis is the design of a

1/13

-approximation algorithm for the problem, using the configuration-LP. Specifically, although our algorithm is fully combinatorial, it consists of a local-search procedure that is guaranteed to succeed only when the configuration-LP is feasible. In order to establish the correctness and running time of the algorithm, it is crucial to use the configuration-LP in our analysis. The second problem we study is the scheduling of jobs on unrelated machines in order to minimize the sum of weighted completion times. For this problem, the best known approximation algorithm achieves a ratio of

3/2-r

, for some small

r>0

. Our second contribution in this thesis is the improvement of this ratio to

(1+\sqrt{2})/2+c

, for any

c>0

, for the special case of the problem where the jobs have uniform Smith ratios. To achieve this ratio, we design a randomized rounding algorithm that rounds solutions to the corresponding configuration-LP. Through a careful examination of the distribution this randomized algorithm outputs, we identify the one that maximizes the approximation ratio, and we then upper bound the ratio this worst-case distribution exhibits by

(1+\sqrt{2})/2+c

EPFL2017

A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem

Ola Nils Anders Svensson, Jakub Tarnawski

We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of that relaxation. Our techniques build upon the constant-factor approximation algorithm for the special case of node-weighted metrics. Specifically, we give a generic reduction to structured instances that resemble, but are more general than, those arising from node-weighted metrics. For those instances, we then solve Local-Connectivity ATSP, a problem known to be equivalent (in terms of constant-factor approximation) to the asymmetric traveling salesman problem.

ASSOC COMPUTING MACHINERY2018