Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPolynomial-time approximability of the k-Sink Location problem
179
0
0.0
(
0
)
Added by
R\\'emy Belmonte
Publication date
2015
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
A dynamic network ${cal N} = (G,c,tau,S)$ where $G=(V,E)$ is a graph, integers $tau(e)$ and $c(e)$ represent, for each edge $ein E$, the time required to traverse edge $e$ and its nonnegative capacity, and the set $Ssubseteq V$ is a set of sources. In the $k$-{sc Sink Location} problem, one is given as input a dynamic network ${cal N}$ where every source $uin S$ is given a nonnegative supply value $sigma(u)$. The task is then to find a set of sinks $X = {x_1,ldots,x_k}$ in $G$ that minimizes the routing time of all supply to $X$. Note that, in the case where $G$ is an undirected graph, the optimal position of the sinks in $X$ needs not be at vertices, and can be located along edges. Hoppe and Tardos showed that, given an instance of $k$-{sc Sink Location} and a set of $k$ vertices $Xsubseteq V$, one can find an optimal routing scheme of all the supply in $G$ to $X$ in polynomial time, in the case where graph $G$ is directed. Note that when $G$ is directed, this suffices to obtain polynomial-time solvability of the $k$-{sc Sink Location} problem, since any optimal position will be located at vertices of $G$. However, the computational complexity of the $k$-{sc Sink Location} problem on general undirected graphs is still open. In this paper, we show that the $k$-{sc Sink Location} problem admits a fully polynomial-time approximation scheme (FPTAS) for every fixed $k$, and that the problem is $W[1]$-hard when parameterized by $k$.
rate research
Read More
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 introduce the combinatorial optimization problem Time Disjoint Walks (TDW), which has applications in collision-free routing of discrete objects (e.g., autonomous vehicles) over a network. This problem takes as input a digraph $G$ with positive integer arc lengths, and $k$ pairs of vertices that each represent a trip demand from a source to a destination. The goal is to find a walk and delay for each demand so that no two trips occupy the same vertex at the same time, and so that a min-max or min-sum objective over the trip durations is realized. We focus here on the min-sum variant of Time Disjoint Walks, although most of our results carry over to the min-max case. We restrict our study to various subclasses of DAGs, and observe that there is a sharp complexity boundary between Time Disjoint Walks on oriented stars and on oriented stars with the central vertex replaced by a path. In particular, we present a poly-time algorithm for min-sum and min-max TDW on the former, but show that min-sum TDW on the latter is NP-hard. Our main hardness result is that for DAGs with max degree $Deltaleq3$, min-sum Time Disjoint Walks is APX-hard. We present a natural approximation algorithm for the same class, and provide a tight analysis. In particular, we prove that it achieves an approximation ratio of $Theta(k/log k)$ on bounded-degree DAGs, and $Theta(k)$ on DAGs and bounded-degree digraphs.
We study the variant of the Euclidean Traveling Salesman problem where instead of a set of points, we are given a set of lines as input, and the goal is to find the shortest tour that visits each line. The best known upper and lower bounds for the problem in $mathbb{R}^d$, with $dge 3$, are $mathrm{NP}$-hardness and an $O(log^3 n)$-approximation algorithm which is based on a reduction to the group Steiner tree problem. We show that TSP with lines in $mathbb{R}^d$ is APX-hard for any $dge 3$. More generally, this implies that TSP with $k$-dimensional flats does not admit a PTAS for any $1le k leq d-2$ unless $mathrm{P}=mathrm{NP}$, which gives a complete classification of the approximability of these problems, as there are known PTASes for $k=0$ (i.e., points) and $k=d-1$ (hyperplanes). We are able to give a stronger inapproximability factor for $d=O(log n)$ by showing that TSP with lines does not admit a $(2-epsilon)$-approximation in $d$ dimensions under the unique games conjecture. On the positive side, we leverage recent results on restricted variants of the group Steiner tree problem in order to give an $O(log^2 n)$-approximation algorithm for the problem, albeit with a running time of $n^{O(loglog n)}$.
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].
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$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
