Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn Perturbation Resilience of Non-Uniform $k$-Center
94
0
0.0
(
0
)
Added by
Sayan Bandyapadhyay
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Authors
Sayan Bandyapadhyay
Ask ChatGPT about the research
No Arabic abstract
The Non-Uniform $k$-center (NUkC) problem has recently been formulated by Chakrabarty, Goyal and Krishnaswamy [ICALP, 2016] as a generalization of the classical $k$-center clustering problem. In NUkC, given a set of $n$ points $P$ in a metric space and non-negative numbers $r_1, r_2, ldots , r_k$, the goal is to find the minimum dilation $alpha$ and to choose $k$ balls centered at the points of $P$ with radius $alphacdot r_i$ for $1le ile k$, such that all points of $P$ are contained in the union of the chosen balls. They showed that the problem is NP-hard to approximate within any factor even in tree metrics. On the other hand, they designed a bi-criteria constant approximation algorithm that uses a constant times $k$ balls. Surprisingly, no true approximation is known even in the special case when the $r_i$s belong to a fixed set of size 3. In this paper, we study the NUkC problem under perturbation resilience, which was introduced by Bilu and Linial [Combinatorics, Probability and Computing, 2012]. We show that the problem under 2-perturbation resilience is polynomial time solvable when the $r_i$s belong to a constant sized set. However, we show that perturbation resilience does not help in the general case. In particular, our findings imply that even with perturbation resilience one cannot hope to find any good approximation for the problem.
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 consider the colorful $k$-center problem, which is a generalization of the well-known $k$-center problem. Here, we are given red and blue points in a metric space, and a coverage requirement for each color. The goal is to find the smallest radius $rho$, such that with $k$ balls of radius $rho$, the desired number of points of each color can be covered. We obtain a constant approximation for this problem in the Euclidean plane. We obtain this result by combining a pseudo-approximation algorithm that works in any metric space, and an approximation algorithm that works for a special class of instances in the plane. The latter algorithm uses a novel connection to a certain matching problem in graphs.
For any $epsilon>0$, Laue and Matijevi{c} [CCCG07, IPL08] give a PTAS for finding a $(1+epsilon)$-approximate solution to the $k$-hop MST problem in the Euclidean plane that runs in time $(n/epsilon)^{O(k/epsilon)}$. In this paper, we present an algorithm that runs in time $(n/epsilon)^{O(log k cdot(1/epsilon)^2cdotlog^2(1/epsilon))}$. This gives an improvement on the dependency on $k$ on the exponent, while having a worse dependency on $epsilon$. As in Laue and Matijevi{c}, we follow the framework introduced by Arora for Euclidean TSP. Our key ingredients include exponential distance scaling and compression of dynamic programming state tables.
We consider the problem of center-based clustering in low-dimensional Euclidean spaces under the perturbation stability assumption. An instance is $alpha$-stable if the underlying optimal clustering continues to remain optimal even when all pairwise distances are arbitrarily perturbed by a factor of at most $alpha$. Our main contribution is in presenting efficient exact algorithms for $alpha$-stable clustering instances whose running times depend near-linearly on the size of the data set when $alpha ge 2 + sqrt{3}$. For $k$-center and $k$-means problems, our algorithms also achieve polynomial dependence on the number of clusters, $k$, when $alpha geq 2 + sqrt{3} + epsilon$ for any constant $epsilon > 0$ in any fixed dimension. For $k$-median, our algorithms have polynomial dependence on $k$ for $alpha > 5$ in any fixed dimension; and for $alpha geq 2 + sqrt{3}$ in two dimensions. Our algorithms are simple, and only require applying techniques such as local search or dynamic programming to a suitably modified metric space, combined with careful choice of data structures.
In the scheduling with non-uniform communication delay problem, the input is a set of jobs with precedence constraints. Associated with every precedence constraint between a pair of jobs is a communication delay, the time duration the scheduler has to wait between the two jobs if they are scheduled on different machines. The objective is to assign the jobs to machines to minimize the makespan of the schedule. Despite being a fundamental problem in theory and a consequential problem in practice, the approximability of scheduling problems with communication delays is not very well understood. One of the top ten open problems in scheduling theory, in the influential list by Schuurman and Woeginger and its latest update by Bansal, asks if the problem admits a constant factor approximation algorithm. In this paper, we answer the question in negative by proving that there is a logarithmic hardness for the problem under the standard complexity theory assumption that NP-complete problems do not admit quasi-polynomial time algorithms. Our hardness result is obtained using a surprisingly simple reduction from a problem that we call Unique Machine Precedence constraints Scheduling (UMPS). We believe that this problem is of central importance in understanding the hardness of many scheduling problems and conjecture that it is very hard to approximate. Among other things, our conjecture implies a logarithmic hardness of related machine scheduling with precedences, a long-standing open problem in scheduling theory and approximation algorithms.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
