A fast algorithm for near cost optimal line plans

We consider the design of line plans in public transport at a minimal total cost. Both, linear and nonlinear integer programming are adequate and intuitive modeling approaches for this problem. We present a heuristic variable fixing procedure which builds on problem knowledge from both techniques. We derive and compare lower bounds from different linearizations in order to assess the quality of our solutions. The involved integer linear programs are strengthened by means of problem specific valid inequalities. Computational results with practical data from the Dutch Railways indicate that our algorithm gives excellent solutions within minutes of computation time.     

A probably fast,provably optimal algorithm for rectilinear Steiner trees

We use the technique of divide-and-conquer to construct a rectilinear Steiner minimal tree on a set of sites in the plane. A well-known optimal algorithm for this problem by Dreyfus and Wagner [10] is used to solve the problem in the base case. The run time of our optimal algorithm is probabilistic in nature: for all ? > 0, there exists b > 0 such that Prob[T(n) > 2^{b√n log n]>1–?, for n log n} > 1 – ?, for n sites uniformly distributed on a rectangle. The key fact in the run-time argument is the existence of probable bounds on the number of edges of an optimal tree crossing our subdivision lines. We can test these bounds in low-degree polynomial time for any given set of sites. © 1994 John Wiley & Sons, Inc.     

PORA: A Physarum-inspired obstacle-avoiding routing algorithm for integrated circuit design

The plasmodium of Physarum polycephalum, a large, amoeboid cell, has attracted much attention recently due to its intelligent behaviors in pathfinding, danger avoidance, and network construction. Inspired by the biological behaviors of this primitive organism, in this study, we explore the optimization capability of Physarum polycephalum systematically and present the first Physarum-inspired obstacle-avoiding routing algorithm for the physical design of integrated circuits. We simulate the foraging behaviors of Physarum polycephalum using a novel nutrition absorption/consumption mathematical model, thereby presenting an efficient routing tool called Physarum router. With the proposed routing approach, for a given set of pin vertices and a given set of on-chip functional modules, a rectilinear Steiner minimal tree connecting all the pin vertices while avoiding the blockage of functional modules can be constructed automatically. Furthermore, several heuristics including a divide-and-conquer strategy, a non-pin leaf node pruning strategy, a dynamic parameter strategy, etc., are integrated into the proposed algorithm to fundamentally improve the performance of the Physarum router. Simulation results on multiple benchmarks confirm that the proposed algorithm leads to shorter wirelength compared with several state-of-the-art methods.     

A cognitive model of spatial path-planning

Planning a path to a destination, given a number of options and obstacles, is a common task. We suggest a two-component cognitive model that combines retrieval of knowledge about the environment with search guided by visual perception. In the first component, subsymbolic information, acquired during navigation, aids in the retrieval of declarative information representing possible paths to take. In the second component, visual information directs the search, which in turn creates knowledge for the first component. The model is implemented using the ACT-R cognitive architecture and makes realistic assumptions about memory access and shifts in visual attention. We present simulation results for memory-based high-level navigation in grid and tree structures, and visual navigation in mazes, varying relevant cognitive (retrieval noise and visual finsts) and environmental (maze and path size) parameters. The visual component is evaluated with data from a multi-robot control experiment, where subjects planned paths for robots to explore a building. We describe a method to compare trajectories without referring to aligned points in the itinerary. The evaluation shows that the model provides a good fit, but also that planning strategies may vary with task loads.     

On locally optimal nonparametric tests

Summary There is an abundancy of problems in which no parametric model realistically describes the situation and in which, accordingly, we have to resort to nonparametric methods. As the numerical problems connected with nonparametric tests are becoming less and less important, rank tests, permutation tests and the like are becoming more and more part of the standard armatory of applied statisticians. The lack of tabulated critical values, for instance, should no longer be a serious objection against the use of permutation tests in practice; cf. Edgington (1987).The rationale underlying permutation and rank tests has been outlined in quite a number of text books and papers; cf. Fraser (1957), Lehmann (1959), Hájek-Sidák (1967) or Witting (1970). Roughly speaking, permutation tests are constructibel if the data can be condensed by means of a sufficient and complete statistic allowing for the proper kind of conditioning. Rank tests arise if the underlying problem is invariant with respect to (w.r.t.) a large group of transformations which leads to a maximal invariant statistic consisting of (signed) ranks.Most practical nonparametric problems, however, are too complex to be tractable by just one of those approaches. Many of them, however, can be handled by a combination of both techniques. In this paper we outline the logic underlying that combined reduction method and apply it to construct locally most powerful tests. Moreover, we discuss what we label Hoeffding's transfer problem, i.e. the uniformity aspect of locally most powerful tests with respect to the starting point at the boundary. We are concentrating on the discussion of the nonparametric two-sample location and scale problem. Further important problems are mentioned in Section III.This is a written account of an invited lecture delivered by the third author on occasion of the 14th Symposium über Operations Research, Ulm, September 6–8, 1989.     

