Constant factor approximation for ATSP with two edge weights

Ola Nils Anders Svensson, Jakub Tarnawski
SPRINGER HEIDELBERG, 2018
Article

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.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés

Chargement

Publications associées

Chargement

Ola Nils Anders Svensson, Jakub Tarnawski
SPRINGER HEIDELBERG, 2018
Article

Résumé

Official source

https://infoscience.epfl.ch/record/261129?ln=fr

À propos de ce résultat

Concepts associés (7)

Concepts associés

Chargement

Publications associées (4)

Chargement

Afficher plus

Publications associées

Chargement

Algorithme d'approximation

En informatique théorique, un algorithme d'approximation est une méthode permettant de calculer une solution approchée à un problème algorithmique d'optimisation. Plus précisément, c'est une heuristiq

Problème du voyageur de commerce

vignette|Le problème de voyageur de commerce : calculer un plus court circuit qui passe une et une seule fois par toutes les villes (ici 15 villes). En informatique, le problème du voyageur de commerc

Résolution de problème

vignette|Résolution d'un problème mathématique. La résolution de problème est le processus d'identification puis de mise en œuvre d'une solution à un problème. Méthodologie Dans l'ind

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

Springer Int Publishing Ag2016

Chargement

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

Chargement

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

Chargement

Afficher plus