Approximation algorithms for cycle and path partitions in complete graphs
Signed and weighted graphs (05C22) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)
Given an edge-weighted (metric/general) complete graph with \(n\) vertices, where \(n\bmod k=0\), the maximum weight (metric/general) \(k\)-cycle/path partition problem (\textit{k}CP/\textit{k}PP) asks to find a set of \(\frac nk\) vertex-disjoint \(k\)-cycles/paths such that the total weight is maximized. For \(k=2\), \textit{k}CP and \textit{k}PP are equivalent to the maximum weight perfect matching problem and polynomially solvable. For \(k\ge 3\), metric \textit{k}CP and \textit{k}PP become NP-hard, and general \textit{k}CP and \textit{k}PP become APX-hard even on \(\{0,1\}\)-weighted graphs.\N\NIn this paper, the authors consider approximation algorithms. For metric \(k\)-cycle partition, they improve the previous approximation ratio from \(\frac35\) to \(\frac7{10}\) for \(k=5\), and for \(k>5\) from \(\frac78(1 -\frac1k)^2\) to \((\frac78-\frac1{8k})(1-\frac1k)\) for constant odd \(k>5\) and to \(\frac78(1-\frac1k+\frac1{k(k-1)})\) for even \(k>5\). For metric \(k\)-path partition they improve the approximation ratio from \(\frac78(1-\frac1k)\) to \(\frac{27k^2-48k+16}{32k2-36k-24}\) for \(k\in\{6,8,10\}\). For the case \(k=4\) they improve the approximation ratio from \(\frac34\) to \(\frac56\) for metric 4-cycle partition, from \(\frac23\) to \(\frac34\) for general 4-cycle partition, and from \(\frac34\) to \(\frac{14}{17}\) for metric 4-path partition.
- 8/7-approximation algorithm for (1,2)-TSP
- A 4/5 -- approximation algorithm for the maximum traveling salesman problem
- A \(\frac78\)-approximation algorithm for metric Max TSP
- A \(d/2\) approximation for maximum weight independent set in \(d\)-claw free graphs
- A deterministic approximation algorithm for metric triangle packing
- A local search algorithm for binary maximum 2-path partitioning
- A randomized approximation algorithm for metric triangle packing
- An approximation algorithm for maximum packing of 3-edge paths
- An approximation algorithm for maximum triangle packing
- An improved approximation for maximum weighted \(k\)-set packing
- An improved randomized approximation algorithm for maximum triangle packing
- Approximation algorithms for maximum dispersion
- Approximation algorithms for the maximum-weight cycle/path packing problems
- Approximation results for the weighted \(P_4\) partition problem
- Deterministic 7/8-approximation for the metric maximum TSP
- Deterministic approximation algorithms for the maximum traveling salesman and maximum triangle packing problems
- Erratum to: ``An improved randomized approximation algorithm for maximum triangle packing
- scientific article; zbMATH DE number 3643026 (Why is no real title available?)
- Improved approximation algorithms for cycle and path packings
- Improved approximation algorithms for metric MaxTSP
- Improved approximation algorithms for weighted 2-path partitions
- On Approximating Restricted Cycle Covers
- On local search for weighted \(k\)-set packing
- On the completeness of a generalized matching problem
- Passing the limits of pure local search for weighted \(k\)-Set packing
- The design of approximation algorithms
- The limits of local search for weighted \(k\)-set packing
This page was built for publication: Approximation algorithms for cycle and path partitions in complete graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7033930)