Robustness of locally optimal stabilization

Translated from Optimal'nost Upravlyaemykh Dinamicheskikh Sistem, No. 19, pp. 63–68, Vsesoyuznyi Nauchno-Issledovatel'skii Institut Sistemnykh Issledovanii, Moscow (1988).     

A fast spherical harmonics transform algorithm

The spectral method with discrete spherical harmonics transform plays an important role in many applications. In spite of its advantages, the spherical harmonics transform has a drawback of high computational complexity, which is determined by that of the associated Legendre transform, and the direct computation requires time of for cut-off frequency . In this paper, we propose a fast approximate algorithm for the associated Legendre transform. Our algorithm evaluates the transform by means of polynomial interpolation accelerated by the Fast Multipole Method (FMM). The divide-and-conquer approach with split Legendre functions gives computational complexity . Experimental results show that our algorithm is stable and is faster than the direct computation for .

     

A fast algorithm for balanced sampling

Summary  The cube method (Deville & Tillé 2004) is a large family of algorithms that allows selecting balanced samples with equal or unequal inclusion probabilities. In this paper, we propose a very fast implementation of the cube method. The execution time does not depend on the square of the population size anymore, but only on the population size. Balanced samples can thus be selected in very large populations of several hundreds of thousands of units.     

A simple fast hybrid pattern-matching algorithm

The Knuth–Morris–Pratt (KMP) pattern-matching algorithm guarantees both independence from alphabet size and worst-case execution time linear in the pattern length; on the other hand, the Boyer–Moore (BM) algorithm provides near-optimal average-case and best-case behaviour, as well as executing very fast in practice. We describe a simple algorithm that employs the main ideas of KMP and BM (with a little help from Sunday) in an effort to combine these desirable features. Experiments indicate that in practice the new algorithm is among the fastest exact pattern-matching algorithms discovered to date, apparently dominant for alphabet size above 15–20.     

A fast algorithm for image registration

An algorithm is presented here to estimate a smooth motion at a high frame rate. It is derived from the non-linear constant brightness assumption. A hierarchical approach reduces the dimension of the space of admissible displacements, hence the number of unknown parameters is small compared to the size of the data. The optimal displacement is estimated by a Gauss–Newton method, and the matrix required at each step is assembled rapidly using a finite-element method. To cite this article: J. Fehrenbach, M. Masmoudi, C. R. Acad. Sci. Paris, Ser. I 346 (2008).     

A fast algorithm for equitable coloring

A proper vertex coloring of a graph is equitable if the sizes of color classes differ by at most one. The celebrated Hajnal-Szemerédi Theorem states: For every positive integer r, every graph with maximum degree at most r has an equitable coloring with r+1 colors. We show that this coloring can be obtained in O(rn ²) time, where n is the number of vertices.     

A locally optimal hierarchical divisive heuristic for bipartite modularity maximization

Given a set of entities, cluster analysis aims at finding subsets, also called clusters or communities or modules, entities of which are homogeneous and well separated. In the last ten years clustering on networks, or graphs, has been a subject of intense study. Edges between pairs of vertices within the same cluster should be relatively dense, while edges between pairs of vertices in different clusters should be relatively sparse. This led Newman to define the modularity of a cluster as the difference between the number of internal edges and the expected number of such edges in a random graph with the same degree distribution. The modularity of a partition of the vertices is the sum of the modularities of its clusters. Modularity has been extended recently to the case of bipartite graphs. In this paper we propose a hierarchical divisive heuristic for approximate modularity maximization in bipartite graphs. The subproblem of bipartitioning a cluster is solved exactly; hence the heuristic is locally optimal. Several formulations of this subproblem are presented and compared. Some are much better than others, and this illustrates the importance of reformulations. Computational experiences on a series of ten test problems from the literature are reported.     

A fast algorithm for multivariate Hermite interpolation

