Search results for "approximation"

On the Low-Dimensional Steiner Minimum Tree Problem in Hamming Metric

2011

It is known that the d-dimensional Steiner Minimum Tree Problem in Hamming metric is NP-complete if d is considered to be a part of the input. On the other hand, it was an open question whether the problem is also NP-complete in fixed dimensions. In this paper we answer this question by showing that the problem is NP-complete for any dimension strictly greater than 2. We also show that the Steiner ratio is 2 - 2/d for d ≥ 2. Using this result, we tailor the analysis of the so-called k-LCA approximation algorithm and show improved approximation guarantees for the special cases d = 3 and d = 4.

On the lattice of J-subnormal subgroups

1992

Approximation Operators of Binomial Type

1999

Our objective is to present a unified theory of the approximation operators of binomial type by exploiting the main technique of the so- called “ umbral calculus” or “finite operator calculus” (see [18], [20]-[22]). Let us consider the basic sequence (bn)n≥0 associated to a certain delta operator Q. By supposing that b n (x) ≥ 0, x ∈ [0, ∞), our purpose is to put in evidence some approximation properties of the linear positive operators (L Q n ) n≥1 which are defined on C[0,1] by \( L_n^Qf = \sum\limits_{k = 0}^n {\beta _n^Q{,_k}f\left( {\frac{k}{n}} \right),\beta _{n{,_k}}^Q\left( x \right): = } \frac{1}{{{b_n}\left( n \right)}}\left( {\begin{array}{*{20}{c}} n \\ k \end{array}} \right){b_…

Fast and Simple Approximation of the Diameter and Radius of a Graph

2006

The increasing amount of data to be processed by computers has led to the need for highly efficient algorithms for various computational problems. Moreover, the algorithms should be as simple as possible to be practically applicable. In this paper we propose a very simple approximation algorithm for finding the diameter and the radius of an undirected graph. The algorithm runs in $O(m\sqrt{n})$ time and gives an additive error of $O(\sqrt{n})$ for a graph with n vertices and m edges. Practical experiments show that the results of our algorithm are close to the optimum and compare favorably to the 2/3-approximation algorithm for the diameter problem by Aingworth et al [1].

Voxel-based General Voronoi Diagram for Complex Data with Application on Motion Planning

2020

One major challenge in Assembly Sequence Planning (ASP) for complex real-world CAD-scenarios is to find appropriate disassembly paths for all assembled parts. Such a path places demands on its length and clearance. In the past, it became apparent that planning the disassembly path based on the (approximate) General Voronoi Diagram (GVD) is a good approach to achieve these requirements. But for complex real-world data, every known solution for computing the GVD is either too slow or very memory consuming, even if only approximating the GVD.We present a new approach for computing the approximate GVD and demonstrate its practicability using a representative vehicle data set. We can calculate a…

Complex singularities in KdV solutions

2016

In the small dispersion regime, the KdV solution exhibits rapid oscillations in its spatio-temporal dependence. We show that these oscillations are caused by the presence of complex singularities that approach the real axis. We give a numerical estimate of the asymptotic dynamics of the poles.

Approximation of functions over manifolds : A Moving Least-Squares approach

2021

We present an algorithm for approximating a function defined over a $d$-dimensional manifold utilizing only noisy function values at locations sampled from the manifold with noise. To produce the approximation we do not require any knowledge regarding the manifold other than its dimension $d$. We use the Manifold Moving Least-Squares approach of (Sober and Levin 2016) to reconstruct the atlas of charts and the approximation is built on-top of those charts. The resulting approximant is shown to be a function defined over a neighborhood of a manifold, approximating the originally sampled manifold. In other words, given a new point, located near the manifold, the approximation can be evaluated…

On a topology optimization problem governed by two-dimensional Helmholtz equation

2015

The paper deals with a class of shape/topology optimization problems governed by the Helmholtz equation in 2D. To guarantee the existence of minimizers, the relaxation is necessary. Two numerical methods for solving such problems are proposed and theoretically justified: a direct discretization of the relaxed formulation and a level set parametrization of shapes by means of radial basis functions. Numerical experiments are given.

A Posteriori Error Bounds for Approximations of the Oseen Problem and Applications to the Uzawa Iteration Algorithm

2014

Abstract. We derive computable bounds of deviations from the exact solution of the stationary Oseen problem. They are applied to approximations generated by the Uzawa iteration method. Also, we derive an advanced form of the estimate, which takes into account approximation errors arising due to discretization of the boundary value problem, generated by the main step of the Uzawa method. Numerical tests confirm our theoretical results and show practical applicability of the estimates.

Splineapproximationen von beliebigem Defekt zur numerischen L�sung gew�hnlicher Differentialgleichungen. Teil III

1980

In the first part [5] a general procedure is presented to obtain polynomial spline approximations of arbitrary defect for the solution of the initial value problem of ordinary differential equations. The essential result is a divergence theorem in dependence of the polynomial degree and the defect of the spline functions. In this second part the convergent procedures are investigated and two convergence theorems are proved. Furthermore the question is treated, whether the convergent procedures are appropriate for the numerical solution of stiff equations. The paper is finished by a convergence theorem for a procedure producing spline approximations in a natural way by the discrete approxima…