Partial multicuts in trees

DOI10.1016/j.tcs.2006.09.018zbMath1140.90046OpenAlexW2138694041MaRDI QIDQ861281

Danny Segev, Asaf Levin

Publication date: 9 January 2007

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

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

zbMATH Keywords

Lagrangian relaxationapproximation algorithmsmulticut

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (11)

Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing ⋮ An approximation algorithm for the \(B\)-prize-collecting multicut problem in trees ⋮ An approximation algorithm for \(P\)-prize-collecting set cover problem ⋮ A unified approach to approximating partial covering problems ⋮ An approximation algorithm for the \(k\)-prize-collecting multicut on a tree problem ⋮ Evader interdiction: algorithms, complexity and collateral damage ⋮ The checkpoint problem ⋮ Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth ⋮ Path hitting in acyclic graphs ⋮ Combinatorial approximation algorithms for the submodular multicut problem in trees with submodular penalties ⋮ On the parameterized complexity of separating certain sources from the target

Cites Work

• Unnamed Item
• Improved performance of the greedy algorithm for partial cover
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Strongly polynomial-time approximation for a class of bicriteria problems.
• On the hardness of approximating Multicut and Sparsest-Cut
• Using Homogeneous Weights for Approximating the Partial Cover Problem
• Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem
• A threshold of ln n for approximating set cover
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• A new greedy approach for facility location problems
• On the power of unique 2-prover 1-round games
• Approximating the k-multicut problem
• Combinatorial Optimization with Rational Objective Functions
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• The Complexity of Multiterminal Cuts
• Approximation algorithms for partial covering problems
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• A Unified Approach to Approximating Partial Covering Problems
• Algorithms - ESA 2003

This page was built for publication: Partial multicuts in trees