Efficient Preprocessing of Simple Binary Pattern Forests

Multipattern matching in trees is fundamental to a variety of programming language systems. A bottleneck in this connection has been the combinatorial problem of constructing the immediate subsumption tree for a simple binary pattern forest. We reduce the complexity of this problem fromO(n²) time andO(n²) space toO(n log n) time andO(n) space. Such a result was conjectured possible in 1982 by C. Hoffmann and J. O'Donnell (J. Assoc. Comput. Mach.29(1) (1982), 68–95) and in 1992 finding it was called a main open problem by J. Cai, R. Paige, and R. Tarjan (J. Theoret. Comput. Sci.106(1992), 21–60).     

Finding minimal nested polygons

An algorithm for finding a polygon with minimum number of edges nested in two simplen-sided polygons is presented. The algorithm solves the problem in at mostO(n logn) time, and improves the time complexity of two previousO(n ²) algorithms.The work was supported by NSERC grant OPG0041629.     

Heat flow and a faster algorithm to compute the surface area of a convex body

We draw on the observation that the amount of heat diffusing outside of a heated body in a short period of time is proportional to its surface area, to design a simple algorithm for approximating the surface area of a convex body given by a membership oracle. Our method has a complexity of O^*(n⁴), where n is the dimension, compared to O^*(n⁸) for the previous best algorithm. We show that our complexity cannot be improved given the current state‐of‐the‐art in volume estimation. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 43, 407–428, 2013     

On strategy improvement algorithms for simple stochastic games

The study of simple stochastic games (SSGs) was initiated by Condon for analyzing the computational power of randomized space-bounded alternating Turing machines. The game is played by two players, MAX and MIN, on a directed multigraph, and when the play terminates at a sink vertex s, MAX wins from MIN a payoff p(s)∈[0,1]. Condon proved that the problem SSG-VALUE—given a SSG, determine whether the expected payoff won by MAX is greater than 1/2 when both players use their optimal strategies—is in NP∩coNP. However, the exact complexity of this problem remains open, as it is not known whether the problem is in P or is hard for some natural complexity class. In this paper, we study the computational complexity of a strategy improvement algorithm by Hoffman and Karp for this problem. The Hoffman–Karp algorithm converges to optimal strategies of a given SSG, but no non-trivial bounds were previously known on its running time. We prove a bound of O(n²/n) on the convergence time of the Hoffman–Karp algorithm, and a bound of O(²0.78n) on a randomized variant. These are the first non-trivial upper bounds on the convergence time of these strategy improvement algorithms.     

A select and insert sorting algorithm

A general sorting algorithm, having the well knownO(n ²) algorithmsStraight Insertion Sort andSelection Sort as special cases, is described. This algorithm is analyzed in the case that certain choices in the algorithm are done randomly, and this yields an algorithm that has an average complexity ofO(n ^1.5) and a worst case complexity ofO(n ²). However, making random choices (by some random number generator) is time consuming, and a simple quasi-random scheme is therefore implemented. Test runs indicate that also this version has average complexity ofO(n ^1.5), and it even seems to perform better than the version using real random choices (even if we disregard the time used for the random choices). This version also needs very little administrative overhead, and it therefore compares favourably to many other sorting algorithms for small and medium sized arrays.     

A parallel wilf algorithm for complex zeros of a polynomial

A global recursive bisection algorithm is described for computing the complex zeros of a polynomial. It has complexityO(n ³ p) wheren is the degree of the polynomial andp the bit precision requirement. Ifn processors are available, it can be realized in parallel with complexityO(n ² p); also it can be implemented using exact arithmetic. A combined Wilf-Hansen algorithm is suggested for reduction in complexity.     

Optimally Cutting a Surface into a Disk

We consider the problem of cutting a subset of the edges of a polyhedral manifold surface, possibly with boundary, to obtain a single topological disk, minimizing either the total number of cut edges or their total length. We show that this problem is NP-hard in general, even for manifolds without boundary and for punctured spheres. We also describe an algorithm with running time n ^O(g+k), where n is the combinatorial complexity, g is the genus, and k is the number of boundary components of the input surface. Finally, we describe a greedy algorithm that outputs a O(log² g)-approximation of the minimum cut graph in O(g ² n log n) time.     

A Parallel Reduction of Hamiltonian Cycle to Hamiltonian Path in Tournaments

We propose a parallel algorithm which reduces the problem of computing Hamiltonian cycles in tournaments to the problem of computing Hamiltonian paths. The running time of our algorithm is O(log n) using O(n²/log n) processors on a CRCW PRAM, and O(log n log log n) on an EREW PRAM using O(n²/log n log log n) processors. As a corollary, we obtain a new parallel algorithm for computing Hamiltonian cycles in tournaments. This algorithm can be implemented in time O(log n) using O(n²/log n) processors in the CRCW model and in time O(log²n) with O(n²/log n log log n) processors in the EREW model.     

A parallel search algorithm for directed acyclic graphs

A parallel algorithm for depth-first searching of a directed acyclic graph (DAG) on a shared memory model of a SIMD computer is proposed. The algorithm uses two parallel tree traversal algorithms, one for the preorder traversal and the other for therpostorder traversal of an ordered tree. Each of these traversal algorithms has a time complexity ofO(logn) whenO(n) processors are used,n being the number of vertices in the tree. The parallel depth-first search algorithm for a directed acyclic graphG withn vertices has a time complexity ofO((logn)²) whenO(n ^2.81/logn) processors are used.     

Scheduling unit time jobs with integer release dates to minimize the weighted number of tardy jobs

