A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem

DOI10.1007/978-3-642-03685-9_23zbMath1255.68309arXiv0812.5101OpenAlexW2056547933MaRDI QIDQ3638885

Marcin Mucha, Katarzyna E. Paluch, Aleksander Mądry

Publication date: 28 October 2009

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0812.5101

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items

Optimizing Read Reversals for Sequence Compression ⋮ Approximating the maximum multiple RNA interaction problem ⋮ Efficient PTAS for the maximum traveling salesman problem in a metric space of fixed doubling dimension ⋮ A polynomial algorithm with asymptotic ratio $2/3$ for the asymmetric maximization version of the $m$-PSP ⋮ 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 ⋮ Multi-criteria TSP: Min and Max combined ⋮ Deterministic approximation algorithms for the maximum traveling salesman and maximum triangle packing problems ⋮ When polynomial approximation meets exact computation ⋮ A 0.5358-approximation for Bandpass-2 ⋮ Combinatorial algorithms with performance guarantees for finding several Hamiltonian circuits in a complete directed weighted graph ⋮ Deterministic Algorithms for Multi-criteria TSP ⋮ When polynomial approximation meets exact computation ⋮ On the maximum TSP with \(\gamma\)-parameterized triangle inequality ⋮ Deterministic algorithms for multi-criteria max-TSP ⋮ Approximation of the double traveling salesman problem with multiple stacks ⋮ A local search algorithm for binary maximum 2-path partitioning ⋮ A Polynomial 3/5-Approximate Algorithm for the Asymmetric Maximization Version of the 3-PSP ⋮ Informative path planning as a maximum traveling salesman problem with submodular rewards ⋮ Approximation Algorithms for the Maximum Multiple RNA Interaction Problem ⋮ A polynomial algorithm with approximation ratio 2/3 for the Asymmetric Maximum 2-Peripatetic Salesman Problem

This page was built for publication: A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem