Compressed Indexes for Approximate String Matching

We revisit the problem of indexing a string S[1..n] to support finding all substrings in S that match a given pattern P[1..m] with at most k errors. Previous solutions either require an index of size exponential in k or need Ω(m ^k ) time for searching. Motivated by the indexing of DNA, we investigate space efficient indexes that occupy only O(n) space. For k=1, we give an index to support matching in O(m+occ+log nlog log n) time. The previously best solution achieving this time complexity requires an index of O(nlog n) space. This new index can also be used to improve existing indexes for k≥2 errors. Among others, it can support 2-error matching in O(mlog nlog log n+occ) time, and k-error matching, for any k>2, in O(m ^k−1log nlog log n+occ) time.     

Space Efficient Dynamic Orthogonal Range Reporting

In this paper we present new space efficient dynamic data structures for orthogonal range reporting. The described data structures support planar range reporting queries in time O(log n+klog log (4n/(k+1))) and space O(nlog log n), or in time O(log n+k) and space O(nlog  ^ε n) for any ε>0. Both data structures can be constructed in O(nlog n) time and support insert and delete operations in amortized time O(log ² n) and O(log nlog log n) respectively. These results match the corresponding upper space bounds of Chazelle (SIAM J. Comput. 17, 427–462, 1988) for the static case. We also present a dynamic data structure for d-dimensional range reporting with search time O(log  ^d−1 n+k), update time O(log  ^d n), and space O(nlog  ^d−2+ε n) for any ε>0. The model of computation used in our paper is a unit cost RAM with word size log n. A preliminary version of this paper appeared in the Proceedings of the 21st Annual ACM Symposium on Computational Geometry 2005. Work partially supported by IST grant 14036 (RAND-APX).     

Parallel integer sorting and simulation amongst CRCW models

 In this paper a general technique for reducing processors in simulation without any increase in time is described. This results in an O(√log n) time algorithm for simulating one step of PRIORITY on TOLERANT with processor-time product of O(n log log n); the same as that for simulating PRIORITY on ARBITRARY. This is used to obtain an O(log n/log log n+√log n (log log m− log log n)) time algorithm for sorting n integers from the set {0,…, m−1}, m≧n, with a processor-time product of O(n log log m log log n) on a TOLERANT CRCW PRAM. New upper and lower bounds for ordered chaining problem on an allocated COMMON CRCW model are also obtained. The algorithm for ordered chaining takes O(log n/log log n) time on an allocated PRAM of size n. It is shown that this result is best possible (upto a constant multiplicative factor) by obtaining a lower bound of Ω(r log n/(log r+log log n)) for finding the first (leftmost one) live processor on an allocated-COMMON PRAM of size n of r-slow virtual processors (one processor simulates r processors of allocated PRAM). As a result, for ordered chaining problem, “processor-time product” has to be at least Ω(n log n/log log n) for any poly-logarithmic time algorithm. Algorithm for ordered-chaining problem results in an O(log N/log log N) time algorithm for (stable) sorting of n integers from the set {0,…, m−1} with n-processors on a COMMON CRCW PRAM; here N=max(n, m). In particular if, m=n ^O(1) , then sorting takes Θ(log n/log log n) time on both TOLERANT and COMMON CRCW PRAMs. Processor-time product for TOLERANT is O(n(log log n)²). Algorithm for COMMON uses n processors. Received August 13, 1992/June 30, 1995     

A Tight Lower Bound for Computing the Diameter of a 3D Convex Polytope

The diameter of a set P of n points in ℝ ^d is the maximum Euclidean distance between any two points in P. If P is the vertex set of a 3-dimensional convex polytope, and if the combinatorial structure of this polytope is given, we prove that, in the worst case, deciding whether the diameter of P is smaller than 1 requires Ω(nlog n) time in the algebraic computation tree model. It shows that the O(nlog n) time algorithm of Ramos for computing the diameter of a point set in ℝ³ is optimal for computing the diameter of a 3-polytope. We also give a linear time reduction from Hopcroft’s problem of finding an incidence between points and lines in ℝ² to the diameter problem for a point set in ℝ⁷.     

An O(n 3(log log n/log n)5/4) Time Algorithm for All Pairs Shortest Path

We present an O(n ³(log log n/log n)^5/4) time algorithm for all pairs shortest paths. This algorithm improves on the best previous result of O(n ³/log n) time. Research supported in part by NSF grant 0310245.     

