Improved algorithms for the minmax-regret 1-center and 1-median problems

DOI10.1145/1367064.1367076zbMath1445.90054OpenAlexW2066124676MaRDI QIDQ4962741

Tzu-Chin Lin, Biing-Feng Wang, Hung-I Yu

Publication date: 5 November 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1367064.1367076

zbMATH Keywords

location theorytreescentersmediansgeneral graphsminmax-regret optimization

Mathematics Subject Classification ID

Discrete location and assignment (90B80) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (13)

Minmax regret for sink location on dynamic flow paths with general capacities ⋮ Minmax regret 1-facility location on uncertain path networks ⋮ 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 ⋮ An improved algorithm for the minmax regret path centdian problem on trees ⋮ An improved algorithm for the minmax regret path center problem on trees ⋮ The \(p\)-center problem under locational uncertainty of demand points ⋮ Fix-and-optimize metaheuristics for minmax regret binary integer programming problems under interval uncertainty ⋮ 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 ⋮ One-dimensional \(k\)-center on uncertain data ⋮ Minmax regret \(k\)-sink location on a dynamic path network with uniform capacities ⋮ On the minmax regret path median problem on trees

This page was built for publication: Improved algorithms for the minmax-regret 1-center and 1-median problems