Faster Deterministic Communication in Radio Networks

We study the communication primitives of broadcasting (one-to-all communication) and gossiping (all-to-all communication) in known topology radio networks, i.e., where for each primitive the schedule of transmissions is precomputed based on full knowledge about the size and the topology of the network. We show that gossiping can be completed in time units in any radio network of size n, diameter D, and maximum degree Δ=Ω(log n). This is an almost optimal schedule in the sense that there exists a radio network topology, specifically a Δ-regular tree, in which the radio gossiping cannot be completed in less than units of time. Moreover, we show a schedule for the broadcast task. Both our transmission schemes significantly improve upon the currently best known schedules by Gąsieniec, Peleg, and Xin (Proceedings of the 24th Annual ACM SIGACT-SIGOPS PODC, pp. 129–137, 2005), i.e., a O(D+Δlog n) time schedule for gossiping and a D+O(log ³ n) time schedule for broadcast. Our broadcasting schedule also improves, for large D, a very recent O(D+log ² n) time broadcasting schedule by Kowalski and Pelc. A preliminary version of this paper appeared in the proceedings of ISAAC’06. F. Cicalese supported by the Sofja Kovalevskaja Award 2004 of the Alexander von Humboldt Stiftung. F. Manne and Q. Xin supported by the Research Council of Norway through the SPECTRUM project.     

Subcubic Cost Algorithms for the All Pairs Shortest Path Problem

In this paper we give three subcubic cost algorithms for the all pairs shortest distance (APSD) and path (APSP) problems. The first is a parallel algorithm that solves the APSD problem for a directed graph with unit edge costs in O(log ² n) time with processors where μ = 2.688 on an EREW PRAM. The second parallel algorithm solves the APSP, and consequently APSD, problem for a directed graph with nonnegative general costs (real numbers) in O(log ² n) time with o(n ³ ) subcubic cost. Previously this cost was greater than O(n ³ ) . Finally we improve with respect to M the complexity O((Mn) ^μ ) of a sequential algorithm for a graph with edge costs up to M to O(M ^1/3 n ^(6+ω)/3 (log n) ^2/3 (log log n) ^1/3 ) in the APSD problem, where ω = 2.376 . Received October 15, 1995; revised June 21, 1996.     

ℓ 2 2 Spreading Metrics for Vertex Ordering Problems

We design approximation algorithms for the vertex ordering problems Minimum Linear Arrangement, Minimum Containing Interval Graph, and Minimum Storage-Time Product, achieving approximation factors of $O(\sqrt{\log n}\log\log n)We design approximation algorithms for the vertex ordering problems Minimum Linear Arrangement, Minimum Containing Interval Graph, and Minimum Storage-Time Product, achieving approximation factors of O(?{logn}loglogn)O(\sqrt{\log n}\log\log n) , O(?{logn}loglogn)O(\sqrt{\log n}\log\log n) , and O(?{logT}loglogT)O(\sqrt{\log T}\log\log T) , respectively, the last running in time polynomial in T (T being the sum of execution times). The technical contribution of our paper is to introduce “ℓ ₂² spreading metrics” (that can be computed by semidefinite programming) as relaxations for both undirected and directed “permutation metrics,” which are induced by permutations of {1,2,…,n}. The techniques introduced in the recent work of Arora, Rao and Vazirani (Proc. of 36th STOC, pp. 222–231, 2004) can be adapted to exploit the geometry of such ℓ ₂² spreading metrics, giving a powerful tool for the design of divide-and-conquer algorithms. In addition to their applications to approximation algorithms, the study of such ℓ ₂² spreading metrics as relaxations of permutation metrics is interesting in its own right. We show how our results imply that, in a certain sense we make precise, ℓ ₂² spreading metrics approximate permutation metrics on n points to a factor of O(?{logn}loglogn)O(\sqrt{\log n}\log\log n) .     

Improved Approximation Algorithm for Convex Recoloring of Trees

