Approximation algorithms for maximum latency and partial cycle cover

DOI10.1016/J.DISOPT.2008.12.003MaRDI QIDQ1015324zbMATH OpenOpenAlexFDO

Authors Refael Hassin, Asaf Levin, Shlomi Rubinstein

Publication date 7 May 2009

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disopt.2008.12.003

zbMATH Keywords

approximation algorithmsmaximum latencypartial cycle cover

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Recommendations

• Constant-factor approximations for cycle cover problems
• Algorithms and Data Structures
• Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems
• scientific article; zbMATH DE number 871910
• Approximating maximum weight cycle covers in directed graphs with weights zero and one

Cites work

• scientific article; zbMATH DE number 3685495 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• 35/44-Approximation for Asymmetric Maximum TSP with Triangle Inequality
• A \(\frac78\)-approximation algorithm for metric Max TSP
• An improved randomized approximation algorithm for Max TSP
• Approximating Capacitated Routing and Delivery Problems
• Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
• Better approximations for max TSP
• Budgeted Matching and Budgeted Matroid Intersection Via the Gasoline Puzzle
• Combinatorial Optimization with Rational Objective Functions
• Matching is as easy as matrix inversion
• Robust Matchings

This page was built for publication: Approximation algorithms for maximum latency and partial cycle cover

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