Improved algorithms for computing minmax regret sinks on dynamic path and tree networks

DOI10.1016/j.tcs.2015.07.009zbMath1333.90069OpenAlexW1093958314MaRDI QIDQ896121

Tsunehiko Kameda, Binay K. Bhattacharya

Publication date: 11 December 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.07.009

zbMATH Keywords

facility locationuncertain demandrobust solutionminmax regret optimizationsink location problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Discrete location and assignment (90B80)

Related Items (9)

Multiple sink location problem in path networks with a combinational objective ⋮ Minmax regret for sink location on dynamic flow paths with general capacities ⋮ Minimax regret 1-sink location problem with accessibility in dynamic general networks ⋮ Minmax centered \(k\)-partitioning of trees and applications to sink evacuation with dynamic confluent flows ⋮ Capacity provisioning for evacuation on path networks ⋮ Minmax regret 1-sink location problems on dynamic flow path networks with parametric weights ⋮ Unnamed Item ⋮ Minsum \(k\)-sink problem on path networks ⋮ Minmax regret \(k\)-sink location on a dynamic path network with uniform capacities

Cites Work

• Unnamed Item
• Minmax regret 1-facility location on uncertain path networks
• Minimax regret 1-sink location problem in dynamic cycle networks
• A linear time algorithm for computing minmax regret 1-median on a tree network
• An \(O(n \log^2 n)\) algorithm for the optimal sink location problem in dynamic tree networks
• Robust discrete optimization and its applications
• Algorithms for the robust 1-center problem on a tree
• An \(O(pn^ 2)\) algorithm for the \(p\)-median and related problems on tree graphs
• Improved Algorithms for Computing Minmax Regret 1-Sink and 2-Sink on Path Network
• Minimax Regret 1-Sink Location Problems in Dynamic Path Networks
• Minimax Regret k-sink Location Problem in Dynamic Path Networks
• Mathematical Foundations of Computer Science 2003
• Minimax Regret Sink Location Problem in Dynamic Tree Networks with Uniform Capacity

This page was built for publication: Improved algorithms for computing minmax regret sinks on dynamic path and tree networks