Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
From MaRDI portal
Publication:3546300
DOI10.1145/1082036.1082041zbMath1323.68572OpenAlexW2167197687MaRDI QIDQ3546300
M. I. Sviridenko, Haim Kaplan, Nira Shafrir, Moshe Lewenstein
Publication date: 21 December 2008
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1082036.1082041
Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Related Items (48)
Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems ⋮ The power of greedy algorithms for approximating Max-ATSP, cyclic cover, and superstrings ⋮ LP-based solution methods for the asymmetric TSP ⋮ Two Approximation Algorithms for ATSP with Strengthened Triangle Inequality ⋮ An Improved Integrality Gap for Asymmetric TSP Paths ⋮ The asymmetric bottleneck traveling salesman problem: algorithms, complexity and empirical analysis ⋮ Lower and upper competitive bounds for online directed graph exploration ⋮ Efficient PTAS for the maximum traveling salesman problem in a metric space of fixed doubling dimension ⋮ On the relationship between ATSP and the cycle cover problem ⋮ Motion planning algorithms for the Dubins Travelling Salesperson Problem ⋮ A polynomial algorithm with asymptotic ratio $2/3$ for the asymmetric maximization version of the $m$-PSP ⋮ An experimental study of a hybrid genetic algorithm for the maximum traveling salesman problem ⋮ On global integer extrema of real-valued box-constrained multivariate quadratic functions ⋮ Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies ⋮ A probabilistic PTAS for shortest common superstring ⋮ An algorithm for the polyhedral cycle cover problem with constraints on the number and length of cycles ⋮ Exponential approximation schemata for some network design problems ⋮ A semidefinite optimization approach to the target visitation problem ⋮ Polyhedral techniques in combinatorial optimization: matchings and tours ⋮ Minimum-Weight Cycle Covers and Their Approximability ⋮ 35/44-approximation for asymmetric maximum TSP with triangle inequality ⋮ Multi-criteria TSP: Min and Max combined ⋮ Reoptimization of the shortest common superstring problem ⋮ The minimum spanning tree problem with non-terminal set ⋮ Approximately fair cost allocation in metric traveling salesman games ⋮ Approximating Multi-criteria Max-TSP ⋮ Analysis of set-up time models: a metric perspective ⋮ The on-line asymmetric traveling salesman problem ⋮ Approximating the minimum tour cover of a digraph ⋮ Combinatorial algorithms with performance guarantees for finding several Hamiltonian circuits in a complete directed weighted graph ⋮ Maximum ATSP with weights zero and one via half-edges ⋮ Improved approximation algorithms for metric MaxTSP ⋮ Deterministic Algorithms for Multi-criteria TSP ⋮ Restricted Common Superstring and Restricted Common Supersequence ⋮ APPROXIMATING ASYMMETRIC TSP IN EXPONENTIAL TIME ⋮ Complexity of the directed spanning cactus problem ⋮ Approximating Shortest Superstring Problem Using de Bruijn Graphs ⋮ Unnamed Item ⋮ TSP with bounded metrics ⋮ Deterministic algorithms for multi-criteria max-TSP ⋮ No-Wait Flowshop Scheduling Is as Hard as Asymmetric Traveling Salesman Problem ⋮ Approximation algorithms for maximum latency and partial cycle cover ⋮ Approximation algorithms for multi-criteria traveling salesman problems ⋮ A Polynomial 3/5-Approximate Algorithm for the Asymmetric Maximization Version of the 3-PSP ⋮ Minimum-weight cycle covers and their approximability ⋮ Algorithms as Mechanisms: The Price of Anarchy of Relax and Round ⋮ An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem ⋮ A polynomial algorithm with approximation ratio 2/3 for the Asymmetric Maximum 2-Peripatetic Salesman Problem
This page was built for publication: Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
