Algorithms for Page Retrieval and Hamiltonian Paths on Forward-Convex Line Graphs

The problems of determining whether an undirected graph G is sequentially edge-connected, whether G has a dominating path, and whether there is a Hamiltonian path in the line graph of G are shown to be equivalent. These problems are NP-hard even if G is bipartite. They can be used to model certain page retrieval problems in relational database systems in which a graph called page connectivity graph is used to represent a join operation. Many page connectivity graphs encountered in practice are forward-convex. In this paper we develop an algorithm that solves the above-mentioned problems in O(|E(G)|) time for forward-convex graphs G.     

A Class of Revised Broyden Algorithms Without Exact Line Search

In this paper, we discuss the convergence of the Broyden algorithms with revised search direction. Under some inexact line searches, we prove that the algorithms are globally convergent for continuously differentiable functions and the rate of local convergence of the algorithms is one-step superlinear and n-step second-order for uniformly convex objective functions.     

最优公交线路选择问题的数学模型及算法

公交线路选择问题是城市公共交通信息查询的重要内容，本文建立了满足不同公交线路查询者需求的最优线路选择模型并给出了相应的算法。首先通过引入各条公交线路直达最短距离矩阵构造了公交网络直达关系图（直达矩阵），在直达关系图（直达矩阵）上，利用修改了的最短路算法，即可求得最优换乘路线。根据出行者的不同需求，通过在直达关系图上定义不同的权系数，可以分别求得换乘次数最少的公交出行线路、经过站点最少的公交出行线路；通过修改最短路算法，可以求得出行耗时最少的线路及出行费用最低的线路，另外，本模型还可以综合考虑出行者的需求情况，求得出行者满意度最大的出行路线。     

用整线性插值方法导出增量算法

本文介绍了整线性插值方法 ,运用该方法使得增量算法有一个统一的处理 .作为例子 ,文中给出了如何用这种方法导出 Bresenham算法     

Developing Systems for Real-Time Streaming Analysis

Sources of streaming data are proliferating and so are the demands to analyze and mine such data in real time. Statistical methods frequently form the core of real-time analysis, and therefore, statisticians increasingly encounter the challenges and implicit requirements of real-time systems. This work recommends a comprehensive strategy for development and implementation of streaming algorithms, beginning with exploratory data analysis in a flexible computing environment, leading to specification of a computational algorithm for the streaming setting and its initial implementation, and culminating in successive improvements to computational efficiency and throughput. This sequential development relies on a collaboration between statisticians, domain scientists, and the computer engineers developing the real-time system. This article illustrates the process in the context of a radio astronomy challenge to mitigate adverse impacts of radio frequency interference (noise) in searches for high-energy impulses from distant sources. The radio astronomy application motivates discussion of system design, code optimization, and the use of hardware accelerators such as graphics processing units, field-programmable gate arrays, and IBM Cell processors. Supplementary materials, available online, detail the computing systems typically used for streaming systems with real-time constraints and the process of optimizing code for high efficiency and throughput.     

Global Convergence of Algorithms with Nonmonotone Line Search Strategy in Unconstrained Optimization

In this paper we state some nonmonotone line search strategies for unconstrained optimization algorithms. Abstracting from the concrete line search strategy we prove two general convergence results. Using this theory we can show the global convergence of the BFGS method with nonmonotone line search strategy. In contrast to some former results about nonmonotone line search strategies, both our convergence results and their proofs are natural generalizations of known results for the monotone case.     

Algorithms for ham-sandwich cuts

