Minmax regret 1-center algorithms for path/tree/unicycle/cactus networks

DOI10.1016/j.dam.2014.10.022zbMath1320.05055OpenAlexW1977160818MaRDI QIDQ496433

Tsunehiko Kameda, Zhao Song, Binay K. Bhattacharya

Publication date: 21 September 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2014.10.022

zbMATH Keywords

facility locationrobust solution1-center problemminmax regret optimizationuncertain weight

Mathematics Subject Classification ID

Paths and cycles (05C38) Signed and weighted graphs (05C22)

Related Items

Efficient algorithms for the minmax regret path center problem with length constraint on trees ⋮ A quadratic time exact algorithm for continuous connected 2-facility location problem in trees ⋮ New approaches to the robust 1-center location problems on tree networks ⋮ Constant work-space algorithms for facility location problems ⋮ An improved algorithm for the minmax regret path center problem on trees ⋮ Minmax regret \(k\)-sink location on a dynamic path network with uniform capacities

Cites Work

• Unnamed Item
• Finding the upper envelope of n line segments in O(n log n) time
• A note on the minmax regret centdian location on trees
• Fractional cascading. II: Applications
• A linear algorithm for the pos/neg-weighted 1-median problem on a cactus
• Location science research: a review
• Algorithms for the robust 1-center problem on a tree
• Complexity of robust single facility location problems on networks with uncertain edge lengths.
• A note on the robust 1-center problem on trees
• Efficient algorithms for center problems in cactus networks
• An \(O(pn^ 2)\) algorithm for the \(p\)-median and related problems on tree graphs
• Minimax regret path location on trees
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• New Results on the Complexity of p-Centre Problems
• Off-Line Maintenance of Planar Configurations
• Minimax regret p-center location on a network with demand uncertainty
• Minmax-regret robust 1-median location on a tree
• Improved algorithms for the minmax-regret 1-center and 1-median problems
• Improved Minmax Regret 1-Center Algorithms for Cactus Networks with c Cycles
• Mathematical Foundations of Computer Science 2003
• Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph