A linear-time algorithm for finding approximate shortest common superstrings

Approximate shortest common superstrings for a given setR of strings can be constructed by applying the greedy heuristics for finding a longest Hamiltonian path in the weighted graph that represents the pairwise overlaps between the strings inR. We develop an efficient implementation of this idea using a modified Aho-Corasick string-matching automaton. The resulting common superstring algorithm runs in timeO(n) or in timeO(n min(logm, log¦¦)) depending on whether or not the goto transitions of the Aho-Corasick automaton can be implemented by direct indexing over the alphabet . Heren is the total length of the strings inR andm is the number of such strings. The best previously known method requires timeO(n logm) orO(n logn) depending on the availability of direct indexing.This work was supported by the Academy of Finland.     

Degree-Optimal Routing for P2P Systems

We define a family of Distributed Hash Table systems whose aim is to combine the routing efficiency of randomized networks—e.g. optimal average path length O(log ² n/δlog δ) with δ degree—with the programmability and startup efficiency of a uniform overlay—that is, a deterministic system in which the overlay network is transitive and greedy routing is optimal. It is known that Ω(log n) is a lower bound on the average path length for uniform overlays with O(log n) degree (Xu et al., IEEE J. Sel. Areas Commun. 22(1), 151–163, 2004). Our work is inspired by neighbor-of-neighbor (NoN) routing, a recently introduced variation of greedy routing that allows us to achieve optimal average path length in randomized networks. The advantage of our proposal is that of allowing the NoN technique to be implemented without adding any overhead to the corresponding deterministic network. We propose a family of networks parameterized with a positive integer c which measures the amount of randomness that is used. By varying the value c, the system goes from the deterministic case (c=1) to an “almost uniform” system. Increasing c to relatively low values allows for routing with asymptotically optimal average path length while retaining most of the advantages of a uniform system, such as easy programmability and quick bootstrap of the nodes entering the system. We also provide a matching lower bound for the average path length of the routing schemes for any c. This work was partially supported by the Italian FIRB project “WEB-MINDS” (Wide-scalE, Broadband MIddleware for Network Distributed Services), .     

Fast Dynamic Transitive Closure with Lookahead

In this paper we consider the problem of dynamic transitive closure with lookahead. We present a randomized one-sided error algorithm with updates and queries in O(n ^{ω(1,1,ε)−ε} ) time given a lookahead of n ^ε operations, where ω(1,1,ε) is the exponent of multiplication of n×n matrix by n×n ^ε matrix. For ε≤0.294 we obtain an algorithm with queries and updates in O(n ^2−ε ) time, whereas for ε=1 the time is O(n ^ω−1). This is essentially optimal as it implies an O(n ^ω ) algorithm for boolean matrix multiplication. We also consider the offline transitive closure in planar graphs. For this problem, we show an algorithm that requires O(n^\fracw2)O(n^{\frac{\omega}{2}}) time to process n^\frac12n^{\frac{1}{2}} operations. We also show a modification of these algorithms that gives faster amortized queries. Finally, we give faster algorithms for restricted type of updates, so called element updates. All of the presented algorithms are randomized with one-sided error. All our algorithms are based on dynamic algorithms with lookahead for matrix inverse, which are of independent interest.     

Efficient construction of a bounded-degree spanner with low weight

LetS be a set ofn points in ℝ ^d and lett>1 be a real number. At-spanner forS is a graph having the points ofS as its vertices such that for any pairp, q of points there is a path between them of length at mostt times the Euclidean distance betweenp andq. An efficient implementation of a greedy algorithm is given that constructs at-spanner having bounded degree such that the total length of all its edges is bounded byO (logn) times the length of a minimum spanning tree forS. The algorithm has running timeO (n log ^d n). Applying recent results of Das, Narasimhan, and Salowe to thist-spanner gives anO(n log ^d n)-time algorithm for constructing at-spanner having bounded degree and whose total edge length is proportional to the length of a minimum spanning tree forS. Previously, noo(n ²)-time algorithms were known for constructing at-spanner of bounded degree. In the final part of the paper, an application to the problem of distance enumeration is given. This work was supported by the ESPRIT Basic Research Actions Program, under Contract No. 7141 (Project ALCOM II).     

Parallel batch scheduling of equal-length jobs with release and due dates

