Minmax regret for sink location on dynamic flow paths with general capacities

DOI10.1016/J.DAM.2022.02.027MaRDI QIDQ2133396zbMATH OpenOpenAlexFDO

Authors Mordecai J. Golin, Sai Sandeep

Publication date 29 April 2022

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

dynamic flow networksminmax regretrobust optimization

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Deterministic network models in operations research (90B10) Discrete location and assignment (90B80) Programming involving graphs or networks (90C35) Minimax problems in mathematical programming (90C47)

Abstract: In dynamic flow networks, every vertex starts with items (flow) that need to be shipped to designated sinks. All edges have two associated quantities: length, the amount of time required for a particle to traverse the edge, and capacity, the number of units of flow that can enter the edge in unit time. The goal is move all flow to the sinks. A variation of the problem, modelling evacuation protocols, is to find the sink location(s) that minimize evacuation time, restricting the flow to be CONFLUENT. Solving this problem is is NP-hard on general graphs, and thus research into optimal algorithms has traditionally been restricted to special graphs such as paths, and trees. A specialized version of robust optimization is minmax REGRET, in which the input flows at the vertices are only partially defined by constraints. The goal is to find a sink location that has the minimum{ regret} over all input flows that satisfy the partially defined constraints. Regret for a fully defined input flow and a sink is defined to be the difference between the evacuation time to that sink and the optimal evacuation time. A large recent literature derives polynomial time algorithms for the minmax regret $k$-sink location problem on paths and trees under the simplifying condition that all edges have the same (uniform) capacity. This paper develops a $O(n^{4}logn)$ time algorithm for the minmax regret $1$-sink problem on paths with general (non-uniform) capacities. To the best of our knowledge, this is the first minmax regret result for dynamic flow problems in any type of graph with general capacities.

Recommendations

• Minmax regret k-sink location on a dynamic path network with uniform capacities
• Minmax regret 1-sink location problems on dynamic flow path networks with parametric weights
• Minimax regret 1-sink location problems in dynamic path networks
• Minimax regret 1-sink location problem in dynamic path networks
• Minimax regret k-sink location problem in dynamic 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
• Minimax regret 1-sink location problem with accessibility in dynamic general networks
• Minimax regret vertex 2-sink location problem in dynamic path networks
• Minimax regret 1-sink location problem in dynamic cycle networks

Cites work

• (Almost) Tight bounds and existence theorems for single-commodity confluent flows
• A Linear Time Algorithm for Computing Minmax Regret 1-Median on a Tree
• A survey of dynamic network flows
• An \(O(n \log^2 n)\) algorithm for the optimal sink location problem in dynamic tree networks
• An improved algorithm for the minmax regret median problem on a tree
• An O\((n\log n)\) version of the Averbakh-Berman algorithm for the robust median of a tree
• Capacitated Confluent Flows: Complexity and Algorithms
• Constructing maximal dynamic flows from static flows
• Improved algorithms for computing \(k\)-sink on dynamic flow path networks
• Improved algorithms for computing minmax regret sinks on dynamic path and tree networks
• Improved algorithms for the minmax-regret 1-center and 1-median problems
• Min-max and min-max regret versions of combinatorial optimization problems: A survey
• Minimax regret 1-sink location problem in dynamic path networks
• Minimax regret 1-sink location problems in dynamic path networks
• Minimax regret p-center location on a network with demand uncertainty
• Minimax regret sink location problem in dynamic tree networks with uniform capacity
• Minimax regret vertex 2-sink location problem in dynamic path networks
• Minmax regret 1-facility location on uncertain path networks
• Minmax regret k-sink location on a dynamic path network with uniform capacities
• Minmax-regret evacuation planning for cycle networks
• Quickest Flows Over Time
• Robust discrete optimization and its applications
• Sink Evacuation on Trees with Dynamic Confluent Flows
• The inapproximability of maximum single-sink unsplittable, priority and confluent flow problems

Cited in

(8)

• Minmax regret k-sink location on a dynamic path network with uniform capacities
• Minmax-regret evacuation planning for cycle networks
• Minimax regret 1-sink location problem in dynamic path networks
• Minimax regret sink location problem in dynamic tree networks with uniform capacity
• 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
• Minmax regret 1-sink location problems on dynamic flow path networks with parametric weights
• Minmax-regret k-sink location on a dynamic tree network with uniform capacities

This page was built for publication: Minmax regret for sink location on dynamic flow paths with general capacities

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