Precision,Local Search and Unimodal Functions

We investigate the effects of precision on the efficiency of various local search algorithms on 1-D unimodal functions. We present a (1+1)-EA with adaptive step size which finds the optimum in O(log n) steps, where n is the number of points used. We then consider binary (base-2) and reflected Gray code representations with single bit mutations. The standard binary method does not guarantee locating the optimum, whereas using the reflected Gray code does so in Θ((log n)²) steps. A(1+1)-EA with a fixed mutation probability distribution is then presented which also runs in O((log n)²). Moreover, a recent result shows that this is optimal (up to some constant scaling factor), in that there exist unimodal functions for which a lower bound of Ω((log n)²) holds regardless of the choice of mutation distribution. For continuous multimodal functions, the algorithm also locates the global optimum in O((log n)²). Finally, we show that it is not possible for a black box algorithm to efficiently optimise unimodal functions for two or more dimensions (in terms of the precision used).     

Minimum Weight Convex Steiner Partitions

New tight bounds are presented on the minimum length of planar straight line graphs connecting n given points in the plane and having convex faces. Specifically, we show that the minimum length of a convex Steiner partition for n points in the plane is at most O(log n/log log n) times longer than a Euclidean minimum spanning tree (EMST), and this bound is the best possible. Without Steiner points, the corresponding bound is known to be Θ(log n), attained for n vertices of a pseudo-triangle. We also show that the minimum length convex Steiner partition of n points along a pseudo-triangle is at most O(log log n) times longer than an EMST, and this bound is also the best possible. Our methods are constructive and lead to O(nlog n) time algorithms for computing convex Steiner partitions having O(n) Steiner points and weight within the above worst-case bounds in both cases.     

Improved Approximate String Matching Using Compressed Suffix Data Structures

Approximate string matching is about finding a given string pattern in a text by allowing some degree of errors. In this paper we present a space efficient data structure to solve the 1-mismatch and 1-difference problems. Given a text T of length n over an alphabet A, we can preprocess T and give an -bit space data structure so that, for any query pattern P of length m, we can find all 1-mismatch (or 1-difference) occurrences of P in O(|A|mlog log n+occ) time, where occ is the number of occurrences. This is the fastest known query time given that the space of the data structure is o(nlog ² n) bits. The space of our data structure can be further reduced to O(nlog |A|) with the query time increasing by a factor of log  ^ε n, for 0<ε≤1. Furthermore, our solution can be generalized to solve the k-mismatch (and the k-difference) problem in O(|A| ^k m ^k (k+log log n)+occ) and O(log  ^ε n(|A| ^k m ^k (k+log log n)+occ)) time using an -bit and an O(nlog |A|)-bit indexing data structures, respectively. We assume that the alphabet size |A| is bounded by for the -bit space data structure.     

Approximating Minimum-Power Degree and Connectivity Problems

