Minimax regret 1-median problem in dynamic path networks

DOI10.1007/978-3-319-44543-4_10zbMATH Open1397.90236arXiv1509.07600OpenAlexW2949692692MaRDI QIDQ726099FDOQ726099

Authors: Yuya Higashikawa, Siu-Wing Cheng, Tsunehiko Kameda, Naoki Katoh, Shun Saburi 

Publication date: 3 August 2018

Published in: Lecture Notes in Computer Science, Theory of Computing Systems (Search for Journal in Brave)

Abstract: This paper considers the minimax regret 1-median problem in dynamic path networks. In our model, we are given a dynamic path network consisting of an undirected path with positive edge lengths, uniform positive edge capacity, and nonnegative vertex supplies. Here, each vertex supply is unknown but only an interval of supply is known. A particular assignment of supply to each vertex is called a scenario. Given a scenario s and a sink location x in a dynamic path network, let us consider the evacuation time to x of a unit supply given on a vertex by s. The cost of x under s is defined as the sum of evacuation times to x for all supplies given by s, and the median under s is defined as a sink location which minimizes this cost. The regret for x under s is defined as the cost of x under s minus the cost of the median under s. Then, the problem is to find a sink location such that the maximum regret for all possible scenarios is minimized. We propose an O(n^3) time algorithm for the minimax regret 1-median problem in dynamic path networks with uniform capacity, where n is the number of vertices in the network.

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

Recommendations

• Minimax regret 1-median problem in dynamic path networks
• The minmax relative regret median problem on networks
• Minimax regret 1-sink location problems in dynamic path networks
• Minimax regret 1-sink location problem in dynamic path networks
• On the minmax regret path median problem on trees
• Minimax regret k-sink location problem in dynamic path networks
• A minmax regret version of the time-dependent shortest path problem
• Minimax regret single-facility ordered median location problems on networks
• Minmax Regret Median Location on a Network Under Uncertainty
• Minimax regret vertex 2-sink location problem in dynamic path networks

zbMATH Keywords

evacuation planningminimax regretsink locationdynamic flow

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Cooperative games (91A12) Transportation, logistics and supply chain management (90B06) Discrete location and assignment (90B80)

Cites Work

• Minmax-regret robust 1-median location on a tree
• Algorithms for the robust 1-center problem on a tree
• Minmax regret 1-facility location on uncertain path networks
• A Linear Time Algorithm for Computing Minmax Regret 1-Median on a Tree
• Minimax regret 1-sink location problems in dynamic path networks
• Constructing Maximal Dynamic Flows from Static Flows
• Minimax Regret Sink Location Problem in Dynamic Tree Networks with Uniform Capacity
• A note on the minmax regret centdian location on trees
• Minimax regret 1-sink location problem in dynamic path networks
• Multiple Sink Location Problems in Dynamic Path Networks
• An \(O(n \log^2 n)\) algorithm for the optimal sink location problem in dynamic tree networks
• Linear Time Algorithms for Two- and Three-Variable Linear Programs
• A linear time algorithm for computing minmax regret 1-median on a tree network
• An O\((n\log n)\) version of the Averbakh-Berman algorithm for the robust median of a tree
• Improved Algorithms for Computing Minmax Regret 1-Sink and 2-Sink on Path Network
• Minmax regret \(k\)-sink location on a dynamic path network with uniform capacities
• Minimax regret sink location problem in dynamic tree networks with uniform capacity
• Multiple sink location problems in dynamic path networks

Cited In (11)

• Multiple sink location problem in path networks with a combinational objective
• Improved Algorithms for Computing Minmax Regret 1-Sink and 2-Sink on Path Network
• A minmax regret version of the time-dependent shortest path problem
• Minmax regret 1-facility location on uncertain path networks
• Minmax regret 1-sink location problems on dynamic flow path networks with parametric weights
• Title not available (Why is that?)
• Minimax regret 1-sink location problem in dynamic cycle networks
• Minimax regret 1-sink location problems in dynamic path networks
• Minmax regret 1-sink location problems on dynamic flow path networks with parametric weights
• Minmax regret 1-center algorithms for path/tree/unicycle/cactus networks
• Minimax regret 1-median problem in dynamic path networks

This page was built for publication: Minimax regret 1-median problem in dynamic path networks

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