An algorithm for the polyhedral cycle cover problem with constraints on the number and length of cycles

DOI10.1134/S0081543819070113MaRDI QIDQ2185648zbMATH OpenOpenAlexFDO

Authors V. V. Shenmaier

Publication date 5 June 2020

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

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

zbMATH Keywords

optimal solutionpolynomial-time algorithmcycle covermaximum traveling salesman problempolyhedral metricmax TSP

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) (n)-dimensional polytopes (52B11) Signed and weighted graphs (05C22) Paths and cycles (05C38)

Recommendations

• A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph
• Constant-factor approximations for cycle cover problems
• On Approximating Restricted Cycle Covers
• scientific article; zbMATH DE number 1947046
• scientific article; zbMATH DE number 1875429

Cites work

• scientific article; zbMATH DE number 4068645 (Why is no real title available?)
• scientific article; zbMATH DE number 3895002 (Why is no real title available?)
• A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem
• An O(n) algorithm for the linear multiple choice knapsack problem and related problems
• Approximating maximum weight cycle covers in directed graphs with weights zero and one
• Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
• Approximation and Online Algorithms
• Asymptotically optimal algorithms for geometric MAX TSP and MAX \(m\)-PSP
• Complexity and approximation of the smallest \(k\)-enclosing ball problem
• TSP with bounded metrics
• The geometric maximum traveling salesman problem

Cited in

(4)

• A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph
• On asymptotically optimal solvability of max \(m\)-\(k\)-cycles cover problem in a normed space
• A branch-and-cut algorithm for the maximum covering cycle problem
• An optimal strategy for the constrained cycle cover problem

This page was built for publication: An algorithm for the polyhedral cycle cover problem with constraints on the number and length of cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2185648)