A note on the subadditive network design problem

DOI10.1016/j.orl.2009.05.006zbMath1173.90334OpenAlexW2117719091MaRDI QIDQ1038103

Mohammad Taghi Hajiaghayi, MohammadHossein Bateni

Publication date: 17 November 2009

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2009.05.006

zbMATH Keywords

approximation algorithmnetwork designhardness of approximationsubadditive cost function

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10)

Cites Work

• On the hardness of approximating label-cover
• The hardness of approximate optima in lattices, codes, and systems of linear equations
• Simpler and better approximation algorithms for network design
• The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
• Stochastic Steiner Tree with Non-uniform Inflation
• On the hardness of approximating minimization problems
• A constant factor approximation for the single sink edge installation problems
• A tight bound on approximating arbitrary metrics by tree metrics
• On the hardness of approximating spanners
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A note on the subadditive network design problem