In this paper we study parallel batch scheduling problems with bounded batch capacity and equal-length jobs in a single and parallel machine environment. It is shown that the feasibility problem 1|p-batch,b<n,r _j ,p _j =p,C _j ≤d _j |− can be solved in O(n ²) time and that the problem of minimizing the maximum lateness can be solved in O(n ²log n) time. For the parallel machine problem P|p-batch,b<n,r _j ,p _j =p,C _j ≤d _j |− an O(n ³log n)-time algorithm is provided, which can also be used to solve the problem of minimizing the maximum lateness in O(n ³log ² n) time.     

Approximating Shortest Paths on Weighted Polyhedral Surfaces

One common problem in computational geometry is that of computing shortest paths between two points in a constrained domain. In the context of Geographical Information Systems (GIS), terrains are often modeled as Triangular Irregular Networks (TIN) which are a special class on non-convex polyhedra. It is often necessary to compute shortest paths on the TIN surface which takes into account various weights according to the terrain features. We have developed algorithms to compute approximations of shortest paths on non-convex polyhedra in both the unweighted and weighted domain. The algorithms are based on placing Steiner points along the TIN edges and then creating a graph in which we apply Dijkstra's shortest path algorithm. For two points s and t on a non-convex polyhedral surface P , our analysis bounds the approximate weighted shortest path cost as || Π'(s,t)|| ≤ ||Π(s,t)|| + W |L| , where L denotes the longest edge length of \cal P and W denotes the largest weight of any face of P . The worst case time complexity is bounded by O(n ⁵ ) . An alternate algorithm, based on geometric spanners, is also provided and it ensures that ||Π' (s,t)|| ≤β(||Π(s,t)|| + W|L|) for some fixed constant β >1 , and it runs in O(n ³ log n) worst case time. We also present detailed experimental results which show that the algorithms perform much better in practice and the accuracy is near-optimal. Received April 15, 1998; revised February 15, 1999.     

Efficient algorithms for constructing (1+∊,β)-spanners in the distributed and streaming models

For an unweighted undirected graph G = (V,E), and a pair of positive integers α ≥ 1, β ≥ 0, a subgraph G′ = (V,H), H ⊂eqE, is called an (α,β)-spanner of G if for every pair of vertices u,v ∊ V, dist_G′(u,v) ≤ α ⋅ dist_G(u,v) + β. It was shown in [21] that for any ∊ > 0, κ = 1,2,…, there exists an integer β = β(∊,κ) such that for every n-vertex graph G there exists a (1+∊,β)-spanner G′ with O(n^1+1/κ) edges. An efficient distributed protocol for constructing (1+∊,β)-spanners was devised in [19]. The running time and the communication complexity of that protocol are O(n^1+ρ) and O(|E|n^ρ), respectively, where ρ is an additional control parameter of the protocol that affects only the additive term β. In this paper we devise a protocol with a drastically improved running time (O(n^ρ) as opposed to O(n^1+ρ)) for constructing (1+∊,β)-spanners. Our protocol has the same communication complexity as the protocol of [19], and it constructs spanners with essentially the same properties as the spanners that are constructed by the protocol of [19]. The protocol can be easily extended to a parallel implementation which runs in O(log n + (|E|⋅ n^ρlog n)/p) time using p processors in the EREW PRAM model. In particular, when the number of processors, p, is at least |E|⋅ n^ρ, the running time of the algorithm is O(log n). We also show that our protocol for constructing (1+∊,β)-spanners can be adapted to the streaming model, and devise a streaming algorithm that uses a constant number of passes and O(n^1+1/κ⋅ {log} n) bits of space for computing all-pairs-almost-shortest-paths of length at most by a multiplicative factor (1+∊) and an additive term of β greater than the shortest paths. Our algorithm processes each edge in time O(n^ρ), for an arbitrarily small ρ > 0. The only previously known algorithm for the problem [23] constructs paths of length κ times greater than the shortest paths, has the same space requirements as our algorithm, but requires O(n^1+1/κ) time for processing each edge of the input graph. However, the algorithm of [23] uses just one pass over the input, as opposed to the constant number of passes in our algorithm. We also show that any streaming algorithm for o(n)-approximate distance computation requires Ω(n) bits of space. This work was Supported by the DoD University Research Initiative (URI) administered by the Office of Naval Research under Grant N00014-01-1-0795. Michael Elkin was supported by ONR grant N00014-01-1-0795. Jian Zhang was supported by ONR grant N00014-01-1-0795 and NSF grants CCR-0105337 and ITR-0331548. Preliminary version of this paper was published in PODC’04, see [22]. After the preliminary version of our paper [22] appeared on PODC’04, Feigenbaum et al. [24] came up with a new streaming algorithm for the problem that is far more efficient than [23] in terms of time-per-edge processing. However, our algorithm is still the only existing streaming algorithm that provides an almost additive approximation of distances.     

