Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe $p$-Center Problem in Tree Networks Revisited
48
0
0.0
(
0
)
Added by
Tsunehiko Kameda
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We present two improved algorithms for weighted discrete $p$-center problem for tree networks with $n$ vertices. One of our proposed algorithms runs in $O(n log n + p log^2 n log(n/p))$ time. For all values of $p$, our algorithm thus runs as fast as or faster than the most efficient $O(nlog^2 n)$ time algorithm obtained by applying Coles speed-up technique [cole1987] to the algorithm due to Megiddo and Tamir [megiddo1983], which has remained unchallenged for nearly 30 years. Our other algorithm, which is more practical, runs in $O(n log n + p^2 log^2(n/p))$ time, and when $p=O(sqrt{n})$ it is faster than Megiddo and Tamirs $O(n log^2n loglog n)$ time algorithm [megiddo1983].
rate research
Read More
In this paper, we introduce and study the Non-Uniform k-Center problem (NUkC). Given a finite metric space $(X,d)$ and a collection of balls of radii ${r_1geq cdots ge r_k}$, the NUkC problem is to find a placement of their centers on the metric space and find the minimum dilation $alpha$, such that the union of balls of radius $alphacdot r_i$ around the $i$th center covers all the points in $X$. This problem naturally arises as a min-max vehicle routing problem with fleets of different speeds. The NUkC problem generalizes the classic $k$-center problem when all the $k$ radii are the same (which can be assumed to be $1$ after scaling). It also generalizes the $k$-center with outliers (kCwO) problem when there are $k$ balls of radius $1$ and $ell$ balls of radius $0$. There are $2$-approximation and $3$-approximation algorithms known for these problems respectively; the former is best possible unless P=NP and the latter remains unimproved for 15 years. We first observe that no $O(1)$-approximation is to the optimal dilation is possible unless P=NP, implying that the NUkC problem is more non-trivial than the above two problems. Our main algorithmic result is an $(O(1),O(1))$-bi-criteria approximation result: we give an $O(1)$-approximation to the optimal dilation, however, we may open $Theta(1)$ centers of each radii. Our techniques also allow us to prove a simple (uni-criteria), optimal $2$-approximation to the kCwO problem improving upon the long-standing $3$-factor. Our main technical contribution is a connection between the NUkC problem and the so-called firefighter problems on trees which have been studied recently in the TCS community.
In this paper we initiate the study of the heterogeneous capacitated $k$-center problem: given a metric space $X = (F cup C, d)$, and a collection of capacities. The goal is to open each capacity at a unique facility location in $F$, and also to assign clients to facilities so that the number of clients assigned to any facility is at most the capacity installed; the objective is then to minimize the maximum distance between a client and its assigned facility. If all the capacities $c_i$s are identical, the problem becomes the well-studied uniform capacitated $k$-center problem for which constant-factor approximations are known. The additional choice of determining which capacity should be installed in which location makes our problem considerably different from this problem, as well the non-uniform generalizations studied thus far in literature. In fact, one of our contributions is in relating the heterogeneous problem to special-cases of the classical Santa Claus problem. Using this connection, and by designing new algorithms for these special cases, we get the following results: (a)A quasi-polynomial time $O(log n/epsilon)$-approximation where every capacity is violated by $1+varepsilon$, (b) A polynomial time $O(1)$-approximation where every capacity is violated by an $O(log n)$ factor. We get improved results for the {em soft-capacities} version where we can place multiple facilities in the same location.
The three-in-a-tree problem asks for an induced tree of the input graph containing three mandatory vertices. In 2006, Chudnovsky and Seymour [Combinatorica, 2010] presented the first polynomial time algorithm for this problem, which has become a critical subroutine in many algorithms for detecting induced subgraphs, such as beetles, pyramids, thetas, and even and odd-holes. In 2007, Derhy and Picouleau [Discrete Applied Mathematics, 2009] considered the natural generalization to $k$ mandatory vertices, proving that, when $k$ is part of the input, the problem is $mathsf{NP}$-complete, and ask what is the complexity of four-in-a-tree. Motivated by this question and the relevance of the original problem, we study the parameterized complexity of $k$-in-a-tree. We begin by showing that the problem is $mathsf{W[1]}$-hard when jointly parameterized by the size of the solution and minimum clique cover and, under the Exponential Time Hypothesis, does not admit an $n^{o(k)}$ time algorithm. Afterwards, we use Courcelles Theorem to prove fixed-parameter tractability under cliquewidth, which prompts our investigation into which parameterizations admit single exponential algorithms; we show that such algorithms exist for the unrelated parameterizations treewidth, distance to cluster, and distance to co-cluster. In terms of kernelization, we present a linear kernel under feedback edge set, and show that no polynomial kernel exists under vertex cover nor distance to clique unless $mathsf{NP} subseteq mathsf{coNP}/mathsf{poly}$. Along with other remarks and previous work, our tractability and kernelization results cover many of the most commonly employed parameters in the graph parameter hierarchy.
We study the multi-level Steiner tree problem: a generalization of the Steiner tree problem in graphs where terminals $T$ require varying priority, level, or quality of service. In this problem, we seek to find a minimum cost tree containing edges of varying rates such that any two terminals $u$, $v$ with priorities $P(u)$, $P(v)$ are connected using edges of rate $min{P(u),P(v)}$ or better. The case where edge costs are proportional to their rate is approximable to within a constant factor of the optimal solution. For the more general case of non-proportional costs, this problem is hard to approximate with ratio $c log log n$, where $n$ is the number of vertices in the graph. A simple greedy algorithm by Charikar et al., however, provides a $min{2(ln |T|+1), ell rho}$-approximation in this setting, where $rho$ is an approximation ratio for a heuristic solver for the Steiner tree problem and $ell$ is the number of priorities or levels (Byrka et al. give a Steiner tree algorithm with $rhoapprox 1.39$, for example). In this paper, we describe a natural generalization to the multi-level case of the classical (single-level) Steiner tree approximation algorithm based on Kruskals minimum spanning tree algorithm. We prove that this algorithm achieves an approximation ratio at least as good as Charikar et al., and experimentally performs better with respect to the optimum solution. We develop an integer linear programming formulation to compute an exact solution for the multi-level Steiner tree problem with non-proportional edge costs and use it to evaluate the performance of our algorithm on both random graphs and multi-level instances derived from SteinLib.
Given a graph $G = (V,E)$ and a subset $T subseteq V$ of terminals, a emph{Steiner tree} of $G$ is a tree that spans $T$. In the vertex-weighted Steiner tree (VST) problem, each vertex is assigned a non-negative weight, and the goal is to compute a minimum weight Steiner tree of $G$. We study a natural generalization of the VST problem motivated by multi-level graph construction, the emph{vertex-weighted grade-of-service Steiner tree problem} (V-GSST), which can be stated as follows: given a graph $G$ and terminals $T$, where each terminal $v in T$ requires a facility of a minimum grade of service $R(v)in {1,2,ldotsell}$, compute a Steiner tree $G$ by installing facilities on a subset of vertices, such that any two vertices requiring a certain grade of service are connected by a path in $G$ with the minimum grade of service or better. Facilities of higher grade are more costly than facilities of lower grade. Multi-level variants such as this one can be useful in network design problems where vertices may require facilities of varying priority. While similar problems have been studied in the edge-weighted case, they have not been studied as well in the more general vertex-weighted case. We first describe a simple heuristic for the V-GSST problem whose approximation ratio depends on $ell$, the number of grades of service. We then generalize the greedy algorithm of [Klein & Ravi, 1995] to show that the V-GSST problem admits a $(2 ln |T|)$-approximation, where $T$ is the set of terminals requiring some facility. This result is surprising, as it shows that the (seemingly harder) multi-grade problem can be approximated as well as the VST problem, and that the approximation ratio does not depend on the number of grades of service.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
