An approximation algorithm for the \(k\)-prize-collecting multicut on a tree problem

DOI10.1016/j.tcs.2020.07.014zbMath1464.68287OpenAlexW3042489864MaRDI QIDQ2205937

Yanyan Li

Publication date: 21 October 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2020.07.014

zbMATH Keywords

approximation algorithmprimal-dual algorithmmulticutLagrange relaxation\(k\)-prize-collecting multicut

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (3)

An approximation algorithm for the \(B\)-prize-collecting multicut problem in trees ⋮ An approximation algorithm for \(P\)-prize-collecting set cover problem ⋮ A primal-dual approximation algorithm for the \(k\)-prize-collecting minimum power cover problem

Cites Work

• A unified approach to approximating partial covering problems
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Partial multicuts in trees
• A 5-approximation algorithm for the \(k\)-prize-collecting Steiner tree problem
• The Design of Approximation Algorithms
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Unnamed Item

This page was built for publication: An approximation algorithm for the \(k\)-prize-collecting multicut on a tree problem