Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userImproved Algorithms for Multiple Sink Location Problems in Dynamic Path Networks
185
0
0.0
(
0
)
Added by
Yuya Higashikawa
Publication date
2014
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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 corresponds 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].
rate research
Read More
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 runs 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$.
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-uniform, 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 give new approximation algorithms for the submodular joint replenishment problem and the inventory routing problem, using an iterative rounding approach. In both problems, we are given a set of $N$ items and a discrete time horizon of $T$ days in which given demands for the items must be satisfied. Ordering a set of items incurs a cost according to a set function, with properties depending on the problem under consideration. Demand for an item at time $t$ can be satisfied by an order on any day prior to $t$, but a holding cost is charged for storing the items during the intermediate period; the goal is to minimize the sum of the ordering and holding cost. Our approximation factor for both problems is $O(log log min(N,T))$; this improves exponentially on the previous best results.
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.
Given a directed graph $G = (V, E)$, the $k$-path partition problem is to find a minimum collection of vertex-disjoint directed paths each of order at most $k$ to cover all the vertices of $V$. The problem has various applications in facility location, network monitoring, transportation and others. Its special case on undirected graphs has received much attention recently, but the general directed version is seemingly untouched in the literature. We present the first $k/2$-approximation algorithm, for any $k ge 3$, based on a novel concept of augmenting path to minimize the number of singletons in the partition. When $k ge 7$, we present an improved $(k+2)/3$-approximation algorithm based on the maximum path-cycle cover followed by a careful $2$-cycle elimination process. When $k = 3$, we define the second novel kind of augmenting paths and propose an improved $13/9$-approximation algorithm.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