Some notes on maximal arc intersection of spherical polygons: its \mathcal{NP} -hardness and approximation algorithms

Finding a sequence of workpiece orientations such that the number of setups is minimized is an important optimization problem in manufacturing industry. In this paper we present some interesting notes on this optimal workpiece setup problem. These notes show that (1) The greedy algorithm proposed in Comput. Aided Des. 35 (2003), pp. 1269–1285 for the optimal workpiece setup problem has the performance ratio bounded by O(ln n−ln ln n+0.78), where n is the number of spherical polygons in the ground set; (2) In addition to greedy heuristic, linear programming can also be used as a near-optimal approximation solution; (3) The performance ratio by linear programming is shown to be tighter than that of greedy heuristic in some cases.     

Improved heuristics for the bounded-diameter minimum spanning tree problem

Given an undirected, connected, weighted graph and a positive integer k, the bounded-diameter minimum spanning tree (BDMST) problem seeks a spanning tree of the graph with smallest weight, among all spanning trees of the graph, which contain no path with more than k edges. In general, this problem is NP-Hard for 4 ≤ k < n − 1, where n is the number of vertices in the graph. This work is an improvement over two existing greedy heuristics, called randomized greedy heuristic (RGH) and centre-based tree construction heuristic (CBTC), and a permutation-coded evolutionary algorithm for the BDMST problem. We have proposed two improvements in RGH/CBTC. The first improvement iteratively tries to modify the bounded-diameter spanning tree obtained by RGH/CBTC so as to reduce its cost, whereas the second improves the speed. We have modified the crossover and mutation operators and the decoder used in permutation-coded evolutionary algorithm so as to improve its performance. Computational results show the effectiveness of our approaches. Our approaches obtained better quality solutions in a much shorter time on all test problem instances considered.     

Output-Sensitive Algorithm for Computing β-Skeletons

The β-skeleton is a measure of the internal shape of a planar set of points. We get an entire spectrum of shapes by varying the parameter β. For a fixed value of β, a β-skeleton is a geometric graph obtained by joining each pair of points whose β-neighborhood is empty. For β≥1, this neighborhood of a pair of points p _i ,p _j is the interior of the intersection of two circles of radius , centered at the points (1−β/2)p _i +(β/2)p _j and (β/2)p _i +(1−β/2)p _j , respectively. For β∈(0,1], it is the interior of the intersection of two circles of radius , passing through p _i and p _j . In this paper we present an output-sensitive algorithm for computing a β-skeleton in the metrics l ₁ and l _∞ for any β≥2. This algorithm is in O(nlogn+k), where k is size of the output graph. The complexity of the previous best known algorithm is in O(n ^5/2logn) [7]. Received April 26, 2000     

Fast Algorithms for the Density Finding Problem

We study the problem of finding a specific density subsequence of a sequence arising from the analysis of biomolecular sequences. Given a sequence A=(a ₁,w ₁),(a ₂,w ₂),…,(a _n ,w _n ) of n ordered pairs (a _i ,w _i ) of numbers a _i and width w _i >0 for each 1≤i≤n, two nonnegative numbers ℓ, u with ℓ≤u and a number δ, the Density Finding Problem is to find the consecutive subsequence A(i ^*,j ^*) over all O(n ²) consecutive subsequences A(i,j) with width constraint satisfying ℓ≤w(i,j)=∑ _r=i ^j w _r ≤u such that its density is closest to δ. The extensively studied Maximum-Density Segment Problem is a special case of the Density Finding Problem with δ=∞. We show that the Density Finding Problem has a lower bound Ω(nlog n) in the algebraic decision tree model of computation. We give an algorithm for the Density Finding Problem that runs in optimal O(nlog n) time and O(nlog n) space for the case when there is no upper bound on the width of the sequence, i.e., u=w(1,n). For the general case, we give an algorithm that runs in O(nlog ² m) time and O(n+mlog m) space, where and w _min=min  _r=1 ⁿ w _r . As a byproduct, we give another O(n) time and space algorithm for the Maximum-Density Segment Problem. Grants NSC95-2221-E-001-016-MY3, NSC-94-2422-H-001-0001, and NSC-95-2752-E-002-005-PAE, and by the Taiwan Information Security Center (TWISC) under the Grants NSC NSC95-2218-E-001-001, NSC95-3114-P-001-002-Y, NSC94-3114-P-001-003-Y and NSC 94-3114-P-011-001.     

