Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userGeneralized Center Problems with Outliers
88
0
0.0
(
0
)
Added by
Deeparnab Chakrabarty
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We study the $mathcal{F}$-center problem with outliers: given a metric space $(X,d)$, a general down-closed family $mathcal{F}$ of subsets of $X$, and a parameter $m$, we need to locate a subset $Sin mathcal{F}$ of centers such that the maximum distance among the closest $m$ points in $X$ to $S$ is minimized. Our main result is a dichotomy theorem. Colloquially, we prove that there is an efficient $3$-approximation for the $mathcal{F}$-center problem with outliers if and only if we can efficiently optimize a poly-bounded linear function over $mathcal{F}$ subject to a partition constraint. One concrete upshot of our result is a polynomial time $3$-approximation for the knapsack center problem with outliers for which no (true) approximation algorithm was known.
rate research
Read More
In recent years, the capacitated center problems have attracted a lot of research interest. Given a set of vertices $V$, we want to find a subset of vertices $S$, called centers, such that the maximum cluster radius is minimized. Moreover, each center in $S$ should satisfy some capacity constraint, which could be an upper or lower bound on the number of vertices it can serve. Capacitated $k$-center problems with one-sided bounds (upper or lower) have been well studied in previous work, and a constant factor approximation was obtained. We are the first to study the capacitated center problem with both capacity lower and upper bounds (with or without outliers). We assume each vertex has a uniform lower bound and a non-uniform upper bound. For the case of opening exactly $k$ centers, we note that a generalization of a recent LP approach can achieve constant factor approximation algorithms for our problems. Our main contribution is a simple combinatorial algorithm for the case where there is no cardinality constraint on the number of open centers. Our combinatorial algorithm is simpler and achieves better constant approximation factor compared to the LP approach.
A bipartite graph $G=(A,B,E)$ is ${cal H}$-convex, for some family of graphs ${cal H}$, if there exists a graph $Hin {cal H}$ with $V(H)=A$ such that the set of neighbours in $A$ of each $bin B$ induces a connected subgraph of $H$. Many $mathsf{NP}$-complete problems, including problems such as Dominating Set, Feedback Vertex Set, Induced Matching and List $k$-Colouring, become polynomial-time solvable for ${mathcal H}$-convex graphs when ${mathcal H}$ is the set of paths. In this case, the class of ${mathcal H}$-convex graphs is known as the class of convex graphs. The underlying reason is that the class of convex graphs has bounded mim-width. We extend the latter result to families of ${mathcal H}$-convex graphs where (i) ${mathcal H}$ is the set of cycles, or (ii) ${mathcal H}$ is the set of trees with bounded maximum degree and a bounded number of vertices of degree at least $3$. As a consequence, we can re-prove and strengthen a large number of results on generalized convex graphs known in the literature. To complement result (ii), we show that the mim-width of ${mathcal H}$-convex graphs is unbounded if ${mathcal H}$ is the set of trees with arbitrarily large maximum degree or an arbitrarily large number of vertices of degree at least $3$. In this way we are able to determine complexity dichotomies for the aforementioned graph problems. Afterwards we perform a more refined width-parameter analysis, which shows even more clearly which width parameters are bounded for classes of ${cal H}$-convex graphs.
Given a weighted graph $G=(V,E)$ with weight functions $c:Eto mathbb{R}_+$ and $pi:Vto mathbb{R}_+$, and a subset $Usubseteq V$, the normalized cut value for $U$ is defined as the sum of the weights of edges exiting $U$ divided by the weight of vertices in $U$. The {it mean isoperimetry problem}, $mathsf{ISO}^1(G,k)$, for a weighted graph $G$ is a generalization of the classical uniform sparsest cut problem in which, given a parameter $k$, the objective is to find $k$ disjoint nonempty subsets of $V$ minimizing the average normalized cut value of the parts. The robust version of the problem seeks an optimizer where the number of vertices that fall out of the subpartition is bounded by some given integer $0 leq rho leq |V|$. Our main result states that $mathsf{ISO}^1(G,k)$, as well as its robust version, $mathsf{CRISO}^1(G,k,rho)$, subjected to the condition that each part of the subpartition induces a connected subgraph, are solvable in time $O(k^2 rho^2 pi(V(T)^3)$ on any weighted tree $T$, in which $pi(V(T))$ is the sum of the vertex-weights. This result implies that $mathsf{ISO}^1(G,k)$ is strongly polynomial-time solvable on weighted trees when the vertex-weights are polynomially bounded and may be compared to the fact that the problem is NP-Hard for weighted trees in general. Also, using this, we show that both mentioned problems, $mathsf{ISO}^1(G,k)$ and $mathsf{CRISO}^1(G,k,rho)$ as well as the ordinary robust mean isoperimetry problem $mathsf{RISO}^1(G,k,rho)$, admit polynomial-time $O(log^{1.5}|V| loglog |V|)$-approximation algorithms for weighted graphs with polynomially bounded weights, using the R{a}cke-Shah tree cut sparsifier.
We study the problem of robustly estimating the mean of a $d$-dimensional distribution given $N$ examples, where most coordinates of every example may be missing and $varepsilon N$ examples may be arbitrarily corrupted. Assuming each coordinate appears in a constant factor more than $varepsilon N$ examples, we show algorithms that estimate the mean of the distribution with information-theoretically optimal dimension-independent error guarantees in nearly-linear time $widetilde O(Nd)$. Our results extend recent work on computationally-efficient robust estimation to a more widely applicable incomplete-data setting.
In this article, we study a generalized version of the maximum independent set and minimum dominating set problems, namely, the maximum $d$-distance independent set problem and the minimum $d$-distance dominating set problem on unit disk graphs for a positive integer $d>0$. We first show that the maximum $d$-distance independent set problem and the minimum $d$-distance dominating set problem belongs to NP-hard class. Next, we propose a simple polynomial-time constant-factor approximation algorithms and PTAS for both the problems.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
