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

DOI10.1007/S11590-007-0051-8MaRDI QIDQ928296zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• scientific article; zbMATH DE number 1342141
• Approximation algorithms for a capacitated network design problem
• scientific article; zbMATH DE number 1003253
• Approximation Algorithms for a Network Design Problem
• Algorithms for a network design problem with crossing supermodular demands

Cites work

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

Cited in

(2)

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

Describes a project that uses

Uses Software

• TSPLIB

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

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