Improved approximation algorithms for the single-sink buy-at-bulk network design problems

DOI10.1016/j.jda.2008.12.003zbMath1184.68358OpenAlexW2022174455MaRDI QIDQ1026237

Balaji Raghavachari, Raja Jothi

Publication date: 24 June 2009

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2008.12.003

zbMATH Keywords

combinatorial optimizationnetwork designapproximation algorithmsrandomized algorithmssingle-sink buy-at-bulk

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items (1)

An improved approximation algorithm for the uniform cost-distance Steiner tree problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximating the Single-Sink Link-Installation Problem in Network Design
• Approximation algorithms for the capacitated minimum spanning tree problem and its variants in network design
• Simpler and better approximation algorithms for network design
• A constant factor approximation for the single sink edge installation problems
• Algorithm Theory - SWAT 2004
• Improved Approximation for Single-Sink Buy-at-Bulk
• A tight bound on approximating arbitrary metrics by tree metrics

This page was built for publication: Improved approximation algorithms for the single-sink buy-at-bulk network design problems