Computing the Greedy Spanner in Near-Quadratic Time

The greedy algorithm produces high-quality spanners and, therefore, is used in several applications. However, even for points in d-dimensional Euclidean space, the greedy algorithm has near-cubic running time. In this paper, we present an algorithm that computes the greedy spanner for a set of n points in a metric space with bounded doubling dimension in O(n²logn)\ensuremath {\mathcal {O}}(n^{2}\log n) time. Since computing the greedy spanner has an Ω(n ²) lower bound, the time complexity of our algorithm is optimal within a logarithmic factor.     

Parallel Algorithms for Partitioning Sorted Sets and Related Problems

We consider the following partition problem: Given a set S of n elements that is organized as k sorted subsets of size n/k each and given a parameter h with 1/k ≤ h ≤ n/k , partition S into g = O(n/(hk)) subsets D ₁ , D ₂ , . . . , D _g of size Θ(hk) each, such that, for any two indices i and j with 1 ≤ i < j ≤ g , no element in D _i is bigger than any element in D _j . Note that with various combinations of the values of parameters h and k , several fundamental problems, such as merging, sorting, and finding an approximate median, can be formulated as or be reduced to this partition problem. The partition problem also finds many applications in solving problems of parallel computing and computational geometry. In this paper we present efficient parallel algorithms for solving the partition problem and a number of its applications. Our parallel partition algorithm runs in O( log n) time using processors in the EREW PRAM model. The complexity bounds of our parallel partition algorithm on the respective special cases match those of the optimal EREW PRAM algorithms for merging, sorting, and finding an approximate median. Using our parallel partition algorithm, we are also able to obtain better complexity bounds (even possibly on a weaker parallel model) than the previously best known parallel algorithms for several important problems, including parallel multiselection, parallel multiranking, and parallel sorting of k sorted subsets. Received May 5, 1996; revised July 30, 1998.     

Improved Routing and Sorting on Multibutterflies

This paper shows that an N -node AKS network (as described by Paterson) can be embedded in a ( 3N / 2 ) -node twinbutterfly network (i.e., a multibutterfly constructed by superimposing two butterfly networks) with load 1, congestion 1, and dilation 2. The result has several implications, including the first deterministic algorithms for sorting and finding the median of n log n items on an n -input multibutterfly in O ( log n ) time, a work-efficient deterministic algorithm for finding the median of n log ² n log log n items on an n -input multibutterfly in O (log n log log n ) time, and a three-dimensional VLSI layout for the n -input AKS network with volume O(n ^3/2 ) . While these algorithms are not practical, they provide further evidence of the robustness of multibutterfly networks. We also present a separate, and more practical, deterministic algorithm for routing h -relations on an n -input multibutterfly in O(h + log n) time. Previously, only algorithms for solving h one-to-one routing problems were known. Finally, we show that a twinbutterfly, whose individual splitters do not exhibit expansion, can emulate a bounded-degree multibutterfly with (α,β) -expansion, for any α⋅β < 1/4 . Received July 23, 1997; revised May 18, 1998.     

A Metropolis-Type Optimization Algorithm on the Infinite Tree