A pair (T,C) of a tree T and a coloring C is called a colored tree. Given a colored tree (T,C) any coloring C′ of T is called a recoloring of T. Given a weight function on the vertices of the tree the recoloring distance of a recoloring is the total weight of recolored vertices. A coloring of a tree is convex if for any two vertices u and v that are colored by the same color c, every vertex on the path from u to v is also colored by c. In the minimum convex recoloring problem we are given a colored tree and a weight function and our goal is to find a convex recoloring of minimum recoloring distance. The minimum convex recoloring problem naturally arises in the context of phylogenetic trees. Given a set of related species the goal of phylogenetic reconstruction is to construct a tree that would best describe the evolution of this set of species. In this context a convex coloring corresponds to perfect phylogeny. Since perfect phylogeny is not always possible the next best thing is to find a tree which is as close to convex as possible, or, in other words, a tree with minimum recoloring distance. We present a (2+ε)-approximation algorithm for the minimum convex recoloring problem, whose running time is O(n ²+n(1/ε)²4^1/ε ). This result improves the previously known 3-approximation algorithm for this NP-hard problem. We also present an algorithm for computing an optimal convex recoloring whose running time is , where n ^* is the number of colors that violate convexity in the input tree, and Δ is the maximum degree of vertices in the tree. The parameterized complexity of this algorithm is O(n ²+n⋅k⋅2 ^k ).     

On Constrained Facility Location Problems

Given m facilities each with an opening cost, n demands, and distance between every demand and facility, the Facility Location problem finds a solution which opens some facilities to connect every demand to an opened facility such that the total cost of the solution is minimized. The k-Facility Location problem further requires that the number of opened facilities is at most k, where k is a parameter given in the instance of the problem. We consider the Facility Location problems satisfying that for every demand the ratio of the longest distance to facilities and the shortest distance to facilities is at most ω, where ω is a predefined constant. Using the local search approach with scaling technique and error control technique, for any arbitrarily small constant > 0, we give a polynomial-time approximation algorithm for the ω-constrained Facility Location problem with approximation ratio 1 + ω + 1 + ε, which significantly improves the previous best known ratio (ω + 1)/α for some 1≤α≤2, and a polynomial-time approximation algorithm for the ω-constrained k- Facility Location problem with approximation ratio ω+1+ε. On the aspect of approximation hardness, we prove that unless NP■DTIME(nO(loglogn)), the ω-constrained Facility Location problem cannot be approximated within 1 + lnω - 1, which slightly improves the previous best known hardness result 1.243 + 0.316ln(ω - 1). The experimental results on the standard test instances of Facility Location problem show that our algorithm also has good performance in practice.     

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.     

d-Dimensional Range Search on Multicomputers

The range tree is a fundamental data structure for multidimensional point sets, and, as such, is central in a wide range of geometric and database applications. In this paper we describe the first nontrivial adaptation of range trees to the parallel distributed memory setting (BSP-like models). Given a set of n points in d -dimensional Cartesian space, we show how to construct on a coarse-grained multicomputer a distributed range tree T in time O( s / p + T _c (s,p)) , where s = n log ^d-1 n is the size of the sequential data structure and T _c (s,p) is the time to perform an h -relation with h=Θ (s/p) . We then show how T can be used to answer a given set Q of m=O(n) range queries in time O((s log m)/p + T _c (s,p)) and O((s log m)/p + T _c (s,p) + k/p) , where k is the number of results to be reported. These parallel construction and search algorithms are both highly efficient, in that their running times are the sequential time divided by the number of processors, plus a constant number of parallel communication rounds. Received June 1, 1997; revised March 10, 1998.     

Near-Entropy Hotlink Assignments

Consider a rooted tree T of arbitrary maximum degree d representing a collection of n web pages connected via a set of links, all reachable from a source home page represented by the root of T. Each web page i carries a probability p _i representative of the frequency with which it is visited. By adding hotlinks—shortcuts from a node to one of its descendents—we wish to minimize the expected number of steps l needed to visit pages from the home page, expressed as a function of the entropy H(p) of the access probabilities p. This paper introduces several new strategies for effectively assigning hotlinks in a tree. For assigning exactly one hotlink per node, our method guarantees an upper bound on l of 1.141H(p)+1 if d>2 and 1.08H(p)+2/3 if d=2. We also present the first efficient general methods for assigning at most k hotlinks per node in trees of arbitrary maximum degree, achieving bounds on l of at most \frac2H(p)log(k+1)+1\frac{2H(p)}{\log(k+1)}+1 and \fracH(p)log(k+d)-logd+1\frac{H(p)}{\log(k+d)-\log d}+1 , respectively. All our methods are strong, i.e., they provide the same guarantees on all subtrees after the assignment. We also present an algorithm implementing these methods in O(nlog n) time, an improvement over the previous O(n ²) time algorithms. Finally we prove a Ω(nlog n) lower bound on the running time of any strong method that guarantee an average access time strictly better than 2H(p).     