Power optimization is a central issue in wireless network design. Given a graph with costs on the edges, the power of a node is the maximum cost of an edge incident to it, and the power of a graph is the sum of the powers of its nodes. Motivated by applications in wireless networks, we consider several fundamental undirected network design problems under the power minimization criteria. Given a graph G=(V,E)\mathcal{G}=(V,\mathcal{E}) with edge costs {c(e):e∈ℰ} and degree requirements {r(v):v∈V}, the Minimum-Power Edge-Multi-Cover\textsf{Minimum-Power Edge-Multi-Cover} (MPEMC\textsf{MPEMC} ) problem is to find a minimum-power subgraph G of G\mathcal{G} so that the degree of every node v in G is at least r(v). We give an O(log n)-approximation algorithms for MPEMC\textsf{MPEMC} , improving the previous ratio O(log ⁴ n). This is used to derive an O(log n+α)-approximation algorithm for the undirected $\textsf{Minimum-Power $\textsf{Minimum-Power ($\textsf{MP$\textsf{MP ) problem, where α is the best known ratio for the min-cost variant of the problem. Currently, _boxclosen-k)\alpha=O(\log k\cdot \log\frac{n}{n-k}) which is O(log k) unless k=n−o(n), and is O(log ² k)=O(log ² n) for k=n−o(n). Our result shows that the min-power and the min-cost versions of the $\textsf{$\textsf{ problem are equivalent with respect to approximation, unless the min-cost variant admits an o(log n)-approximation, which seems to be out of reach at the moment.     

On Metric Clustering to Minimize the Sum of Radii

Given an n-point metric (P,d) and an integer k>0, we consider the problem of covering P by k balls so as to minimize the sum of the radii of the balls. We present a randomized algorithm that runs in n ^{O(log n⋅log Δ)} time and returns with high probability the optimal solution. Here, Δ is the ratio between the maximum and minimum interpoint distances in the metric space. We also show that the problem is NP-hard, even in metrics induced by weighted planar graphs and in metrics of constant doubling dimension.     

Exact Algorithms for the Bottleneck Steiner Tree Problem

Given n points, called terminals, in the plane ℝ² and a positive integer k, the bottleneck Steiner tree problem is to find k Steiner points from ℝ² and a spanning tree on the n+k points that minimizes its longest edge length. Edge length is measured by an underlying distance function on ℝ², usually, the Euclidean or the L ₁ metric. This problem is known to be NP-hard. In this paper, we study this problem in the L _p metric for any 1≤p≤∞, and aim to find an exact algorithm which is efficient for small fixed k. We present the first fixed-parameter tractable algorithm running in f(k)⋅nlog ² n time for the L ₁ and the L _∞ metrics, and the first exact algorithm for the L _p metric for any fixed rational p with 1<p<∞ whose time complexity is f(k)⋅(n ^k +nlog n), where f(k) is a function dependent only on k. Note that prior to this paper there was no known exact algorithm even for the L ₂ metric.     

An Almost Quadratic Time Algorithm for Sparse Spliced Alignment

The sparse spliced alignment problem consists of finding a chain of zero or more exons from O(n) prescribed candidate exons of a DNA sequence of length O(n) that is most similar to a known related gene sequence of length n. This study improves the running time of the fastest known algorithm for this problem to date, which executes in O(n ^2.25) time, or very recently, in O(n ²log ² n) time, by proposing an O(n ²log n)-time algorithm.     

A New Algorithm for Finding Trees with Many Leaves

We present an algorithm that finds out-trees and out-branchings with at least k leaves in directed graphs. These problems are known as Directed Maximum Leaf Out-Tree and Directed Maximum Leaf Out-Branching, respectively, and—in the case of undirected graphs—as Maximum Leaf Spanning Tree. The run time of our algorithm is O(4 ^k nm) on directed graphs and O(poly(n)+4 ^k k ²) on undirected graphs. This improves over the previously fastest algorithms for these problems with run times of 2 ^O(klog k) poly(n) and O(poly(n)+6.75 ^k poly(k)) respectively.     

<Emphasis Type="Italic">f</Emphasis>-Sensitivity Distance Oracles and Routing Schemes

An f-sensitivity distance oracle for a weighted undirected graph G(V,E) is a data structure capable of answering restricted distance queries between vertex pairs, i.e., calculating distances on a subgraph avoiding some forbidden edges. This paper presents an efficiently constructible f-sensitivity distance oracle that given a triplet (s,t,F), where s and t are vertices and F is a set of forbidden edges such that |F|≤f, returns an estimate of the distance between s and t in G(V,E∖F). For an integer parameter k≥1, the size of the data structure is O(fkn ^1+1/k log (nW)), where W is the heaviest edge in G, the stretch (approximation ratio) of the returned distance is (8k−2)(f+1), and the query time is O(|F|⋅log ² n⋅log log n⋅log log d), where d is the distance between s and t in G(V,E∖F).     

Makespan minimization of multi-slot just-in-time scheduling on single and parallel machines

The paper addresses the problem of multi-slot just-in-time scheduling. Unlike the existing literature on this subject, it studies a more general criterion—the minimization of the schedule makespan rather than the minimization of the number of slots used by schedule. It gives an O(nlog ² n)-time optimization algorithm for the single machine problem. For arbitrary number of m>1 identical parallel machines it presents an O(nlog n)-time optimization algorithm for the case when the processing time of each job does not exceed its due date. For the general case on m>1 machines, it proposes a polynomial time constant factor approximation algorithm.     

Applying Approximate Counting for Computing the Frequency Moments of Long Data Streams

This paper takes up a remark in the well-known paper of Alon, Matias, and Szegedy (J. Comput. Syst. Sci. 58(1):137–147, 1999) about the computation of the frequency moments of data streams and shows in detail how any F _k with k≥1 can be approximately computed using space O(km ^1−1/k (k+log m+log log  n)) based on approximate counting. An important building block for this, which may be interesting in its own right, is a new approximate variant of reservoir sampling using space O(log log  n) for constant error parameters.     

Kinetic Collision Detection for Convex Fat Objects

We design compact and responsive kinetic data structures for detecting collisions between n convex fat objects in 3-dimensional space that can have arbitrary sizes. Our main results are:

OTIS-MOT: an efficient interconnection network for parallel processing

Mesh of trees (MOT) is well known for its small diameter, high bisection width, simple decomposability and area universality. On the other hand, OTIS (Optical Transpose Interconnection System) provides an efficient optoelectronic model for massively parallel processing system. In this paper, we present OTIS-MOT as a competent candidate for a two-tier architecture that can take the advantages of both the OTIS and the MOT. We show that an n⁴_-n^{4}_{-} processor OTIS-MOT has diameter 8log n ^∗+1 (The base of the logarithm is assumed to be 2 throughout this paper.) and fault diameter 8log n+2 under single node failure. We establish other topological properties such as bisection width, multiple paths and the modularity. We show that many communication as well as application algorithms can run on this network in comparable time or even faster than other similar tree-based two-tier architectures. The communication algorithms including row/column-group broadcast and one-to-all broadcast are shown to require O(log n) time, multicast in O(n ²log n) time and the bit-reverse permutation in O(n) time. Many parallel algorithms for various problems such as finding polynomial zeros, sales forecasting, matrix-vector multiplication and the DFT computation are proposed to map in O(log n) time. Sorting and prefix computation are also shown to run in O(log n) time.     

Approximating Buy-at-Bulk and Shallow-Light <Emphasis Type="Italic">k</Emphasis>-Steiner Trees

We study two related network design problems with two cost functions. In the buy-at-bulk k-Steiner tree problem we are given a graph G(V,E) with a set of terminals T⊆V including a particular vertex s called the root, and an integer k≤|T|. There are two cost functions on the edges of G, a buy cost b:E→ℝ⁺ and a distance cost r:E→ℝ⁺. The goal is to find a subtree H of G rooted at s with at least k terminals so that the cost ∑ _e∈H b(e)+∑ _t∈T−s dist(t,s) is minimized, where dist(t,s) is the distance from t to s in H with respect to the r cost. We present an O(log ⁴ n)-approximation algorithm for the buy-at-bulk k-Steiner tree problem. The second and closely related one is bicriteria approximation algorithm for Shallow-light k-Steiner trees. In the shallow-light k-Steiner tree problem we are given a graph G with edge costs b(e) and distance costs r(e), and an integer k. Our goal is to find a minimum cost (under b-cost) k-Steiner tree such that the diameter under r-cost is at most some given bound D. We develop an (O(log n),O(log ³ n))-approximation algorithm for a relaxed version of Shallow-light k-Steiner tree where the solution has at least terminals. Using this we obtain an (O(log ² n),O(log ⁴ n))-approximation algorithm for the shallow-light k-Steiner tree and an O(log ⁴ n)-approximation algorithm for the buy-at-bulk k-Steiner tree problem. Our results are recently used to give the first polylogarithmic approximation algorithm for the non-uniform multicommodity buy-at-bulk problem (Chekuri, C., et al. in Proceedings of 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06), pp. 677–686, 2006). A preliminary version of this paper appeared in the Proceedings of 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) 2006, LNCS 4110, pp. 153–163, 2006. M.T. Hajiaghayi supported in part by IPM under grant number CS1383-2-02. M.R. Salavatipour supported by NSERC grant No. G121210990, and a faculty start-up grant from University of Alberta.     

Covering Many or Few Points with Unit Disks

Let P be a set of n weighted points. We study approximation algorithms for the following two continuous facility-location problems. In the first problem we want to place m unit disks, for a given constant m≥1, such that the total weight of the points from P inside the union of the disks is maximized. We present algorithms that compute, for any fixed ε>0, a (1−ε)-approximation to the optimal solution in O(nlog n) time. In the second problem we want to place a single disk with center in a given constant-complexity region X such that the total weight of the points from P inside the disk is minimized. Here we present an algorithm that computes, for any fixed ε>0, in O(nlog ² n) expected time a disk that is, with high probability, a (1+ε)-approximation to the optimal solution. A preliminary version of this work has appeared in Approximation and Online Algorithms—WAOA 2006, LNCS, vol. 4368.