Multivariate Hermite interpolation is widely applied in many fields, such as finite element construction, inverse engineering, CAD etc.. For arbitrarily given Hermite interpolation conditions, the typical method is to compute the vanishing ideal I （the set of polynomials satisfying all the homogeneous interpolation conditions are zero） and then use a complete residue system modulo I as the interpolation basis. Thus the interpolation problem can be converted into solving a linear equation system. A generic algorithm was presented in [18], which is a generalization of BM algorithm [22] and the complexity is O（τ^3） where r represents the number of the interpolation conditions. In this paper we derive a method to obtain the residue system directly from the relative position of the points and the corresponding derivative conditions （presented by lower sets） and then use fast GEPP to solve the linear system with O（（τ ＋ 3）τ^2） operations, where τ is the displacement-rank of the coefficient matrix. In the best case τ = 1 and in the worst case τ = [τ/n], where n is the number of variables.     

A fast algorithm for coloring Meyniel graphs

We color the nodes of a graph by first applying successive contractions to non-adjacent nodes until we get a clique; then we color the clique and decontract the graph. We show that this algorithm provides a minimum coloring and a maximum clique for any Meyniel graph by using a simple rule for choosing which nodes are to be contracted. This O(n³) algorithm is much simpler than those already existing for Meyniel graphs. Moreover, the optimality of this algorithm for Meyniel graphs provides an alternate nice proof of the following result of Hoàng: a graph G is Meyniel if and only if, for any induced subgraph of G, each node belongs to a stable set that meets all maximal cliques. Finally we give a new characterization for Meyniel graphs.     

A very fast algorithm for matrix factorization

We present a very fast algorithm for general matrix factorization of a data matrix for use in the statistical analysis of high-dimensional data via latent factors. Such data are prevalent across many application areas and generate an ever-increasing demand for methods of dimension reduction in order to undertake the statistical analysis of interest. Our algorithm uses a gradient-based approach which can be used with an arbitrary loss function provided the latter is differentiable. The speed and effectiveness of our algorithm for dimension reduction is demonstrated in the context of supervised classification of some real high-dimensional data sets from the bioinformatics literature.     

A fast algorithm for scalar Nevanlinna-Pick interpolation

Summary In this paper, we derive a fast algorithm for the scalar Nevanlinna-Pick interpolation. Givenn distinct pointsz _i in the unit disk |z|<1 andn complex numbersw _i satisfying the Pick condition for 1in, the new Nevanlinna-Pick interpolation algorithm requires onlyO(n) arithmetic operations to evaluate the interpolatory rational function at a particular value ofz, in contrast to the classical algorithm which requiresO(n ²) arithmetic operations to compute the so-called Fenyves array (which is inherent in the classical algorithm). The new algorithm bypasses the generation of the Fenyves array to speed up the computation, and also yields a parallel scheme requiring onlyO(logn) arithmetic operations on a concurrent-read, exclusive-write parallel random access machine withn processors. We must remark that the rational functionf(z) computed by the new algorithm is one degree higher than the function computed by the classical algorithm.Supported in part by the US Army Research Office Grant No. DAAL03-91-G-0106     

A fast algorithm for multiplying min-sum permutations

The present article considers the problem for determining, for given two permutations over indices from 1 to n, the permutation whose distribution matrix is identical to the min-sum product of the distribution matrices of the given permutations. This problem has several applications in computing the similarity between strings. The fastest known algorithm to date for solving this problem executes in O(n^1.5) time, or very recently, in O(nlogn) time. The present article independently proposes another O(nlogn)-time algorithm for the same problem, which can also be used to partially solve the problem efficiently with respect to time in the sense that, for given indices g and i with 1≤g<i≤n+1, the proposed algorithm outputs the values R(h) for all indices h with g≤h<i in O(n+(i−g)log(i−g)) time, where R is the solution of the problem.     

A fast imputation algorithm in quantile regression

In many applications, some covariates could be missing for various reasons. Regression quantiles could be either biased or under-powered when ignoring the missing data. Multiple imputation and EM-based augment approach have been proposed to fully utilize the data with missing covariates for quantile regression. Both methods however are computationally expensive. We propose a fast imputation algorithm (FI) to handle the missing covariates in quantile regression, which is an extension of the fractional imputation in likelihood based regressions. FI and modified imputation algorithms (FIIPW and MIIPW) are compared to existing MI and IPW approaches in the simulation studies, and applied to part of of the National Collaborative Perinatal Project study.