Approximate Pattern Matching with the <Emphasis Type="Italic">L</Emphasis><Subscript>1</Subscript>, <Emphasis Type="Italic">L</Emphasis><Subscript>2</Subscript> and <Emphasis Type="Italic">L</Emphasis><Subscript>∞</Subscript> Metrics

Given an alphabet Σ={1,2,…,|Σ|} text string T∈Σ ⁿ and a pattern string P∈Σ ^m , for each i=1,2,…,n−m+1 define L _p (i) as the p-norm distance when the pattern is aligned below the text and starts at position i of the text. The problem of pattern matching with L _p distance is to compute L _p (i) for every i=1,2,…,n−m+1. We discuss the problem for d=1,2,∞. First, in the case of L ₁ matching (pattern matching with an L ₁ distance) we show a reduction of the string matching with mismatches problem to the L ₁ matching problem and we present an algorithm that approximates the L ₁ matching up to a factor of 1+ε, which has an O(\frac1e²nlogmlog|S|)O(\frac{1}{\varepsilon^{2}}n\log m\log|\Sigma|) run time. Then, the L ₂ matching problem (pattern matching with an L ₂ distance) is solved with a simple O(nlog m) time algorithm. Finally, we provide an algorithm that approximates the L _∞ matching up to a factor of 1+ε with a run time of O(\frac1enlogmlog|S|)O(\frac{1}{\varepsilon}n\log m\log|\Sigma|) . We also generalize the problem of String Matching with mismatches to have weighted mismatches and present an O(nlog ⁴ m) algorithm that approximates the results of this problem up to a factor of O(log m) in the case that the weight function is a metric.     

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.     

An O(n log n) Average Time Algorithm for Computing the Shortest Network under a Given Topology

In 1992 F. K. Hwang and J. F. Weng published an O(n ² ) time algorithm for computing the shortest network under a given full Steiner topology interconnecting n fixed points in the Euclidean plane. The Hwang—Weng algorithm can be used to improve substantially existing algorithms for the Steiner minimum tree problem because it reduces the number of different Steiner topologies to be considered dramatically. In this paper we present an improved Hwang—Weng algorithm. While the worst-case time complexity of our algorithm is still O(n ² ) , its average time complexity over all the full Steiner topologies interconnecting n fixed points is O (n log n ). Received August 24, 1996; revised February 10, 1997.     

Finding the k Shortest Paths in Parallel

A concurrent-read exclusive-write PRAM algorithm is developed to find the k shortest paths between pairs of vertices in an edge-weighted directed graph. Repetitions of vertices along the paths are allowed. The algorithm computes an implicit representation of the k shortest paths to a given destination vertex from every vertex of a graph with n vertices and m edges, using O(m+nk log ² k) work and O( log^3k log ^*k+ log n( log log k+ log ^*n)) time, assuming that a shortest path tree rooted at the destination is pre-computed. The paths themselves can be extracted from the implicit representation in O( log k + log n) time, and O(n log n +L) work, where L is the total length of the output. Received July 2, 1997; revised June 18, 1998.     

Fault-Tolerant Real-Time Scheduling

