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

DOI10.1016/J.TCS.2015.07.009MaRDI QIDQ896121zbMATH OpenOpenAlexFDO

Authors Tsunehiko Kameda, Binay 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)

Recommendations

• Improved Algorithms for Computing Minmax Regret 1-Sink and 2-Sink on Path Network
• An \(O(n^2\log^2 n)\) time algorithm for minmax regret minsum sink on path networks
• Minimax regret sink location problem in dynamic tree networks with uniform capacity
• Minimax Regret Sink Location Problem in Dynamic Tree Networks with Uniform Capacity
• An improved algorithm for the minmax regret path centdian problem on trees
• Minimax regret 1-sink location problems in dynamic path networks
• An improved algorithm for the minmax regret path center problem on trees
• Minimax regret k-sink location problem in dynamic path networks
• Minimax regret 1-sink location problem in dynamic path networks
• Minimax regret vertex 2-sink location problem in dynamic path networks

Cites work

• scientific article; zbMATH DE number 1714716 (Why is no real title available?)
• A linear time algorithm for computing minmax regret 1-median on a tree network
• Algorithms for the robust 1-center problem on a tree
• An \(O(n \log^2 n)\) algorithm for the optimal sink location problem in dynamic tree networks
• 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
• Mathematical Foundations of Computer Science 2003
• Minimax Regret Sink Location Problem in Dynamic Tree Networks with Uniform Capacity
• Minimax regret 1-sink location problem in dynamic cycle networks
• Minimax regret 1-sink location problems in dynamic path networks
• Minimax regret k-sink location problem in dynamic path networks
• Minmax regret 1-facility location on uncertain path networks
• Robust discrete optimization and its applications

Cited in

(16)

• Multiple sink location problem in path networks with a combinational objective
• A TREE PARTITIONING PROBLEM ARISING FROM AN EVACUATION PROBLEM IN TREE DYNAMIC NETWORKS
• Improved Algorithms for Computing Minmax Regret 1-Sink and 2-Sink on Path Network
• Minmax regret for sink location on dynamic flow paths with general capacities
• Minmax regret 1-sink location problems on dynamic flow path networks with parametric weights
• Minmax centered \(k\)-partitioning of trees and applications to sink evacuation with dynamic confluent flows
• Minsum \(k\)-sink problem on path networks
• Capacity provisioning for evacuation on path networks
• Improved algorithms for computing \(k\)-sink on dynamic flow path networks
• Minimax regret 1-sink location problem with accessibility in dynamic general networks
• A linear time algorithm for computing minmax regret 1-median on a tree network
• Minmax regret k-sink location on a dynamic path network with uniform capacities
• Minmax regret 1-center algorithms for path/tree/unicycle/cactus networks
• Minmax regret 1-sink location problems on dynamic flow path networks with parametric weights
• An \(O(n^2\log^2 n)\) time algorithm for minmax regret minsum sink on path networks
• 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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q896121)