Let S(v) be a function defined on the vertices v of the infinite binary tree. One algorithm to seek large positive values of S is the Metropolis-type Markov chain (X _n ) defined by for each neighbor w of v , where b is a parameter (``1/temperature") which the user can choose. We introduce and motivate study of this algorithm under a probability model for the objective function S , in which S is a ``tree-indexed simple random walk," that is, the increments (e) = S(w)-S(v) along parent—child edges e = (v,w) are independent and P ( = 1) = p , P( = -1) = 1-p . This algorithm has a ``speed" r(p,b) = lim _n n ^-1 ES(X _n ) . We study the speed via a mixture of rigorous arguments, nonrigorous arguments, and Monte Carlo simulations, and compare with a deterministic greedy algorithm which permits rigorous analysis. Formalizing the nonrigorous arguments presents a challenging problem. Mathematically, the subject is in part analogous to recent work of Lyons et al. [19], [20] on the speed on random walk on Galton—Watson trees. A key feature of the model is the existence of a critical point p _crit below which the problem is infeasible; we study the behavior of algorithms as p p _crit. This provides a novel analogy between optimization algorithms and statistical physics. Received September 8, 1997; revised February 15, 1998.     

Tight Results on Minimum Entropy Set Cover

In the minimum entropy set cover problem, one is given a collection of k sets which collectively cover an n-element ground set. A feasible solution of the problem is a partition of the ground set into parts such that each part is included in some of the k given sets. Such a partition defines a probability distribution, obtained by dividing each part size by n. The goal is to find a feasible solution minimizing the (binary) entropy of the corresponding distribution. Halperin and Karp have recently proved that the greedy algorithm always returns a solution whose cost is at most the optimum plus a constant. We improve their result by showing that the greedy algorithm approximates the minimum entropy set cover problem within an additive error of 1 nat =log ₂ e bits ≃1.4427 bits. Moreover, inspired by recent work by Feige, Lovász and Tetali on the minimum sum set cover problem, we prove that no polynomial-time algorithm can achieve a better constant, unless P = NP. We also discuss some consequences for the related minimum entropy coloring problem. G. Joret is a Research Fellow of the Fonds National de la Recherche Scientifique (FNRS).     

On the number of transitive digraphs withn labeled vertices andk arcs

A computer determination of the numberT _n,k of transitive digraphs onn labeled vertices andk arcs is obtained for 2≤n≤6,0 ≤k≤n ²-n. Furthermore some formulae are given for determiningT _n,k, ∇n for extremal values ofk (namely, 0≤k≤6 andn ² -3n+4≤k≤n ²-n). Work carried out at Fondazione Ugo Bordoni under the agreements between Fondazione Ugo Bordoni and the Istituto Superiore P. T.     

Fast Generation of Random Permutations Via Networks Simulation

We consider the problem of generating random permutations with uniform distribution. That is, we require that for an arbitrary permutation π of n elements, with probability 1/n! the machine halts with the i th output cell containing π(i) , for 1 ≤ i ≤ n . We study this problem on two models of parallel computations: the CREW PRAM and the EREW PRAM. The main result of the paper is an algorithm for generating random permutations that runs in O(log log n) time and uses O(n ^1+o(1) ) processors on the CREW PRAM. This is the first o(log n) -time CREW PRAM algorithm for this problem. On the EREW PRAM we present a simple algorithm that generates a random permutation in time O(log n) using n processors and O(n) space. This algorithm outperforms each of the previously known algorithms for the exclusive write PRAMs. The common and novel feature of both our algorithms is first to design a suitable random switching network generating a permutation and then to simulate this network on the PRAM model in a fast way. Received November 1996; revised March 1997.     

DNA sequencing and string learning

In laboratories the majority of large-scale DNA sequencing is done following theshotgun strategy, which is to sequence large amount of relatively short fragments randomly and then heuristically find a shortest common superstring of the fragments [26]. We study mathematical frameworks, under plausible assumptions, suitable for massive automated DNA sequencing and for analyzing DNA sequencing algorithms. We model the DNA sequencing problem as learning a string from its randomly drawn substrings. Under certain restrictions, this may be viewed as string learning in Valiant's distribution-free learning model and in this case we give an efficient learning algorithm and a quantitative bound on how many examples suffice. One major obstacle to our approach turns out to be a quite well-known open question on how to approximate a shortest common superstring of a set of strings, raised by a number of authors in the last 10 years [9], [29], [30]. We give the firstprovably good algorithm which approximates a shortest superstring of lengthn by a superstring of lengthO(n logn). The algorithm works equally well even in the presence of negative examples, i.e., when merging of some strings is prohibited. Some of the results presented in this paper appeared in theProceedings of the 31st IEEE Symposium on the Foundations of Computer Science, pp. 125–134, 1990 [21]. The first author was supported in part by NSERC Operating Grant OGP0046613. The second author was supported in part by NSERC Operating Grants OGP0036747 and OGP0046506.     

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.