Search results for "Approximation algorithm"
showing 10 items of 46 documents
Modelling Complex Volume Shape Using Ellipsoid: Application to Pore Space Representation
2017
Natural shapes have complex volume forms that are usually difficult to model using simple analytical equations. The complexity of the representation is due to the heterogeneity of the physical environment and the variety of phenomena involved. In this study we consider the representation of the porous media. Thanks to the technological advances in Computed Topography scanners, the acquisition of images of complex shapes becomes possible. However, and unfortunately, the image data is not directly usable for simulation purposes. In this paper, we investigate the modeling of such shapes using a piece wise approximation of image data by ellipsoids. We propose to use a split-merge strategy and a…
Regularized LMS methods for baseline wandering removal in wearable ECG devices
2016
The acquisition of electrocardiogram (ECG) signals by means of light and reduced size devices can be usefully exploited in several health-care applications, e.g., in remote monitoring of patients. ECG signals, however, are affected by several artifacts due to noise and other disturbances. One of the major ECG degradation is represented by the baseline wandering (BW), a slowly varying change of the signal trend. Several BW removal algorithms have been proposed into the literature, even though their complexity often hinders their implementation into wearable devices characterized by limited computational and memory resources. In this study, we formalize the BW removal problem as a mean-square…
Extreme Learning Machines for Data Classification Tuning by Improved Bat Algorithm
2018
Single hidden layer feed forward neural networks are widely used for various practical problems. However, the training process for determining synaptic weights of such neural networks can be computationally very expensive. In this paper we propose a new learning algorithm for learning the synaptic weights of the single hidden layer feedforward neural networks in order to reduce the learning time. We propose combining the upgraded bat algorithm with the extreme learning machine. The proposed approach reduces the number of evaluations needed to train a neural network and efficiently finds optimal input weights and the hidden biases. The proposed algorithm was tested on standard benchmark clas…
Paths Coloring Algorithms in Mesh Networks
2003
In this paper, we will consider the problem of coloring directed paths on a mesh network. A natural application of this graph problem is WDM-routing in all-optical networks. Our main result is a simple 4-approximation algorithm for coloring line-column paths on a mesh. We also present sharper results when there is a restriction on the path lengths. Moreover, we show that these results can be extended to toroidal meshes and to line-column or column-line paths.
On spline methods of approximation under L-fuzzy information
2011
This work is closely related to our previous papers on algorithms of approximation under L-fuzzy information. In the classical theory of approximation central algorithms were worked out on the basis of usual, that is crisp splines. We describe central methods for solution of linear problems with balanced L-fuzzy information and develop the concept of L-fuzzy splines.
Efficient lower and upper bounds of the diagonal-flip distance between triangulations
2006
There remains today an open problem whether the rotation distance between binary trees or equivalently the diagonal-flip distance between triangulations can be computed in polynomial time. We present an efficient algorithm for computing lower and upper bounds of this distance between a pair of triangulations.
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.
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…
How Low Can Approximate Degree and Quantum Query Complexity Be for Total Boolean Functions?
2012
It has long been known that any Boolean function that depends on n input variables has both degree and exact quantum query complexity of Omega(log n), and that this bound is achieved for some functions. In this paper we study the case of approximate degree and bounded-error quantum query complexity. We show that for these measures the correct lower bound is Omega(log n / loglog n), and we exhibit quantum algorithms for two functions where this bound is achieved.