Consider a set of n unit time jobs, each one having a release date, a due date, both nonnegative integers, and a weight, a positive real number. Given a set of m parallel machines, we describe an algorithm for finding schedules with minimum weighted number of tardy jobs. The complexity of the proposed algorithm is O(n²\frac(1+logm)m)O(n^{2}\frac{(1+\log m)}{m}) . The best previous algorithm for this problem has complexity O(mn ³) and employs network flow techniques. Our method is based on a characterization for schedules of this type and employs graph theoretic tools.     

Fast Algorithm for Cross-Validation of the Best Linear Unbiased Predictor

This article proposes a new algorithm for cross-validation of the best linear unbiased predictor. The algorithm relies on a new technique for downdating the inverse of a Cholesky factor. Given n data points, the new algorithm has complexity O(n³), compared to O(n⁴), which is the order for the more traditional delete one and recalculate method.     

A new algorithm for the quasi-assignment problem

The quasi-assignment problem can be used to solve the bus scheduling problem, the tourist guide problem, and the minimum number of chains in a partially ordered set. A successive shortest path algorithm for the assignment problem is extended to the quasiassignment problem. The algorithm is a variation of the primal-dual algorithm, and its computational complexity isO(n ³).The research for this paper was partly supported by the Chinese National Science Foundation.     

O(n2.5) time algorithms for the subgraph homeomorphism problem on trees

The complexity of the subgraph homeomorphism problems have been open. We show O(n^2.5) time algorithms when the problems are restricted to trees, directed or undirected. The algorithm can be applied to the subtree isomorphism problem for unrooted trees with the same complexity, and improves over Reyner's O(n^3.5) algorithm for the subtree isomorphism problem.     

On Conditional Covering Problem

The conditional covering problem (CCP) aims to locate facilities on a graph, where the vertex set represents both the demand points and the potential facility locations. The problem has a constraint that each vertex can cover only those vertices that lie within its covering radius and no vertex can cover itself. The objective of the problem is to find a set that minimizes the sum of the facility costs required to cover all the demand points. An algorithm for CCP on paths was presented by Horne and Smith (Networks 46(4):177–185, 2005). We show that their algorithm is wrong and further present a correct O(n ³) algorithm for the same. We also propose an O(n ²) algorithm for the CCP on paths when all vertices are assigned unit costs and further extend this algorithm to interval graphs without an increase in time complexity.     

A faster algorithm for 2-cyclic robotic scheduling with a fixed robot route and interval processing times

Consider an m-machine production line for processing identical parts served by a mobile robot. The problem is to find the minimum cycle time for 2-cyclic schedules, in which exactly two parts enter and two parts leave the production line during each cycle. This work treats a special case of the 2-cyclic robot scheduling problem when the robot route is given and the operation durations are to be chosen from prescribed intervals. The problem was previously proved to be polynomially solvable in O(m⁸log m) time. This paper proposes an improved algorithm with reduced complexity O(m⁴).     

An approximation algorithm for the minimum two peripatetic salesmen problem with different weight functions

We present a polynomial algorithm with time complexity O(n ⁵) and approximation ratio 4/3 (plus some additive constant) for the minimum 2-peripatetic salesman problem in a complete n-vertex graph with different weight functions valued 1 and 2 (abbreviated to as 2-PSP(1, 2)-min-2w). This result improves the available algorithm for this problem with approximation ratio 11/7.     

Scheduling jobs with release times preemptively on a single machine to minimize the number of late jobs

We give a direct combinatorial O(n³logn) algorithm for minimizing the number of late jobs on a single machine when jobs have release times and preemptions are allowed. Our algorithm improves the earlier O(n⁵) and O(n⁴) dynamic programming algorithms for this problem.     

On the Piano Movers' problem: IV. Various decomposable two-dimensional motion-planning problems

Various special motion-planning problems involving arbitrarily many degrees of freedom are shown to admit relatively simple solutions by techniques based on the connectivity graph approach described by Schwartz and Sharir. The solutions exploit the particularly simple configuration space structure of the robot systems considered. A typical problem is that of planning motions for a 2-dimensional robot system consisting of several arms all jointed at one common endpoint and free to rotate past each other. The algorithm given for solving this problem runs in time O(n^k+4), where k is the number of arms.     

Improved complexity results for several multifacility location problems on trees

In this paper we consider multifacility location problems on tree networks. On general networks, these problems are usually NP-hard. On tree networks, however, often polynomial time algorithms exist; e.g., for the median, center, centdian, or special cases of the ordered median problem. We present an enhanced dynamic programming approach for the ordered median problem that has a time complexity of just O(ps ² n ⁶) for the absolute and O(ps ² n ²) for the node restricted problem, improving on the previous results by a factor of O(n ³). (n and p being the number of nodes and new facilities, respectively, and s (≤n) a value specific for the ordered median problem.) The same reduction in complexity is achieved for the multifacility k-centrum problem leading to O(pk ² n ⁴) (absolute) and O(pk ² n ²) (node restricted) algorithms.     

Fast Nonparametric Density-Based Clustering of Large Datasets Using a Stochastic Approximation Mean-Shift Algorithm

Mean-shift is an iterative procedure often used as a nonparametric clustering algorithm that defines clusters based on the modal regions of a density function. The algorithm is conceptually appealing and makes assumptions neither about the shape of the clusters nor about their number. However, with a complexity of O(n²) per iteration, it does not scale well to large datasets. We propose a novel algorithm which performs density-based clustering much quicker than mean shift, yet delivering virtually identical results. This algorithm combines subsampling and a stochastic approximation procedure to achieve a potential complexity of O(n) at each step. Its convergence is established. Its performances are evaluated using simulations and applications to image segmentation, where the algorithm was tens or hundreds of times faster than mean shift, yet causing negligible amounts of clustering errors. The algorithm can be combined with existing approaches to further accelerate clustering.