Improved approximation for fractionally subadditive network design

DOI10.1016/J.IPL.2019.105861MaRDI QIDQ2011025zbMATH OpenOpenAlexFDO

Authors Marcin Mucha, Marcin Smulewicz

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

approximation algorithmsflownetwork design

Mathematics Subject Classification ID

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

Recommendations

• Single-sink fractionally subadditive network design
• A note on the subadditive network design problem
• Approximability of capacitated network design
• Approximability of capacitated network design
• Approximation algorithms for a capacitated network design problem

Cites work

• A factor 2 approximation algorithm for the generalized Steiner network problem
• A tight bound on approximating arbitrary metrics by tree metrics
• An improved approximation algorithm for requirement cut
• Expander graphs and their applications
• Single-sink fractionally subadditive network design

Cited in

(2)

• A note on the subadditive network design problem
• Single-sink fractionally subadditive network design

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2011025)