Up- and downgrading the 1-center in a network

DOI10.1016/j.ejor.2008.09.013zbMath1163.90710OpenAlexW2080160510MaRDI QIDQ1026756

Elisabeth Gassner

Publication date: 29 June 2009

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2008.09.013

zbMATH Keywords

treecomplexitylocation problemcombinatorial optimizationnetwork improvementdowngradingupgradingnetwork modificationvertex center

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (13)

The inverse 1-center problem on trees with variable edge lengths under Chebyshev norm and Hamming distance ⋮ 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 ⋮ Upgrading edges in the maximal covering location problem ⋮ The \(p\)-median problem with upgrading of transportation costs and minimum travel time allocation ⋮ Upgrading \(p\)-median problem on a path ⋮ Speedup the optimization of maximal closure of a node-weighted directed acyclic graph ⋮ The uniform cost reverse 1-centdian location problem on tree networks with edge length reduction ⋮ Optimal algorithms for inverse obnoxious center location problems under the weighted Chebyshev and Hamming cost norms on networks ⋮ The minmax regret inverse maximum weight problem ⋮ Up- and downgrading the Euclidean 1-median problem and knapsack Voronoi diagrams ⋮ A game-theoretic approach for downgrading the 1-median in the plane with Manhattan metric

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An O(n) algorithm for the linear multiple choice knapsack problem and related problems
• The inverse 1-maxian problem with edge length modification
• Reverse 2-median problem on trees
• Modifying edges of a network to obtain short subgraphs
• Approximation algorithms for certain network improvement problems
• Weight reduction problems with certain bottleneck objectives.
• Inapproximability and a polynomially solvable special case of a network improvement problem.
• A network improvement problem under different norms
• The complexity analysis of the inverse center location problem
• Minimizing the sum of the \(k\) largest functions in linear time.
• Inverse combinatorial optimization: a survey on problems, methods, and results
• Inverse median problems
• Bottleneck Capacity Expansion Problems with General Budget Constraints
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• An Algorithmic Approach to Network Location Problems. II: Thep-Medians
• Maximizing the minimum source-sink path subject to a budget constraint
• Edge Weight Reduction Problems in Directed Acyclic Graphs
• Upgrading trees under diameter and budget constraints
• Network upgrading problems
• Increasing the Weight of Minimum Spanning Trees
• The network inhibition problem
• A linear time algorithm for the reverse 1‐median problem on a cycle

This page was built for publication: Up- and downgrading the 1-center in a network