Constant Factor Approximation for ATSP with Two Edge Weights

Ola Nils Anders Svensson, Jakub Tarnawski
Springer Int Publishing Ag, 2016
Conference paper

We give a constant factor approximation algorithm for the Asymmetric Traveling Salesman Problem on shortest path metrics of directed graphs with two different edge weights. For the case of unit edge weights, the first constant factor approximation was given recently in [ 17]. This was accomplished by introducing an easier problem called Local-Connectivity ATSP and showing that a good solution to this problem can be used to obtain a constant factor approximation for ATSP. In this paper, we solve Local-Connectivity ATSP for two different edge weights. The solution is based on a flow decomposition theorem for solutions of the Held-Karp relaxation, which may be of independent interest.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts

Related publications

Ola Nils Anders Svensson, Jakub Tarnawski
Springer Int Publishing Ag, 2016
Conference paper

Abstract

Official source

https://infoscience.epfl.ch/record/222004?ln=en

About this result

Related concepts (7)

Related concepts

Related publications (4)

Related publications

Approximation algorithm

In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable

Travelling salesman problem

The travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exa

Problem solving

Problem solving is the process of achieving a goal by overcoming obstacles, a frequent part of most activities. Problems in need of solutions range from simple personal tasks (e.g. how to turn on an a

Constant factor approximation for ATSP with two edge weights

Ola Nils Anders Svensson, Jakub Tarnawski

We give a constant factor approximation algorithm for the Asymmetric Traveling Salesman Problem on shortest path metrics of directed graphs with two different edge weights. For the case of unit edge weights, the first constant factor approximation was given recently by Svensson. This was accomplished by introducing an easier problem called Local-Connectivity ATSP and showing that a good solution to this problem can be used to obtain a constant factor approximation for ATSP. In this paper, we solve Local-Connectivity ATSP for two different edge weights. The solution is based on a flow decomposition theorem for solutions of the Held-Karp relaxation, which may be of independent interest.

SPRINGER HEIDELBERG2018

Maximizing Symmetric Submodular Functions

Moran Feldman

Symmetric submodular functions are an important family of submodular functions capturing many interesting cases, including cut functions of graphs and hypergraphs. Maximization of such functions subject to various constraints receives little attention by current research, unlike similar minimization problems that have been widely studied. In this work, we identify a few submodular maximization problems for which one can get a better approximation for symmetric objectives than the state-of-the-art approximation for general submodular functions. We first consider the problem of maximizing a non-negative symmetric submodular function f : 2(N) -> R+ subject to a down-monotone solvable polytope P subset of 0,1 . For this problem, we describe an algorithm producing a fractional solution of value at least 0.432 . f(OPT), where OPT is the optimal integral solution. Our second result considers the problem max{f(S) : vertical bar S vertical bar = k} for a non-negative symmetric submodular function f : 2(N) -> R+ For this problem, we give an approximation ratio that depends on the value k/vertical bar N vertical bar and is always at least 0.432. Our method can also be applied to non-negative non-symmetric submodular functions, in which case it produces 1/e - o(1) approximation, improving over the best-known result for this problem. For unconstrained maximization of a 11011-negative symmetric submodular function, we describe a deterministic linear-time 1/2-approximation algorithm. Finally, we give a [1 - (1 - 1/k)(k-1)]-approximation algorithm for Submodular Welfare with k players having identical non-negative submodular utility functions and show that this is the best possible approximation ratio for the problem.

Association for Computing Machinery2017

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