Approximation algorithms for feasible cut and multicut problems

DOI10.1007/3-540-60313-1_158zbMath1512.68253MaRDI QIDQ6102317

Joseph Cheriyan, Bo Yu

Publication date: 8 May 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Approximation methods and heuristics in mathematical programming (90C59) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (3)

Parameterized complexity dichotomy for \textsc{Steiner Multicut} ⋮ Rounding to an integral program ⋮ Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations

Cites Work

• Unnamed Item
• The Steiner tree problem
• Geometric algorithms and combinatorial optimization
• A Greedy Heuristic for the Set-Covering Problem
• The cut cone,L1 embeddability, complexity, and multicommodity flows
• The Complexity of Multiterminal Cuts
• Approximation algorithms for combinatorial fractional programming problems
• Nonlinear formulations and improved randomized approximation algorithms for multicut problems
• Approximate max-flow min-(multi)cut theorems and their applications

This page was built for publication: Approximation algorithms for feasible cut and multicut problems