22 results
Search Results
2. Efficient approximation algorithms for clustering point-sets
- Author
-
Xu, Guang and Xu, Jinhui
- Subjects
- *
POINT set theory , *APPROXIMATION theory , *ALGORITHMS , *ALGEBRAIC spaces , *CLUSTER analysis (Statistics) , *MATHEMATICAL analysis - Abstract
Abstract: In this paper, we consider the problem of clustering a set of n finite point-sets in d-dimensional Euclidean space. Different from the traditional clustering problem (called points clustering problem where the to-be-clustered objects are points), the point-sets clustering problem requires that all points in a single point-set be clustered into the same cluster. This requirement disturbs the metric property of the underlying distance function among point-sets and complicates the clustering problem dramatically. In this paper, we use a number of interesting observations and techniques to overcome this difficulty. For the k-center clustering problem on point-sets, we give an -time 3-approximation algorithm and an -time -approximation algorithm, where m is the total number of input points and k is the number of clusters. When k is a small constant, the performance ratio of our algorithm reduces to for any . For the k-median problem on point-sets, we present a polynomial time -approximation algorithm. Our approaches are rather general and can be easily implemented for practical purpose. [Copyright &y& Elsevier]
- Published
- 2010
- Full Text
- View/download PDF
3. Reductions between scheduling problems with non-renewable resources and knapsack problems.
- Author
-
Györgyi, Péter and Kis, Tamás
- Subjects
- *
COMPUTER scheduling , *KNAPSACK problems , *APPROXIMATION theory , *ALGORITHMS , *MATHEMATICAL analysis , *COMPUTER systems - Abstract
In this paper we establish approximation preserving reductions between scheduling problems in which jobs either consume some raw materials, or produce some intermediate products, and variants of the knapsack problem. Through the reductions, we get new approximation algorithms, as well as inapproximability results for the scheduling problems. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
4. Arbitrary-level hanging nodes for adaptive -FEM approximations in 3D.
- Author
-
Kus, Pavel, Solin, Pavel, and Andrs, David
- Subjects
- *
ARBITRARY constants , *FINITE element method , *APPROXIMATION theory , *ALGORITHMS , *MATHEMATICAL analysis - Abstract
Abstract: In this paper we discuss constrained approximation with arbitrary-level hanging nodes in adaptive higher-order finite element methods ( -FEM) for three-dimensional problems. This technique enables using highly irregular meshes, and it greatly simplifies the design of adaptive algorithms as it prevents refinements from propagating recursively through the finite element mesh. The technique makes it possible to design efficient adaptive algorithms for purely hexahedral meshes. We present a detailed mathematical description of the method and illustrate it with numerical examples. [Copyright &y& Elsevier]
- Published
- 2014
- Full Text
- View/download PDF
5. The inverse eigenproblem with a submatrix constraint and the associated approximation problem for -symmetric matrices.
- Author
-
Yin, Feng, Guo, Ke, Huang, Guangxin, and Huang, Bormin
- Subjects
- *
APPROXIMATION theory , *SYMMETRIC matrices , *PROBLEM solving , *ALGORITHMS , *MATHEMATICAL analysis - Abstract
Abstract: Let and be nontrivial involutions, i.e., and . A matrix is called -symmetric if . This paper presents a -symmetric matrix solution to the inverse eigenproblem with a leading principal submatrix constraint. The solvability condition of the constrained inverse eigenproblem is also derived. The existence, the uniqueness and the expression of the -symmetric matrix solution to the best approximation problem of the constrained inverse eigenproblem are achieved, respectively. An algorithm is presented to compute the -symmetric matrix solution to the best approximation problem. Two numerical examples are given to illustrate the effectiveness of our results. [Copyright &y& Elsevier]
- Published
- 2014
- Full Text
- View/download PDF
6. Approximating minimum bending energy path in a simple corridor.
- Author
-
Xu, Lei and Xu, Jinhui
- Subjects
- *
APPROXIMATION theory , *ALGORITHMS , *CURVES , *GEOMETRY , *MATHEMATICAL analysis - Abstract
Abstract: In this paper, we consider the problem of computing a minimum bending energy path (or MinBEP) in a simple corridor. Given a simple 2D corridor C bounded by straight line segments and arcs of radius 2r, the MinBEP problem is to compute a path P inside C and crossing two pre-specified points s and t located at each end of C so that the bending energy of P is minimized. For this problem, we first show how to lower bound the bending energy of an optimal curve with bounded curvature, and then use this lower bound to design a -approximation algorithm for this restricted version of the MinBEP problem. Our algorithm is based on a number of interesting geometric observations and approximation techniques on smooth curves, and can be easily implemented for practical purpose. It is the first algorithm with a guaranteed performance ratio for the MinBEP problem. [Copyright &y& Elsevier]
- Published
- 2014
- Full Text
- View/download PDF
7. Spectral binomial tree: New algorithms for pricing barrier options.
- Author
-
Muroi, Yoshifumi and Yamada, Takashi
- Subjects
- *
ALGORITHMS , *OPTIONS (Finance) , *PRICING , *MATHEMATICAL expansion , *APPROXIMATION theory , *MATHEMATICAL analysis - Abstract
Abstract: This paper introduces new and significantly fast algorithms to evaluate the price of double barrier options using binomial trees. To compute the price of double barrier options accurately, trees with large numbers of steps must be used, which is time consuming. In order to overcome this weakness, we develop new computational algorithms based on the spectral expansion method. The original idea of this method is coming from the eigenexpansion approach in PDEs. We show that this method enables us to compute double barrier options within 0.07 s, even if we use binomial trees with one billion steps. Moreover, this algorithm is easy to implement. In addition, the prices obtained by the proposed approach are always the same as those obtained by conventional binomial trees and show a good approximation to those by earlier studies. [Copyright &y& Elsevier]
- Published
- 2013
- Full Text
- View/download PDF
8. A two-grid algorithm for expanded mixed finite element approximations of semi-linear elliptic equations.
- Author
-
Liu, Wei, Rui, Hongxing, and Hu, Fengzhu
- Subjects
- *
ALGORITHMS , *FINITE element method , *APPROXIMATION theory , *LINEAR equations , *NONLINEAR analysis , *MATHEMATICAL analysis - Abstract
Abstract: A semi-linear elliptic problem with variable coefficient is approximated by expanded mixed formulation based on the RTN and BDM mixed finite elements. In order to solve the nonlinear approximation system of equations efficiently, a two-grid algorithm is considered and discussed in this paper. The work includes a small nonlinear system on a coarse grid space with mesh size and a linear system on a fine grid space with mesh size . It follows from error estimates that asymptotically optimal accuracy can be obtained as long as the mesh sizes satisfy in the norm. Some numerical examples are presented to illustrate the theoretical results. [Copyright &y& Elsevier]
- Published
- 2013
- Full Text
- View/download PDF
9. An algorithm for computing a Padé approximant with minimal degree denominator
- Author
-
Ibryaeva, O.L. and Adukov, V.M.
- Subjects
- *
ALGORITHMS , *APPROXIMATION theory , *KERNEL functions , *TOEPLITZ matrices , *TOPOLOGICAL degree , *MATHEMATICAL analysis - Abstract
Abstract: In this paper, a new definition of a reduced Padé approximant and an algorithm for its computation are proposed. Our approach is based on the investigation of the kernel structure of the Toeplitz matrix. It is shown that the reduced Padé approximant always has nice properties which the classical Padé approximant possesses only in the normal case. The new algorithm allows us to avoid the appearance of Froissart doublets induced by computer roundoff in the non-normal Padé table. [Copyright &y& Elsevier]
- Published
- 2013
- Full Text
- View/download PDF
10. Synthetic boundary conditions for image deblurring
- Author
-
Fan, Ying Wai (Daniel) and Nagy, James G.
- Subjects
- *
IMAGE reconstruction , *APPROXIMATION theory , *ALGORITHMS , *BOUNDARY value problems , *NUMERICAL analysis , *MATHEMATICAL analysis - Abstract
Abstract: In this paper we introduce a new boundary condition that can be used when reconstructing an image from observed blurred and noisy data. Our approach uses information from the observed image to enforce boundary conditions that continue image features such as edges and texture across the boundary. Because of its similarity to methods used in texture synthesis, we call our approach synthetic boundary conditions. We provide an efficient algorithm for implementing the new boundary condition, and provide a linear algebraic framework for the approach that puts it in the context of more classical and well known image boundary conditions, including zero, periodic, reflective, and anti-reflective. Extensive numerical experiments show that our new synthetic boundary conditions provide a more accurate approximation of the true image scene outside the image boundary, and thus allow for better reconstructions of the unknown, true image scene. [Copyright &y& Elsevier]
- Published
- 2011
- Full Text
- View/download PDF
11. Improved Hessian approximation with modified secant equations for symmetric rank-one method
- Author
-
Modarres, Farzin, Malik, Abu Hassan, and Leong, Wah June
- Subjects
- *
APPROXIMATION theory , *ALGORITHMS , *NUMERICAL analysis , *MATHEMATICAL symmetry , *MATHEMATICAL analysis , *NUMERICAL solutions to equations - Abstract
Abstract: Symmetric rank-one (SR1) is one of the competitive formulas among the quasi-Newton (QN) methods. In this paper, we propose some modified SR1 updates based on the modified secant equations, which use both gradient and function information. Furthermore, to avoid the loss of positive definiteness and zero denominators of the new SR1 updates, we apply a restart procedure to this update. Three new algorithms are given to improve the Hessian approximation with modified secant equations for the SR1 method. Numerical results show that the proposed algorithms are very encouraging and the advantage of the proposed algorithms over the standard SR1 and BFGS updates is clearly observed. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
12. An efficient computational method for linear fifth-order two-point boundary value problems
- Author
-
Lv, Xueqin and Cui, Minggen
- Subjects
- *
COMPUTATIONAL complexity , *BOUNDARY value problems , *LINEAR statistical models , *ALGORITHMS , *KERNEL functions , *APPROXIMATION theory , *MATHEMATICAL analysis - Abstract
Abstract: In this paper, we present a new algorithm to solve general linear fifth-order boundary value problems (BVPs) in the reproducing kernel space . Representation of the exact solution is given in the reproducing kernel space. Its approximate solution is obtained by truncating the -term of the exact solution. Some examples are displayed to demonstrate the computational efficiency of the method. [Copyright &y& Elsevier]
- Published
- 2010
- Full Text
- View/download PDF
13. Randomized priority algorithms
- Author
-
Angelopoulos, Spyros and Borodin, Allan
- Subjects
- *
COMPUTER scheduling , *MATHEMATICAL optimization , *CASE studies , *APPROXIMATION theory , *ALGORITHMS , *MATHEMATICAL analysis - Abstract
Abstract: Borodin, Nielsen and Rackoff introduced the class of priority algorithms as a framework for modeling deterministic greedy-like algorithms. In this paper we address the effect of randomization in greedy-like algorithms. More specifically, we consider approximation ratios within the context of randomized priority algorithms. As case studies, we prove inapproximation results for two well-studied optimization problems, namely facility location and makespan scheduling. [Copyright &y& Elsevier]
- Published
- 2010
- Full Text
- View/download PDF
14. An approximate programming method based on the simplex method for bilevel programming problem
- Author
-
Wang, Guangmin, Zhu, Kejun, and Wan, Zhongping
- Subjects
- *
APPROXIMATION theory , *NONLINEAR programming , *MATHEMATICAL optimization , *ALGORITHMS , *MATHEMATICAL analysis - Abstract
Abstract: Many real problems can be modeled to the problems with a hierarchical structure, and bilevel programming is a useful tool to solve the hierarchical optimization problems. So the bilevel programming is widely applied, and numerous methods have been proposed to solve this programming. In this paper, we propose an approximate programming algorithm to solve bilevel nonlinear programming problem. Finally, the example illustrates the feasibility of the proposed algorithm. [Copyright &y& Elsevier]
- Published
- 2010
- Full Text
- View/download PDF
15. Hardness results and approximation algorithms for (weighted) paired-domination in graphs
- Author
-
Chen, Lei, Lu, Changhong, and Zeng, Zhenbing
- Subjects
- *
APPROXIMATION theory , *ALGORITHMS , *DOMINATING set , *GRAPH theory , *DYNAMIC programming , *COMBINATORICS , *COMPUTER science , *MATHEMATICAL analysis - Abstract
Abstract: Let be a simple graph without isolated vertices. A vertex set is a paired-dominating set if every vertex in has a neighbor in and the induced subgraph has a perfect matching. In this paper, we investigate the approximation hardness of paired-domination in graphs. For weighted paired-domination, an approximation algorithm in general graphs and an exact dynamic programming style algorithm in trees are also given. [Copyright &y& Elsevier]
- Published
- 2009
- Full Text
- View/download PDF
16. A two-dimensional matrix Padé-type approximation in the inner product space
- Author
-
Tao, Youtian and Gu, Chuanqing
- Subjects
- *
PADE approximant , *APPROXIMATION theory , *MATRICES (Mathematics) , *LINEAR systems , *ALGORITHMS , *INNER product spaces , *POLYNOMIALS , *MATHEMATICAL analysis - Abstract
Abstract: By introducing a bivariate matrix-valued linear functional on the scalar polynomial space, a general two-dimensional (2-D) matrix Padé-type approximant () in the inner product space is defined in this paper. The coefficients of its denominator polynomials are determined by taking the direct inner product of matrices. The remainder formula is developed and an algorithm for the numerator polynomials is presented when the generating polynomials are given in advance. By means of the Hankel-like coefficient matrix, a determinantal expression of is presented. Moreover, to avoid the computation of the determinants, two efficient recursive algorithms are proposed. At the end the method of is applied to partial realization problems of 2-D linear systems. [Copyright &y& Elsevier]
- Published
- 2009
- Full Text
- View/download PDF
17. Condition number based complexity estimate for computing local extrema
- Author
-
She, Zhikun and Zheng, Zhiming
- Subjects
- *
ALGORITHMS , *EXTREMAL problems (Mathematics) , *METHOD of steepest descent (Numerical analysis) , *APPROXIMATION theory , *MATHEMATICAL analysis - Abstract
Abstract: In this paper, we present a new algorithm for computing local extrema by modifying and combining algorithms in symbolic and numerical computation. This new algorithm improves the classical steepest descent method that may not terminate, by combining a Sturm’s theorem based separation method and a sufficient condition on infeasibility. In addition, we incorporate a grid subdivision method into our algorithm to approximate all local extrema. The complexity of our algorithm is polynomial in a newly defined condition number, and singly exponential in the number of variables. [Copyright &y& Elsevier]
- Published
- 2009
- Full Text
- View/download PDF
18. An improved randomized approximation algorithm for maximum triangle packing
- Author
-
Chen, Zhi-Zhong, Tanahashi, Ruka, and Wang, Lusheng
- Subjects
- *
ALGORITHMS , *COMBINATORIAL packing & covering , *MATHEMATICAL constants , *POLYNOMIALS , *MATHEMATICAL analysis , *APPROXIMATION theory - Abstract
Abstract: This paper deals with the maximum triangle packing problem. For this problem, Hassin and Rubinstein gave a randomized polynomial-time approximation algorithm that achieves an expected ratio of for any constant . By modifying their algorithm, we obtain a new randomized polynomial-time approximation algorithm for the problem which achieves an expected ratio of for any constant . [Copyright &y& Elsevier]
- Published
- 2009
- Full Text
- View/download PDF
19. Approximation algorithms and hardness results for the clique packing problem
- Author
-
Chataigner, F., Manić, G., Wakabayashi, Y., and Yuster, R.
- Subjects
- *
ALGORITHMS , *APPROXIMATION theory , *ASSIGNMENT problems (Programming) , *ISOMORPHISM (Mathematics) , *GRAPH theory , *TRIANGLES , *MATHEMATICAL analysis - Abstract
Abstract: For a fixed family of graphs, an -packing in a graph is a set of pairwise vertex-disjoint subgraphs of , each isomorphic to an element of . Finding an -packing that maximizes the number of covered edges is a natural generalization of the maximum matching problem, which is just . In this paper we provide new approximation algorithms and hardness results for the -packing problem where . We show that already for the -packing problem is APX-complete, and, in fact, we show that it remains so even for graphs with maximum degree 4. On the positive side, we give an approximation algorithm with approximation ratio at most 2 for every fixed . For we obtain better approximations. For we obtain a simple -approximation, achieving a known ratio that follows from a more involved algorithm of Halldórsson. For , we obtain a -approximation, and for we obtain a -approximation. [Copyright &y& Elsevier]
- Published
- 2009
- Full Text
- View/download PDF
20. Improved approximations for max set splitting and max NAE SAT
- Author
-
Zhang, Jiawei, Ye, Yinyu, and Han, Qiaoming
- Subjects
- *
ALGORITHMS , *APPROXIMATION theory , *MATHEMATICAL programming , *MATHEMATICAL analysis - Abstract
We present a 0.7499-approximation algorithm for Max Set Splitting in this paper. The previously best known result for this problem is a 0.7240-approximation by Andersson and Engebretsen (Inform. Process. Lett. 65 (1998) 305), which is based on a semidefinite programming (SDP) relaxation. Our improvement is resulted from a strengthened SDP relaxation, an improved rounding method, and a tighter analysis compared with that in Andersson and Engebretsen (1998). [Copyright &y& Elsevier]
- Published
- 2004
- Full Text
- View/download PDF
21. Sub-sample swapping for sequential Monte Carlo approximation of high-dimensional densities in the context of complex object tracking.
- Author
-
Dubuisson, Séverine, Gonzales, Christophe, and Son Nguyen, Xuan
- Subjects
- *
MONTE Carlo method , *APPROXIMATION theory , *ALGORITHMS , *PARTITIONS (Mathematics) , *SEQUENTIAL analysis , *MATHEMATICAL analysis - Abstract
Abstract: In this paper, we address the problem of complex object tracking using the particle filter framework, which essentially amounts to estimate high-dimensional distributions by a sequential Monte Carlo algorithm. For this purpose, we first exploit Dynamic Bayesian Networks to determine conditionally independent subspaces of the object’s state space, which allows us to independently perform the particle filter’s propagations and corrections over small spaces. Second, we propose a swapping process to transform the weighted particle set provided by the update step of the particle filter into a “new particle set” better focusing on high peaks of the posterior distribution. This new methodology, called Swapping-Based Partitioned Sampling, is proved to be mathematically sound and is successfully tested and validated on synthetic video sequences for single or multiple articulated object tracking. [Copyright &y& Elsevier]
- Published
- 2013
- Full Text
- View/download PDF
22. Fuzzy approximation relations on fuzzy n-cell number space and their applications in classification
- Author
-
Wang, Guixiang, Shi, Peng, and Wen, Chenglin
- Subjects
- *
FUZZY numbers , *APPROXIMATION theory , *ALGORITHMS , *VECTOR analysis , *DIMENSIONAL analysis , *MATHEMATICAL analysis , *CLASSIFICATION , *FUZZY systems - Abstract
Abstract: In this paper, the problems of fuzzy binary relations on fuzzy n-cell number space and their applications are investigated. Firstly, we have defined some fuzzy approximation relations on fuzzy n-cell number space, and studied their properties. Secondly, as application, we have developed an algorithmic version of classification in an imprecise or uncertain environment by using the fuzzy approximation relations. Practical examples are provided to show the application and rationality of the proposed techniques. [Copyright &y& Elsevier]
- Published
- 2011
- Full Text
- View/download PDF
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.