An approximation algorithm for network design problems with downwards-monotone demand functions

DOI10.1007/s11590-007-0051-8zbMath1180.90350OpenAlexW1997374695MaRDI QIDQ928296

Sumitra Mukherjee, Michael J. Laszlo

Publication date: 11 June 2008

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11590-007-0051-8

zbMATH Keywords

integer programsspanning forests

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items (2)

Approximation Algorithms for a Network Design Problem ⋮ A 3/2-approximation algorithm for some minimum-cost graph problems

Uses Software

• TSPLIB

Cites Work

• Another greedy heuristic for the constrained forest problem
• A greedy heuristic for a minimum-weight forest problem
• Approximating minimum-cost graph problems with spanning tree edges
• TSPLIB—A Traveling Salesman Problem Library
• A General Approximation Technique for Constrained Forest Problems

This page was built for publication: An approximation algorithm for network design problems with downwards-monotone demand functions