A variable dimension algorithm for the linear complementarity problem

A variable dimension algorithm is presented for the linear complementarity problems – Mz = q; s,z 0; s _i z _i = 0 fori = 1,2, ,n. The algorithm solves a sequence of subproblems of different dimensions, the sequence being possibly nonmonotonic in the dimension of the subproblem solved. Every subproblem is the linear complementarity problem defined by a leading principal minor of the matrixM. Index-theoretic arguments characterize the points at which nonmonotonic behavior occurs.     

Decision problems in the space of Dehn fillings

Normal surface theory is used to study Dehn fillings of a knot-manifold. We use that any triangulation of a knot-manifold may be modified to a triangulation having just one vertex in the boundary. In this situation, it is shown that there is a finite computable set of slopes on the boundary of the knot-manifold, which come from boundary slopes of normal or almost normal surfaces. This is combined with existence theorems for normal and almost normal surfaces to construct algorithms to determine precisely those manifolds obtained by Dehn filling of a given knot-manifold that: (1) are reducible, (2) contain two-sided incompressible surfaces, (3) are Haken, (4) fiber over S¹, (5) are the 3-sphere, and (6) are a lens space. Each of these algorithms is a finite computation.Moreover, in the case of essential surfaces, we show that the topology of each filled manifold is strongly reflected in the combinatorial properties of a triangulation of the knot-manifold with just one vertex in the boundary. If a filled manifold contains an essential surface then the knot-manifold contains an essential normal vertex solution which caps off to an essential surface of the same type in the filled manifold. (Normal vertex solutions are the premier class of normal surface and are computable.)     

Parallel and bootstrapped stochastic approximation

Parallelization of stochastic approximation procedures can reduce computation and total observation time of a system. Concerning the number of all observations used by the pure sequential and the suggested parallel method a weak invariance principle implies the asymptotic equivalence of both methods. A loglog invariance principle and a rate of a.s. convergence result describe the pathwise properties. Due to the parallel design asymptotic confidence regions can readily be constructed either by computing the bootstrap distribution or the Gaussian limit distribution determined by the empirical covariance     

用遗传算法研究Con(n=3-60)团簇的结构特性

我们采用半经验的Gupta多体势结合遗传算法,系统地研究了Con(n=3-60)团簇的几何结构特性.我们发现在钴团簇的生长中存在一个类fcc构型与类Ih构型之间的竞争,从n=39开始,钴团簇呈现出明显的Ih生长模式.Con(n=3-60)团簇的幻数为13,19,23,38,55,结合钴团簇的平均最近邻原子间距和平均配位数,分析了钴团簇幻数序列存在的原因.我们发现团簇内部原子具有增强团簇对称性和加强团簇稳定性的显著作用.     

Polynomial kernels for 3-leaf power graph modification problems

A graph G=(V,E) is a 3-leaf power iff there exists a tree T the leaf set of which is V and such that uv∈E iff u and v are at distance at most 3 in T. The 3-leaf power graph edge modification problems, i.e. edition (also known as the closest 3-leaf power), completion and edge-deletion are FPT when parameterized by the size of the edge set modification. However, polynomial kernels were known for none of these three problems. For each of them, we provide kernels with O(k³) vertices that can be computed in linear time. We thereby answer an open problem first mentioned by Dom et al. (2004) [8].     

Integration and Optimization of Multivariate Polynomials by Restriction onto a Random Subspace

We consider the problem of efficient integration of an n-variate polynomial with respect to the Gaussian measure in ℝⁿ and related problems of complex integration and optimization of a polynomial on the unit sphere. We identify a class of n-variate polynomials f for which the integral of any positive integer power f^p over the whole space is well approximated by a properly scaled integral over a random subspace of dimension O(log n). Consequently, the maximum of f on the unit sphere is well approximated by a properly scaled maximum on the unit sphere in a random subspace of dimension O(log n). We discuss connections with problems of combinatorial counting and applications to efficient approximation of a hafnian of a positive matrix.     

Subadditive approaches in integer programming

Linear programming duality is well understood and the reduced cost of a column is frequently used in various algorithms. On the other hand, for integer programs it is not clear how to define a dual function even though the subadditive dual theory has been developed a long time ago. In this work we propose a family of computationally tractable subadditive dual functions for integer programs. We develop a solution methodology that computes an optimal primal solution and an optimal subadditive dual function. We present computational experiments, which show that the new algorithm is tractable.     

Algorithms for Unconstrained Optimization Problems via Control Theory

Existing algorithms for solving unconstrained optimization problems are generally only optimal in the short term. It is desirable to have algorithms which are long-term optimal. To achieve this, the problem of computing the minimum point of an unconstrained function is formulated as a sequence of optimal control problems. Some qualitative results are obtained from the optimal control analysis. These qualitative results are then used to construct a theoretical iterative method and a new continuous-time method for computing the minimum point of a nonlinear unconstrained function. New iterative algorithms which approximate the theoretical iterative method and the proposed continuous-time method are then established. For convergence analysis, it is useful to note that the numerical solution of an unconstrained optimization problem is none other than an inverse Lyapunov function problem. Convergence conditions for the proposed continuous-time method and iterative algorithms are established by using the Lyapunov function theorem.