Approximation algorithms for certain network improvement problems
From MaRDI portal
Publication:1282208
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
minimum spanning treeapproximation algorithmsNP-hardnessedge weighted graphbudget constrained network upgrading problems
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
