Improved approximation for fractionally subadditive network design

DOI10.1016/j.ipl.2019.105861zbMath1478.68254OpenAlexW2981213705MaRDI QIDQ2011025

Marcin Smulewicz, Marcin Mucha

Publication date: 28 November 2019

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2019.105861

zbMATH Keywords

flownetwork designapproximation algorithms

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) Approximation algorithms (68W25) Signed and weighted graphs (05C22)

Cites Work

• A factor 2 approximation algorithm for the generalized Steiner network problem
• An improved approximation algorithm for requirement cut
• Expander graphs and their applications
• A tight bound on approximating arbitrary metrics by tree metrics
• Unnamed Item

This page was built for publication: Improved approximation for fractionally subadditive network design