Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTilt Assembly: Algorithms for Micro-Factories That Build Objects with Uniform External Forces
55
0
0.0
(
0
)
Added by
Arne Schmidt
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We present algorithmic results for the parallel assembly of many micro-scale objects in two and three dimensions from tiny particles, which has been proposed in the context of programmable matter and self-assembly for building high-yield micro-factories. The underlying model has particles moving under the influence of uniform external forces until they hit an obstacle; particles can bond when being forced together with another appropriate particle. Due to the physical and geometric constraints, not all shapes can be built in this manner; this gives rise to the Tilt Assembly Problem (TAP) of deciding constructibility. For simply-connected polyominoes $P$ in 2D consisting of $N$ unit-squares (tiles), we prove that TAP can be decided in $O(Nlog N)$ time. For the optimization variant MaxTAP (in which the objective is to construct a subshape of maximum possible size), we show polyAPX-hardness: unless P=NP, MaxTAP cannot be approximated within a factor of $Omega(N^{frac{1}{3}})$; for tree-shaped structures, we give an $O(N^{frac{1}{2}})$-approximation algorithm. For the efficiency of the assembly process itself, we show that any constructible shape allows pipelined assembly, which produces copies of $P$ in $O(1)$ amortized time, i.e., $N$ copies of $P$ in $O(N)$ time steps. These considerations can be extended to three-dimensional objects: For the class of polycubes $P$ we prove that it is NP-hard to decide whether it is possible to construct a path between two points of $P$; it is also NP-hard to decide constructibility of a polycube $P$. Moreover, it is expAPX-hard to maximize a path from a given start point.
rate research
Read More
Product measures of dimension $n$ are known to be concentrated in Hamming distance: for any set $S$ in the product space of probability $epsilon$, a random point in the space, with probability $1-delta$, has a neighbor in $S$ that is different from the original point in only $O(sqrt{nln(1/(epsilondelta))})$ coordinates. We obtain the tight computational version of this result, showing how given a random point and access to an $S$-membership oracle, we can find such a close point in polynomial time. This resolves an open question of [Mahloujifar and Mahmoody, ALT 2019]. As corollaries, we obtain polynomial-time poisoning and (in certain settings) evasion attacks against learning algorithms when the original vulnerabilities have any cryptographically non-negligible probability. We call our algorithm MUCIO (MUltiplicative Conditional Influence Optimizer) since proceeding through the coordinates, it decides to change each coordinate of the given point based on a multiplicative version of the influence of that coordinate, where influence is computed conditioned on previously updated coordinates. We also define a new notion of algorithmic reduction between computational concentration of measure in different metric probability spaces. As an application, we get computational concentration of measure for high-dimensional Gaussian distributions under the $ell_1$ metric. We prove several extensions to the results above: (1) Our computational concentration result is also true when the Hamming distance is weighted. (2) We obtain an algorithmic version of concentration around mean, more specifically, McDiarmids inequality. (3) Our result generalizes to discrete random processes, and this leads to new tampering algorithms for collective coin tossing protocols. (4) We prove exponential lower bounds on the average running time of non-adaptive query algorithms.
We consider minimum-cardinality Manhattan connected sets with arbitrary demands: Given a collection of points $P$ in the plane, together with a subset of pairs of points in $P$ (which we call demands), find a minimum-cardinality superset of $P$ such that every demand pair is connected by a path whose length is the $ell_1$-distance of the pair. This problem is a variant of three well-studied problems that have arisen in computational geometry, data structures, and network design: (i) It is a node-cost variant of the classical Manhattan network problem, (ii) it is an extension of the binary search tree problem to arbitrary demands, and (iii) it is a special case of the directed Steiner forest problem. Since the problem inherits basic structural properties from the context of binary search trees, an $O(log n)$-approximation is trivial. We show that the problem is NP-hard and present an $O(sqrt{log n})$-approximation algorithm. Moreover, we provide an $O(loglog n)$-approximation algorithm for complete bipartite demands as well as improved results for unit-disk demands and several generalizations. Our results crucially rely on a new lower bound on the optimal cost that could potentially be useful in the context of BSTs.
A classic problem in unsupervised learning and data analysis is to find simpler and easy-to-visualize representations of the data that preserve its essential properties. A widely-used method to preserve the underlying hierarchical structure of the data while reducing its complexity is to find an embedding of the data into a tree or an ultrametric. The most popular algorithms for this task are the classic linkage algorithms (single, average, or complete). However, these methods on a data set of $n$ points in $Omega(log n)$ dimensions exhibit a quite prohibitive running time of $Theta(n^2)$. In this paper, we provide a new algorithm which takes as input a set of points $P$ in $mathbb{R}^d$, and for every $cge 1$, runs in time $n^{1+frac{rho}{c^2}}$ (for some universal constant $rho>1$) to output an ultrametric $Delta$ such that for any two points $u,v$ in $P$, we have $Delta(u,v)$ is within a multiplicative factor of $5c$ to the distance between $u$ and $v$ in the best ultrametric representation of $P$. Here, the best ultrametric is the ultrametric $tildeDelta$ that minimizes the maximum distance distortion with respect to the $ell_2$ distance, namely that minimizes $underset{u,v in P}{max} frac{tildeDelta(u,v)}{|u-v|_2}$. We complement the above result by showing that under popular complexity theoretic assumptions, for every constant $varepsilon>0$, no algorithm with running time $n^{2-varepsilon}$ can distinguish between inputs in $ell_infty$-metric that admit isometric embedding and those that incur a distortion of $frac{3}{2}$. Finally, we present empirical evaluation on classic machine learning datasets and show that the output of our algorithm is comparable to the output of the linkage algorithms while achieving a much faster running time.
We study the space complexity of solving the bias-regularized SVM problem in the streaming model. This is a classic supervised learning problem that has drawn lots of attention, including for developing fast algorithms for solving the problem approximately. One of the most widely used algorithms for approximately optimizing the SVM objective is Stochastic Gradient Descent (SGD), which requires only $O(frac{1}{lambdaepsilon})$ random samples, and which immediately yields a streaming algorithm that uses $O(frac{d}{lambdaepsilon})$ space. For related problems, better streaming algorithms are only known for smooth functions, unlike the SVM objective that we focus on in this work. We initiate an investigation of the space complexity for both finding an approximate optimum of this objective, and for the related ``point estimation problem of sketching the data set to evaluate the function value $F_lambda$ on any query $(theta, b)$. We show that, for both problems, for dimensions $d=1,2$, one can obtain streaming algorithms with space polynomially smaller than $frac{1}{lambdaepsilon}$, which is the complexity of SGD for strongly convex functions like the bias-regularized SVM, and which is known to be tight in general, even for $d=1$. We also prove polynomial lower bounds for both point estimation and optimization. In particular, for point estimation we obtain a tight bound of $Theta(1/sqrt{epsilon})$ for $d=1$ and a nearly tight lower bound of $widetilde{Omega}(d/{epsilon}^2)$ for $d = Omega( log(1/epsilon))$. Finally, for optimization, we prove a $Omega(1/sqrt{epsilon})$ lower bound for $d = Omega( log(1/epsilon))$, and show similar bounds when $d$ is constant.
In this paper the problem of scheduling of jobs on parallel machines under incompatibility relation is considered. In this model a binary relation between jobs is given and no two jobs that are in the relation can be scheduled on the same machine. In particular, we consider job scheduling under incompatibility relation forming bipartite graphs, under makespan optimality criterion, on uniform and unrelated machines. We show that no algorithm can achieve a good approximation ratio for uniform machines, even for a case of unit time jobs, under $P eq NP$. We also provide an approximation algorithm that achieves the best possible approximation ratio, even for the case of jobs of arbitrary lengths $p_j$, under the same assumption. Precisely, we present an $O(n^{1/2-epsilon})$ inapproximability bound, for any $epsilon > 0$; and $sqrt{p_{sum}}$-approximation algorithm, respectively. To enrich the analysis, bipartite graphs generated randomly according to Gilberts model $mathcal{G}_{n,n,p(n)}$ are considered. For a broad class of $p(n)$ functions we show that there exists an algorithm producing a schedule with makespan almost surely at most twice the optimum. Due to our knowledge, this is the first study of randomly generated graphs in the context of scheduling in the considered model. For unrelated machines, an FPTAS for $R2|G = bipartite|C_{max}$ is provided. We also show that there is no algorithm of approximation ratio $O(n^bp_{max}^{1-epsilon})$, even for $Rm|G = bipartite|C_{max}$ for $m ge 3$ and any $epsilon > 0$, $b > 0$, unless $P = NP$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
