A mildly exponential approximation algorithm for the permanent

A new approximation algorithm for the permanent of ann ×n 0,1-matrix is presented. The algorithm is shown to have worst-case time complexity exp(O(n ^1/2 log² n)). Asymptotically, this represents a considerable improvement over the best existing algorithm, which has worst-case time complexity exp((n)).Supported by SERC Grant GR/F 90363; work done in part while visiting DIMACS (Center for Discrete Mathematics and Computer Science).Supported by an NSF PYI grant, with matching equipment grant from the AT&T Foundation; work done in part while visiting DIMACS.     

A randomized approximation algorithm for computing bucket orders

We show that a simple randomized algorithm has an expected constant factor approximation guarantee for fitting bucket orders to a set of pairwise preferences.     

A Newton-squaring algorithm for computing the negative invariantsubspace of a matrix

By combining Newton's method for the matrix sign function with a squaring procedure, a basis for the negative invariant subspace of a matrix can be computed efficiently. The algorithm presented is a variant of multiplication-rich schemes for computing the matrix sign function, such as the well-known inversion-free Schulz method, which requires two matrix multiplications per step. However, by avoiding a complete computation of the matrix sign and instead concentrating only on the negative invariant subspace, the final Newton steps can be replaced by steps which require only one matrix squaring each. This efficiency is attained without sacrificing the quadratic convergence of Newton's method     

A fast deterministic smallest enclosing disk approximation algorithm

We describe a simple and fast -time algorithm for finding a (1+?)-approximation of the smallest enclosing disk of a planar set of n points or disks. Experimental results of a readily available implementation are presented.     

一个计算Skowron差别矩阵核的新算法

为提高基于Skowron差别矩阵的求核算法的效率,引入简化决策表的定义,给出了简化Skowron差别矩阵和相应核的定义,证明了新核与基于Skowron差别矩阵的核是一致的。提出一个基于Skowron差别矩阵的快速求核新算法,其时间复杂度和空间复杂度分别降为[max{O(|C||U/C|2),O(|C||U|)}]和[max{O(|U|),O(|C|)}]。     

A deterministic analysis of stochastic approximation withrandomized directions

We study the convergence of two stochastic approximation algorithms with randomized directions: the simultaneous perturbation stochastic approximation algorithm and the random direction Kiefer-Wolfowitz algorithm. We establish deterministic necessary and sufficient conditions on the random directions and noise sequences for both algorithms, and these conditions demonstrate the effect of the “random” directions on the “sample-path” behavior of the algorithms studied. We discuss ideas for further research in the analysis and design of these algorithms     

A deterministic algorithm for isolating real roots of a real polynomial

We describe a bisection algorithm for root isolation of polynomials with real coefficients. It is assumed that the coefficients can be approximated with arbitrary precision; exact computation in the field of coefficients is not required. We refer to such coefficients as bitstream coefficients. The algorithm is simpler, deterministic and has better asymptotic complexity than the randomized algorithm of Eigenwillig et al. (2005). We also discuss a partial extension to multiple roots.     

Improved deterministic approximation algorithms for Max TSP

We present an O(n³)-time approximation algorithm for the maximum traveling salesman problem whose approximation ratio is asymptotically , where n is the number of vertices in the input complete edge-weighted (undirected) graph. We also present an O(n³)-time approximation algorithm for the metric case of the problem whose approximation ratio is asymptotically . Both algorithms improve on the previous bests.     

A geostatistics-assisted approach to the deterministic approximation of climate data

We propose a nonconventional application of variogram analysis to support climate data modelling with analytical functions. This geostatistical technique is applied in the theoretical domain defined by each model variable to detect the systematic behaviours buried in the fluctuations determined by other driving factors and to verify the ability of candidate fits to remove correlations from the data. The climatic average of the atmospheric temperature measured at 387 European meteorological stations has been analysed as a function of geographical parameters by a step-wise procedure. Our final model accounts for non-linearity in latitude with a local-scale residual correlation that decays in approximately ten kilometres. The variance of the residuals from the fitted model (approximately 3% of the total) is mostly determined by local heterogeneity in transitional climates and by urban islands. Our approach is user-friendly, and the support of statistical inference makes the modelling self-consistent.     

On deterministic approximation of DNF

We develop several quasi-polynomial-time deterministic algorithms for approximating the fraction of truth assignments that satisfy a disjunctive normal form formula. The most efficient algorithm computes for a given DNF formulaF onn variables withm clauses and > 0 an estimateY such that ¦Pr[F] –Y¦ in time which is , for any constant. Although the algorithms themselves are deterministic, their analysis is probabilistic and uses the notion of limited independence between random variables.Research supported in part by National Science Foundation Operating Grant CCR-9016468, National Science Foundation Operating Grant CCR-9304722, United States-Israel Binational Science Foundation Grant No. 89-00312, United States-Israel Binational Science Foundation Grant No. 92-00226, and ESPRIT Basic Research Grant EC-US 030.Research partially done while visiting the International Computer Science Institute and while at Carnegie Mellon University.     

Multiterminal global routing: A deterministic approximation scheme

We consider the problem of routing multiterminal nets in a two-dimensional gate-array. Given a gate-array and a set of nets to be routed, we wish to find a routing that uses as little channel space as possible. We present a deterministic approximation algorithm that uses close to the minimum possible channel space. We cast the routing problem as a new form of zero-one multicommodity flow, an integer-programming problem. We solve this integer program approximately by first solving its linear-program relaxation and then rounding any fractions that appear in the solution to the linear program. The running time of the rounding algorithm is exponential in the number of terminals in a net but polynomial in the number of nets and the size of the array. The algorithm is thus best suited to cases where the number of terminals on each net is small.     

Multiterminal global routing: A deterministic approximation scheme

