Minsum \(k\)-sink problem on path networks

DOI10.1016/j.tcs.2019.05.047zbMath1442.90024arXiv1810.10631OpenAlexW2962805720WikidataQ127467864 ScholiaQ127467864MaRDI QIDQ2285143

Yuya Higashikawa, Tsunehiko Kameda, Binay K. Bhattacharya, Robert Benkoczi, Naoki Katoh

Publication date: 16 January 2020

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

Full work available at URL: https://arxiv.org/abs/1810.10631

zbMATH Keywords

facility locationevacuation problemsink location problemdynamic flow in networkminsum criterion

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10) Discrete location and assignment (90B80)

Related Items

Multiple sink location problem in path networks with a combinational objective ⋮ Capacity provisioning for evacuation on path networks ⋮ Minmax regret 1-sink location problems on dynamic flow path networks with parametric weights ⋮ Almost linear time algorithms for minsum \(k\)-sink problems on dynamic flow path networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An \(O(n \log^2 n)\) algorithm for the optimal sink location problem in dynamic tree networks
• Improved algorithms for computing minmax regret sinks on dynamic path and tree networks
• Multiple sink location problems in dynamic path networks
• Transient flows in networks
• Improved complexity bounds for location problems on the real line
• Robust discrete optimization and its applications
• Minsum \(k\)-sink problem on dynamic flow path networks
• Minimax regret 1-sink location problem in dynamic path networks
• Improved algorithms for computing \(k\)-sink on dynamic flow path networks
• Minimax Regret Sink Location Problem in Dynamic Tree Networks with Uniform Capacity
• Combinatorial Optimization with Rational Objective Functions
• An Algorithmic Approach to Network Location Problems. II: Thep-Medians
• Maximal, Lexicographic, and Dynamic Network Flows
• Sink Evacuation on Trees with Dynamic Confluent Flows
• Finding kth paths and p-centers by generating and searching good data structures
• Minimax Regret 1-Sink Location Problems in Dynamic Path Networks
• Constructing Maximal Dynamic Flows from Static Flows
• An Algorithm for Universal Maximal Dynamic Flows in a Network
• Minmax centered \(k\)-partitioning of trees and applications to sink evacuation with dynamic confluent flows