An improved algorithm for the minmax regret path center problem on trees

DOI10.1016/J.JCSS.2020.05.002zbMath1446.68126OpenAlexW4206630957MaRDI QIDQ2194857

Chih-Yu Li, Jhih-Hong Ye, Biing-Feng Wang

Publication date: 7 September 2020

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2020.05.002

zbMATH Keywords

location theorytreescentersminmax regret optimizationpath centers

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms (68W40) Minimax problems in mathematical programming (90C47) Graph theory (including graph drawing) in computer science (68R10) Discrete location and assignment (90B80)

Related Items (2)

Efficient algorithms for the minmax regret path center problem with length constraint on trees ⋮ Robust reverse 1-center problems on trees with interval costs

Cites Work

• Unnamed Item
• Unnamed Item
• A linear time algorithm for computing minmax regret 1-median on a tree network
• Minmax regret 1-center algorithms for path/tree/unicycle/cactus networks
• Minmax regret location--allocation problem on a network under uncertainty
• A note on the minmax regret centdian location on trees
• Optimal algorithms for the path/tree-shaped facility location problems in trees
• A review of extensive facility location in networks
• Sorting weighted distances with applications to objective function evaluations in single facility location problems.
• Algorithms for the robust 1-center problem on a tree
• The centdian subtree on tree networks
• Extensive facility location problems on networks: an updated review
• An improved algorithm for the minmax regret path centdian problem on trees
• Facility location problems with uncertainty on the plane
• Complexity of robust single facility location problems on networks with uncertain edge lengths.
• On the minmax regret path median problem on trees
• An \(O(pn^ 2)\) algorithm for the \(p\)-median and related problems on tree graphs
• Maintaining information in fully dynamic trees with top trees
• Minimax regret path location on trees
• Fast Algorithms for Finding Nearest Common Ancestors
• Sensitivity analysis of the optimal location of a facility
• The optimal location of a path or tree in a tree network
• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• An Algorithmic Approach to Network Location Problems. II: Thep-Medians
• A linear algorithm for a core of a tree
• Sensitivity Analysis in Minisum Facility Location Problems
• Minimax regret p-center location on a network with demand uncertainty
• Minmax Regret Median Location on a Network Under Uncertainty
• An improved algorithm for the minmax regret median problem on a tree
• Efficient Parallel Algorithms for Optimally Locating a Path and a Tree of a Specified Length in a Weighted Tree Network
• Improved algorithms for the minmax-regret 1-center and 1-median problems
• Finding cores of limited length
• Conditional location of path and tree shaped facilities on trees
• The bi‐criteria doubly weighted center‐median path problem on a tree
• Optimum Locations on a Graph with Probabilistic Demands

This page was built for publication: An improved algorithm for the minmax regret path center problem on trees