We consider the problem of routing multiterminal nets in a two-dimensional gate-array. Given a gate-array and a set of nets to be routed, we wish to find a routing that uses as little channel space as possible. We present a deterministic approximation algorithm that uses close to the minimum possible channel space. We cast the routing problem as a new form of zero-one multicommodity flow, an integer-programming problem. We solve this integer program approximately by first solving its linear-program relaxation and then rounding any fractions that appear in the solution to the linear program. The running time of the rounding algorithm is exponential in the number of terminals in a net but polynomial in the number of nets and the size of the array. The algorithm is thus best suited to cases where the number of terminals on each net is small.This work was done while the authors were with the Computer Science Division, University of California at Berkeley. The work of Prabhakar Raghavan was supported by an IBM Doctoral Fellowship, and the work of Clark Thompson was supported by a California State MICRO grant (AT&T Foundation).     

面向图分割问题的确定性退火控制算法

图分割问题是一种典型的NP-hard 问题, 如何对其进行高效求解一直都是学界和工业界的一个难题. 本文构建了一种新型的确定性退火控制算法, 提供了图分割问题的一种高质量近似解法. 算法主要由两部分构成: 全局收敛的迭代过程以及屏障函数最小点组成的收敛路径. 我们证明了,当屏障因子从足够大的实数降为0, 沿着一系列由屏障问题最小点组成的收敛路径可以得到图分割问题的一种高质量的近似解. 仿真计算结果表明本文所构建算法相比已有方法的优越性     

基于可分辨矩阵的快速求核算法

目前求核算法存在以下不足:求得的核与基于正区域的核不一致,算法的时间和空间复杂度不理想.针对上述问题,提出一种简化的可分辨矩阵的定义和求核方法,并证明了由该方法获得的核与基于正区域的核是等价的.为了提高算法效率,采用分布计数的基数排序思想设计等价类U/C划分算法,其时间复杂度为O(|C||U|).在此基础上,给出快速求核算法,其时间和空间复杂度分别降为max{O(|C||U/C|2),O(|C||U|)}和O(|C||U/C|2).最后,实例说明了算法的有效性.     

A new method for computing a column reduced polynomial matrix

A new algorithm is presented for computing a column reduced form of a given full column rank polynomial matrix. The method is based on reformulating the problem as a problem of constructing a minimal polynomial basis for the right nullspace of a polynomial matrix closely related to the original one. The latter problem can easily be solved in a numerically reliable way. Three examples illustrating the method are included.     

基于改进差别矩阵的核增量式更新算法

分析发现杨明教授给出的改进的差别矩阵中存在不必要的计算,为此提出了改进的差别矩阵定义和求核方法;在此基础上提出一种基于改进差别矩阵的核增量式更新算法,主要考虑对象动态增加情况下核的更新问题.理论分析表明改进的核增量式更新算法具有近线性时间和空间复杂度.实验结果显示算法有效可行.     

Algorithms for computing the optimal transitive approximation of a proximity relation

Three ways for generating the optimal transitive approximations or a suboptimal transitive approximation are given in this paper. The first one can obtain all the optimal transitive approximations for any proximity relation. However, trying to find all the optimal transitive approximations can be very expensive. The second one gives a method to obtain a suboptimal transitive approximation which can frequently generate an optimal transitive approximation. Furthermore, starting from the transitive closure the third method is proposed which can obtain a locally optimal transitive approximation. Finally, numerical experiments are carried out to show the abilities of these algorithms and compare them to other existing approximation algorithms.     

A simple deterministic algorithm for guaranteeing the forward progress of transactions

This paper describes a remarkably simple deterministic (not probabilistic) contention-management algorithm for guaranteeing the forward progress of transactions — avoiding deadlocks, livelocks, and other anomalies. The transactions must be finite (no infinite loops), but on each restart, a transaction may access different shared-memory locations. The algorithm supports irrevocable transactions as long as the transaction satisfies a simple ordering constraint. In particular, a transaction that accesses only one shared-memory location is never aborted. The algorithm is suitable for both hardware and software transactional-memory systems. It also can be used in some contexts as a locking protocol for implementing transactions “by hand.”     

A straightforward algorithm for computing the medial axis of a simple polygon

A new algorithm for computing the medial axis of a simple polygon is presented. Although the algorithm runs in O(kN) time where k is the hierarchy of the Voronoi diagram of the polygon ranging from O(N) to O(logN) it is simple to implement and it does not require the complex data-structures required for the faster methods. This is an important factor in many applications of the medial axis.     

An adaptive stochastic approximation algorithm for simultaneousdiagonalization of matrix sequences with applications

We describe an adaptive algorithm based on stochastic approximation theory for the simultaneous diagonalization of the expectations of two random matrix sequences. Although there are several conventional approaches to solving this problem, there are many applications in pattern analysis and signal detection that require an online (i.e., real-time) procedure for this computation. In these applications, we are given two sequences of random matrices {A_k } and {B_k} as online observations, with lim_k→∞E[A_k]=A and lim_k→∞E[B_k]=B, where A and B are real, symmetric and positive definite. For every sample (A_k, B_k), we need the current estimates Φ_k and Λ_k, respectively of the eigenvectors Φ and eigenvalues Λ of A^-1 B. We have described such an algorithm where Φ_k and Λ_k converge provably with probability one to Φ and Λ respectively. A novel computational procedure used in the algorithm is the adaptive computation of A^-½. Besides its use in the generalized eigen-decomposition problem, this procedure can be used on its own in several feature extraction problems. The performance of the algorithm is demonstrated with an example of detecting a high-dimensional signal in the presence of interference and noise, in a digital mobile communications problem. Experiments comparing computational complexity and performance demonstrate the effectiveness of the algorithm in this real-time application