A 0.5358-approximation for Bandpass-2

DOI10.1007/s10878-013-9656-2zbMath1331.90069OpenAlexW2010884279MaRDI QIDQ498435

Weitian Tong, Randy Goebel, Tian Liu, Li-Qin Huang, Guo-Hui Lin

Publication date: 28 September 2015

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-013-9656-2

zbMATH Keywords

approximation algorithmacyclic 2-matchingmaximum weight \(b\)-matchingworst case performance ratioBandpass problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items

The band collocation problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the bandpass problem
• The bandpass problem: Combinatorial optimization and library of problems
• Improved deterministic approximation algorithms for max TSP
• A polynomial algorithm for b-matchings: An alternative approach
• Better approximations for max TSP
• On Local Search for Weighted k-Set Packing
• An Improved Approximation Algorithm for the Bandpass Problem
• A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem
• Efficiency of a Good But Not Linear Set Union Algorithm
• A Staged Primal-Dual Algorithm for Perfect b-Matching with Edge Capacities