We use competitive analysis to study how best to use redundancy to achieve fault-tolerance in online real-time scheduling. We show that the optimal way to use spatial redundancy depends on a complex interaction of the benefits, execution times, release times, and latest start times of the jobs. We give a randomized online algorithm whose competitive ratio is O( logΦ log Delta ( log ² n log m/ log log m)) for transient faults. Here n is the number of jobs, m is the number of processors, Φ is the ratio of the maximum value density of a job to the minimum value density of a job, and Δ is the ratio of the longest possible execution time to the shortest possible execution time. We show that this bound is close to optimal by giving an Ω(( log ΔΦ/ log log m) ( log m log log m) ² ) lower bound on the competitive ratio of any randomized algorithm. In the case of permanent faults, there is a randomized online algorithm that has a competitive ratio of O( log Phi log Δ (log m/log log m)). We also show a lower bound of Ω((log ΔΦ/ log log m) ( log m/log log m)) on the competitive ratio for interval scheduling with permanent faults. Received October 1997; revised January 1999.     

Sub-Constant Error Probabilistically Checkable Proof of Almost-Linear Size

We show a construction of a PCP with both sub-constant error and almost-linear size. Specifically, for some constant 0 < α < 1, we construct a PCP verifier for checking satisfiability of Boolean formulas that on input of size n uses log n+O((log n)^1-a)\log\, n+O((\log\, n)^{1-\alpha}) random bits to make 7 queries to a proof of size n·2^{O((log n)1-a)}n·2^{O((\log\, n)^{1-\alpha})}, where each query is answered by O((log n)^1-a)O((\log\, n)^{1-\alpha}) bit long string, and the verifier has perfect completeness and error 2^{-W((log n)a)}2^{-\Omega((\log\, n)^{\alpha})}.     

Exact and Approximation Algorithms for Clustering

In this paper we present an n^ O(k ^1-1/d ) -time algorithm for solving the k -center problem in \reals ^d , under L _∈ fty - and L ₂ -metrics. The algorithm extends to other metrics, and to the discrete k -center problem. We also describe a simple (1+ɛ) -approximation algorithm for the k -center problem, with running time O(nlog k) + (k/ɛ)^ O(k ^1-1/d ) . Finally, we present an n^ O(k ^1-1/d ) -time algorithm for solving the L -capacitated k -center problem, provided that L=Ω(n/k ^1-1/d ) or L=O(1) . Received July 25, 2000; revised April 6, 2001.     

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.     

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.     

Deterministic Broadcast and Gossiping Algorithms for Ad hoc Networks

We present in this paper three deterministic broadcast and a gossiping algorithm suitable for ad hoc networks where topology changes range from infrequent to very frequent. The proposed algorithms are designed to work in networks where the mobile nodes possessing collision detection capabilities. Our first broadcast algorithm accomplishes broadcast in O(nlog n) for networks where topology changes are infrequent. We also present an O(nlog n) worst case time broadcast algorithms that is resilient to mobility. For networks where topology changes are frequent, we present a third algorithm that accomplishes broadcast in O(Δ·nlog n + n·|M|) in the worst case scenario, where |M| is the length of the message to be broadcasted and Δ the maximum node degree. We then extend one of our broadcast algorithms to develop an O(Dn log n + D²) algorithm for gossiping in the same network model.     

Sample Spaces with Small Bias on Neighborhoods and Error-Correcting Communication Protocols

We give a deterministic algorithm which, on input an integer n , collection \cal F of subsets of {1,2,\ldots,n} , and ɛ∈ (0,1) , runs in time polynomial in n| \cal F |/ɛ and produces a \pm 1 -matrix M with n columns and m=O(log | \cal F |/ɛ ² ) rows with the following property: for any subset F ∈ \cal F , the fraction of 1's in the n -vector obtained by coordinatewise multiplication of the column vectors indexed by F is between (1-ɛ)/2 and (1+ɛ)/2 . In the case that \cal F is the set of all subsets of size at most k , k constant, this gives a polynomial time construction for a k -wise ɛ -biased sample space of size O(log n/ɛ ² ) , compared with the best previous constructions in [NN] and [AGHP] which were, respectively, O(log n/ɛ ⁴ ) and O(log ² n/ɛ ² ) . The number of rows in the construction matches the upper bound given by the probabilistic existence argument. Such constructions are of interest for derandomizing algorithms. As an application, we present a family of essentially optimal deterministic communication protocols for the problem of checking the consistency of two files. Received October 30, 1997; revised September 17, 1999, and April 17, 2000.