Approximation algorithms for certain network improvement problems

DOI10.1023/A:1009798010579zbMath0916.90261OpenAlexW1584910000MaRDI QIDQ1282208

Sven O. Krumke, R. Ravi, Hartmut Noltemeier, Madhav V. Marathe, S. S. Ravi

Publication date: 28 March 1999

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1023/a:1009798010579

zbMATH Keywords

minimum spanning treeapproximation algorithmsNP-hardnessedge weighted graphbudget constrained network upgrading problems

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items (18)

Optimizing budget allocation for center and median points ⋮ Budget-constrained minimum cost flows ⋮ Improving multicut in directed trees by upgrading nodes ⋮ Optimal approaches for upgrading selective obnoxious \(p\)-median location problems on tree networks ⋮ Upgrading the 1-center problem with edge length variables on a tree ⋮ Upgrading min-max spanning tree problem under various cost functions ⋮ The \(p\)-median problem with upgrading of transportation costs and minimum travel time allocation ⋮ Upgrading \(p\)-median problem on a path ⋮ Weight reduction problems with certain bottleneck objectives. ⋮ A GRASP metaheuristic to improve accessibility after a disaster ⋮ Reverse 2-median problem on trees ⋮ On the optimum capacity of capacity expansion problems ⋮ Bottleneck Capacity Expansion Problems with General Budget Constraints ⋮ Complexity of reducing the delay between two nodes by node-based and edge-based upgrading strategies ⋮ A game-theoretic approach for downgrading the 1-median in the plane with Manhattan metric ⋮ A class of node based bottleneck improvement problems ⋮ Up- and downgrading the 1-center in a network ⋮ The non-approximability of bicriteria network design problems

This page was built for publication: Approximation algorithms for certain network improvement problems