Approximation Algorithms for Min-Max Cycle Cover Problems

DOI10.1109/TC.2013.2295609MaRDI QIDQ2982336zbMATH OpenFDO

Authors Wenzheng Xu, W. Liang, Xiao-La Lin

Publication date 16 May 2017

Published in IEEE Transactions on Computers (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/TC.2013.2295609

Mathematics Subject Classification ID

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)

Cited in

(33)

• An asymptotically tight online algorithm for \(m\)-steiner traveling salesman problem
• An overview of graph covering and partitioning
• Distance constrained vehicle routing problem to minimize the total cost: algorithms and complexity
• On the Cycle Augmentation Problem: hardness and approximation algorithms
• New LP relaxations for minimum cycle/path/tree cover problems
• A branch-and-cut algorithm for the maximum covering cycle problem
• Covering tours and cycle covers with turn costs: hardness and approximation
• Better approximability results for min-max tree/cycle/path cover problems
• Approximation algorithms for distance constraint sweep coverage with base stations
• Approximation algorithms for the min-max clustered \(k\)-traveling salesmen problems
• An optimal strategy for the constrained cycle cover problem
• Approximating the Minimum Tour Cover with a Compact Linear Program
• Approximation algorithms for multi-robot patrol-scheduling with min-max latency
• Improved approximation algorithms for some min-max and minimum cycle cover problems
• On Approximating Restricted Cycle Covers
• Approximation algorithms for some min-max and minimum stacker crane cover problems
• New approximation algorithms for the rooted budgeted cycle cover problem
• Approximation algorithms for some min-max and minimum stacker crane cover problems
• Approximation algorithms for some minimum postmen cover problems
• New approximation algorithms for the minimum cycle cover problem
• New approximation algorithms for the rooted budgeted cycle cover problem
• Scheduling on a graph with release times
• Drone-based hybrid charging for multiple sensors: a distributionally robust optimization approach
• The heterogeneous rooted tree cover problem
• Approximation algorithms for solving the trip-constrained vehicle routing cover problems
• Approximation algorithms for the capacitated min-max and minimum graph cover problems
• Approximating graphic min-max and minimum cycle/path/tree cover problems
• Approximation algorithms for solving the heterogeneous rooted tree/path cover problems
• A strongly polynomial time approximation algorithm for the min-max clustered cycle cover problem
• Approximation algorithms for the capacitated min-max and minimum graph cover problems
• Approximation algorithm for the min-max partial tree cover problem
• Maximin share fair division of a k-uniform hypergraph
• Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems

This page was built for publication: Approximation Algorithms for Min-Max Cycle Cover Problems

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