اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدMinimax Regret 1-Median Problem in Dynamic Path Networks
147
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
Evacuation in emergency situations can be modeled by a dynamic flow network. Two criteria have been used before: one is the evacuation completion time and the other is the aggregate evacuation time of individual evacuees. The aim of this paper is to
optimize the aggregate evacuation time in the simplest case, where the network is a path and only one evacuation center (called a sink) is to be introduced. The evacuees are initially located at the vertices, but their precise numbers are unknown, and are given by upper and lower bounds. Under this assumption, we compute the sink location that minimizes the maximum regret. We present an $O(n^2log n)$ time algorithm to solve this problem, improving upon the previously fastest $O(n^3)$ time algorithm, where $n$ is the number of vertices.
We consider the problem of locating a set of $k$ sinks on a path network with general edge capacities that minimizes the sum of the evacuation times of all evacuees. We first present an $O(knlog^4n)$ time algorithm when the edge capacities are non-un
iform, where $n$ is the number of vertices. We then present an $O(knlog^3 n)$ time algorithm when the edge capacities are uniform. We also present an $O(nlog n)$ time algorithm for the special case where $k=1$ and the edge capacities are non-uniform.
We study the Capacitated k-Median problem, for which all the known constant factor approximation algorithms violate either the number of facilities or the capacities. While the standard LP-relaxation can only be used for algorithms violating one of t
he two by a factor of at least two, Shi Li [SODA15, SODA16] gave algorithms violating the number of facilities by a factor of 1+{epsilon} exploring properties of extended relaxations. In this paper we develop a constant factor approximation algorithm for Uniform Capacitated k-Median violating only the capacities by a factor of 1+{epsilon}. The algorithm is based on a configuration LP. Unlike in the algorithms violating the number of facilities, we cannot simply open extra few facilities at selected locations. Instead, our algorithm decides about the facility openings in a carefully designed dependent rounding process.
This paper considers the k-sink location problem in dynamic path networks. In our model, a dynamic path network consists of an undirected path with positive edge lengths, uniform edge capacity, and positive vertex supplies. Here, each vertex supply c
orresponds to a set of evacuees. Then, the problem requires to find the optimal location of $k$ sinks in a given path so that each evacuee is sent to one of k sinks. Let x denote a k-sink location. Under the optimal evacuation for a given x, there exists a (k-1)-dimensional vector d, called (k-1)-divider, such that each component represents the boundary dividing all evacuees between adjacent two sinks into two groups, i.e., all supplies in one group evacuate to the left sink and all supplies in the other group evacuate to the right sink. Therefore, the goal is to find x and d which minimize the maximum cost or the total cost, which are denoted by the minimax problem and the minisum problem, respectively. We study the k-sink location problem in dynamic path networks with continuous model, and prove that the minimax problem can be solved in O(kn) time and the minisum problem can be solved in O(n^2 min{k, 2^{sqrt{log k log log n}}}) time, where n is the number of vertices in the given network. Note that these improve the previous results by [6].
We present a novel approach to finding the $k$-sink on dynamic path networks with general edge capacities. Our first algorithm runs in $O(n log n + k^2 log^4 n)$ time, where $n$ is the number of vertices on the given path, and our second algorithm ru
ns in $O(n log^3 n)$ time. Together, they improve upon the previously most efficient $O(kn log^2 n)$ time algorithm due to Arumugam et al. for all values of $k$. In the case where all the edges have the same capacity, we again present two algorithms that run in $O(n + k^2 log^2n)$ time and $O(n log n)$ time, respectively, and they together improve upon the previously best $O(kn)$ time algorithm due to Higashikawa et al. for all values of $k$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