Given disjoint setsP ₁,P ₂, ...,P _d inR ^d withn points in total, ahamsandwich cut is a hyperplane that simultaneously bisects theP _i . We present algorithms for finding ham-sandwich cuts in every dimensiond>1. Whend=2, the algorithm is optimal, having complexityO(n). For dimensiond>2, the bound on the running time is proportional to the worst-case time needed for constructing a level in an arrangement ofn hyperplanes in dimensiond−1. This, in turn, is related to the number ofk-sets inR ^d−1 . With the current estimates, we get complexity close toO(n ^3/2 ) ford=3, roughlyO(n ^8/3 ) ford=4, andO(n ^d−1−a(d) ) for somea(d)>0 (going to zero asd increases) for largerd. We also give a linear-time algorithm for ham-sandwich cuts inR ³ when the three sets are suitably separated. A preliminary version of the results of this paper appeared in [16] and [17]. Part of this research by J. Matoušek was done while he was visiting the School of Mathematics, Georgia Institute of Technology, Atlanta, and part of his work on this paper was supported by a Humboldt Research Fellowship. W. Steiger expresses gratitude to the NSF DIMACS Center at Rutgers, and his research was supported in part by NSF Grants CCR-8902522 and CCR-9111491.     

Topological Persistence and Simplification

   Abstract. We formalize a notion of topological simplification within the framework of a filtration, which is the history of a growing complex. We classify a topological change that happens during growth as either a feature or noise depending on its lifetime or persistence within the filtration. We give fast algorithms for computing persistence and experimental evidence for their speed and utility.     

Topological Persistence and Simplification

Abstract. We formalize a notion of topological simplification within the framework of a filtration, which is the history of a growing complex. We classify a topological change that happens during growth as either a feature or noise depending on its lifetime or persistence within the filtration. We give fast algorithms for computing persistence and experimental evidence for their speed and utility.     

Algorithms for index tracking

The problem of selecting a portfolio of securities to trackthe performance of a given index is formulated in mathematicalprogramming terms. Optimal weights for given sets of includedsecurities are obtained using linear complementarity algorithms,and various methods of search among neighbouring sets of securitiesare considered. The problem of local optima is considered, andvarious methods, including simulated annealing, are suggestedfor overcoming this. The solution depends on estimation of thecovariance matrix and expected returns for the constituent securities;tracking of the FT-SE 100-share index for the calendar year1988 is solved using various estimation techniques.     

Algorithms for automated inspection

The demand to minimize the number of defects along with the increasing availability of computerized vision systems has made the on-line inspection of all production parts a feasible option in modern manufacturing systems. Vision systems enable noncontact, and thus, nondestructive measurements. An image of the production part is electronically obtained and stored in digital form in a computer. In most cases, the image is then processed to identify the local edges of the object. At a higher image processing level, information on lkocal edges is used to obtain the boundaries of the object. Measurements on the computationally obtained boundary can then be performed mathematically, allowing tests to verify the shape and dimensions of the production part. It is the purpose of this paper to investigate and present methods for the determination of shapes and the use of this information for on-line quality inspection.     

A Simplification of Root Valuation Data for Classical Groups

We study the root valuation strata of the adjoint quotient of the Lie algebra of a connected reductive group G over the field of complex numbers. Given a fixed maximal torus T of G and the corresponding Weyl group W each root valuation stratum corresponds to a pair (w,r) of an element w in W and a rational-valued function r on the set R of roots of T in G. We address the following question posed in a joint paper by Goresky, Kottwitz, and MacPherson. Suppose that for w,w′ in W and a rational-valued function r on R the two root valuation strata corresponding to (w,r) and (w′,r), respectively, are non-empty. Is it true that w and w′ are conjugate in W (more precisely, in the stabilizer of r in W)? Goresky, Kottwitz, and MacPherson show that the answer is positive if r is a constant function. We show that the answer is positive for an arbitrary r if G is of classical type.     

Algorithms for low-dimensional topology

In this article, we re-introduce the so called “Arkaden–Faden–Lage” (briefly, AFL) representation of knots in three-dimensional space introduced by Kurt Reidemeister in the 1930s and show how it can be used to develop efficient algorithms to compute some important topological knot structures. In particular, we introduce an efficient algorithm to calculate the holonomic representation of knots introduced by V. Vassiliev and give the main ideas on how to use the AFL representations of knots to compute the Kontsevich integral. The methods introduced here are to our knowledge novel and can open new perspectives in the development of fast algorithms in low-dimensional topology.