Polynomial-time approximability of the asymmetric problem of covering a graph by a bounded number of cycles

DOI10.1134/s008154382306010xOpenAlexW4391761198MaRDI QIDQ6194910

K. V. Ryzhenko, Mikhail Yu. Khachay, Katherine Neznakhina

Publication date: 16 February 2024

Published in: Proceedings of the Steklov Institute of Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s008154382306010x

zbMATH Keywords

asymmetric traveling salesman problemconstant-factor approximation algorithmcycle cover of graph

Mathematics Subject Classification ID

Computer science (68-XX) Operations research, mathematical programming (90-XX)

Cites Work

• Unnamed Item
• On the asymptotic optimality of a solution of the Euclidean problem of covering a graph by \(m\) nonadjacent cycles of maximum total weight
• Approximability of the minimum-weight \(k\)-size cycle cover problem
• Approximability of the problem about a minimum-weight cycle cover of a graph
• Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems
• Minimum-weight cycle covers and their approximability
• The ellipsoid method and its consequences in combinatorial optimization
• How to tidy up a symmetric set-system by use of uncrossing operations
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Asymptotically optimal approach to the approximate solution of several problems of covering a graph by nonadjacent cycles
• A PTAS for MIN-\(k\)-SCCP in Euclidean space of arbitrary fixed dimension
• Constant-factor approximation algorithms for a series of combinatorial routing problems based on the reduction to the asymmetric traveling salesman problem
• On Approximating Restricted Cycle Covers
• Heuristic analysis, linear programming and branch and bound
• On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
• P-Complete Approximation Problems
• A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem
• An O(log n/log log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem
• An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem
• FIXED RATIO POLYNOMIAL TIME APPROXIMATION ALGORITHM FOR THE PRIZE-COLLECTING ASYMMETRIC TRAVELING SALESMAN PROBLEM