Search

We give a constant factor approximation algorithm for the Asymmetric Traveling Salesman Problem on shortest path metrics of directed graphs with two different edge weights. For the case of unit edge weights, the first constant factor approximation was given recently by Svensson. This was accomplished by introducing an easier problem called Local-Connectivity ATSP and showing that a good solution to this problem can be used to obtain a constant factor approximation for ATSP. In this paper, we solve Local-Connectivity ATSP for two different edge weights. The solution is based on a flow decomposition theorem for solutions of the Held-Karp relaxation, which may be of independent interest. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we propose to use Chambolle’s dual methods to solve Total Variation (TV) inpainting model and (weighted) TV colorization model. The fidelity coefficients in these two models are functions which taking zero in the inpainting region and a positive constant in the other region. Then Chambolle’s dual method can not be directly used to solve these models since the fidelity coefficient will be denominator in the algorithm. In order to overcome this drawback, we propose to approximate these models by adding new variables. Then the approximated problems can be solved by alternating minimization method with Chambolle’s dual method and closed form solutions which is fast and easy to implement. Mathematical results of existence of minimizers are proved for both the original and the approximated problems. Numerical results and comparison with other closely related methods demonstrate that our algorithms are quite efficient. [Copyright &y& Elsevier]

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]

Currently, two-dimensional dyadic wavelet transform (2D-DWT) is habitually considered as the one presented by Mallat, which is defined by an approximation component, two detail components in horizontal and vertical directions. This paper is to introduce a new type of two-dimensional dyadic wavelet transform and its application so that dyadic wavelet can be studied and used widely furthermore. (1) Two-dimensional stationary dyadic wavelet transform (2D-SDWT) is proposed, it is defined by approximation coefficients, detail coefficients in horizontal, vertical and diagonal directions, which is essentially the extension of two-dimensional stationary wavelet transform for orthogonal/biorthogonal wavelet filters. (2) ε-decimated dyadic discrete wavelet transform (DDWT) is introduced and its relation with 2D-SDWT is given, where ε is a sequence of 0's and 1's. (3) Mallat decomposition algorithm based on dyadic wavelet is introduced as a special case of ε-decimated DDWT, and so a face recognition algorithm based on dyadic wavelet is proposed, and experimental results are given to show its effectiveness. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we describe how an idea centered on the concept of self-saturation allows several improvements in the computation of Gröbner bases via Buchberger’s Algorithm. In a nutshell, the idea is to extend the advantages of computing with homogeneous polynomials or vectors to the general case. When the input data are not homogeneous, we use as a main tool the procedure of a self-saturating Buchberger’s Algorithm. Another strictly related topic is treated later when a mathematical foundation is given to the sugar trick which is nowadays widely used in most of the implementations of Buchberger’s Algorithm. A special emphasis is also given to the case of a single grading, and subsequently some timings and indicators showing the practical merits of our approach. [Copyright &y& Elsevier]

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]

Abstract: In this paper, by solving the relaxed quasiconcave programming problem in outcome space, a new global optimization algorithm for convex multiplicative programming is presented. Two kinds of techniques are employed to establish the algorithm. The first one is outer approximation technique which is applied to shrink relaxation area of quasiconcave programming problem and to compute appropriate feasible points and to raise the capacity of bounding. And the other one is branch and bound technique which is used to guarantee global optimization. Some numerical results are presented to demonstrate the effectiveness and feasibility of the proposed algorithm. [Copyright &y& Elsevier]

This paper shows how to compute O(√log n)-approximations to the Sparsest Cut and Balanced Separator problems in Õ(n²) time, thus improving upon the recent algorithm of Arora, Rao, and Vazirani [Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004, pp. 222-231]. Their algorithm uses semidefinite programming and requires Õ (n9.5) time. Our algorithm relies on efficiently finding expander flows in the graph and does not solve semidefinite programs. The existence of expander flows was also established by Arora, Rao, and Vazirani. [ABSTRACT FROM AUTHOR]

This paper considers the problem of computing the real convex hull of a finite set of n-dimensional integer vectors. The starting point is a finite-automaton representation of the initial set of vectors. The proposed method consists in computing a sequence of automata representing approximations of the convex hull and using extrapolation techniques to compute the limit of this sequence. The convex hull can then be directly computed from this limit in the form of an automaton-based representation of the corresponding set of real vectors. The technique is quite general and has been implemented. [ABSTRACT FROM AUTHOR]

Stochastic approximation problem is to find some root or extremum of a nonlinear function for which only noisy measurements of the function are available. The classical algorithm for stochastic approximation problem is the Robbins-Monro (RM) algorithm, which uses the noisy evaluation of the negative gradient direction as the iterative direction. In order to accelerate the RM algorithm, this paper gives a frame algorithm using adaptive iterative directions. At each iteration, the new algorithm goes towards either the noisy evaluation of the negative gradient direction or some other directions under some switch criterions. Two feasible choices of the criterions are proposed and two corresponding flame algorithms are formed. Different choices of the directions under the same given switch criterion in the flame can also form different algorithms. We also proposed the simultanous perturbation difference forms for the two flame algorithms. The almost surely convergence of the new algorithms are all established. The numerical experiments show that the new algorithms are promising. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we extend the algorithm in Xue and Cheng [L. Xue, X.L. Cheng, An algorithm for solving the obstacle problems, Comput. Math. Appl. 48 (2004) 1651–1657] for solving the double obstacle problem. We try to find the approximated region of the contact in the double obstacle problem with less computation time by iteration. Numerical example is given for the double obstacle problem for the elastic–plastic torsion problem to support the algorithm. [Copyright &y& Elsevier]

In this paper we study a discrete version of the classical team decision problem. It has been shown previously that the general discrete team decision problem is NP-hard. Here we present an efficient approximation algorithm for this problem. For the maximization version of this problem with nonnegative rewards, this algorithm computes decision rules which are guaranteed to be within a fixed bound of optimal. [ABSTRACT FROM AUTHOR]