Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the Sensitivity of Shape Fitting Problems
182
0
0.0
(
0
)
Added by
Xin Xiao
Publication date
2012
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In this article, we study shape fitting problems, $epsilon$-coresets, and total sensitivity. We focus on the $(j,k)$-projective clustering problems, including $k$-median/$k$-means, $k$-line clustering, $j$-subspace approximation, and the integer $(j,k)$-projective clustering problem. We derive upper bounds of total sensitivities for these problems, and obtain $epsilon$-coresets using these upper bounds. Using a dimension-reduction type argument, we are able to greatly simplify earlier results on total sensitivity for the $k$-median/$k$-means clustering problems, and obtain positively-weighted $epsilon$-coresets for several variants of the $(j,k)$-projective clustering problem. We also extend an earlier result on $epsilon$-coresets for the integer $(j,k)$-projective clustering problem in fixed dimension to the case of high dimension.
rate research
Read More
In the metric multi-cover problem (MMC), we are given two point sets $Y$ (servers) and $X$ (clients) in an arbitrary metric space $(X cup Y, d)$, a positive integer $k$ that represents the coverage demand of each client, and a constant $alpha geq 1$. Each server can have a single ball of arbitrary radius centered on it. Each client $x in X$ needs to be covered by at least $k$ such balls centered on servers. The objective function that we wish to minimize is the sum of the $alpha$-th powers of the radii of the balls. In this article, we consider the MMC problem as well as some non-trivial generalizations, such as (a) the non-uniform MMC, where we allow client-specific demands, and (b) the $t$-MMC, where we require the number of open servers to be at most some given integer $t$. For each of these problems, we present an efficient algorithm that reduces the problem to several instances of the corresponding $1$-covering problem, where the coverage demand of each client is $1$. Our reductions preserve optimality up to a multiplicative constant factor. Applying known constant factor approximation algorithms for $1$-covering, we obtain the first constant approximations for the MMC and these generalizations.
A method evaluating the sensitivity of a given parameter to topological changes is proposed within the method of moments paradigm. The basis functions are used as degrees of freedom which, when compared to the classical pixeling technique, provide important advantages, one of them being impedance matrix inversion free evaluation of the sensitivity. The devised procedure utilizes port modes and their superposition which, together with only a single evaluation of all matrix operators, leads to a computationally effective procedure. The proposed method is approximately one hundred times faster than contemporary approaches, which allows the investigation of the sensitivity and the modification of shapes in real-time. The method is compared with known approaches and its validity and effectiveness is verified using a series of examples. The procedure can be implemented in up-to-date EM simulators in a straightforward manner. It is shown that the iterative repetition of the topology sensitivity evaluation can be used for gradient-based topology synthesis. This technique can also be employed as a local step in global optimizers.
Given a set of $n$ weighted points on the $x$-$y$ plane, we want to find a step function consisting of $k$ horizontal steps such that the maximum vertical weighted distance from any point to a step is minimized. We solve this problem in $O(n)$ time when $k$ is a constant. Our approach relies on the prune-and-search technique, and can be adapted to design similar linear time algorithms to solve the line-constrained k-center problem and the size-$k$ histogram construction problem as well.
We consider Cheeger-like shape optimization problems of the form $$minbig{|Omega|^alpha J(Omega) : Omegasubset Dbig}$$ where $D$ is a given bounded domain and $alpha$ is above the natural scaling. We show the existence of a solution and analyze as $J(Omega)$ the particular cases of the compliance functional $C(Omega)$ and of the first eigenvalue $lambda_1(Omega)$ of the Dirichlet Laplacian. We prove that optimal sets are open and we obtain some necessary conditions of optimality.
Given a tesselation of the plane, defined by a planar straight-line graph $G$, we want to find a minimal set $S$ of points in the plane, such that the Voronoi diagram associated with $S$ fits $G$. This is the Generalized Inverse Voronoi Problem (GIVP), defined in cite{Trin07} and rediscovered recently in cite{Baner12}. Here we give an algorithm that solves this problem with a number of points that is linear in the size of $G$, assuming that the smallest angle in $G$ is constant.
suggested questions
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
