Sorting and Searching in Faulty Memories

In this paper we investigate the design and analysis of algorithms resilient to memory faults. We focus on algorithms that, despite the corruption of some memory values during their execution, are nevertheless able to produce a correct output at least on the set of uncorrupted values. In this framework, we consider two fundamental problems: sorting and searching. In particular, we prove that any O(nlog n) comparison-based sorting algorithm can tolerate the corruption of at most O((nlog n)^1/2) keys. Furthermore, we present one comparison-based sorting algorithm with optimal space and running time that is resilient to O((nlog n)^1/3) memory faults. We also prove polylogarithmic lower and upper bounds on resilient searching. This work has been partially supported by the Sixth Framework Programme of the EU under Contract Number 507613 (Network of Excellence “EuroNGI: Designing and Engineering of the Next Generation Internet”) and by MIUR, the Italian Ministry of Education, University and Research, under Project ALGO-NEXT (“Algorithms for the Next Generation Internet and Web: Methodologies, Design and Experiments”). A preliminary version of this work was presented at the 36th ACM Symposium on Theory of Computing (STOC’04) .     

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     

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.     

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})}.     

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.     

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.     

Strong-Diameter Decompositions of Minor Free Graphs

We provide the first sparse covers and probabilistic partitions for graphs excluding a fixed minor that have strong diameter bounds; i.e. each set of the cover/partition has a small diameter as an induced sub-graph. Using these results we provide improved distributed name-independent routing schemes. Specifically, given a graph excluding a minor on r vertices and a parameter ρ>0 we obtain the following results: (1) a polynomial algorithm that constructs a set of clusters such that each cluster has a strong-diameter of O(r ² ρ) and each vertex belongs to 2 ^O(r) r! clusters; (2) a name-independent routing scheme with a stretch of O(r ²), headers of O(log n+rlog r) bits, and tables of size 2 ^O(r) r! log ⁴ n/log log n bits; (3) a randomized algorithm that partitions the graph such that each cluster has strong-diameter O(r6 ^r ρ) and the probability an edge (u,v) is cut is O(r  d(u,v)/ρ).     

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:

An Efficient Algorithm for Batch Stability Testing

Given a stable marriage problem instance represented by a bipartite graph having 2n vertices and m edges, we describe an algorithm that can verify the stability of k different matchings in a batch fashion in O((m+kn)log ² n) time. This affirmatively answers a longstanding open question of Gusfield and Irving as to whether stability can be verified in a batch setting (after sufficient preprocessing) in time sub-quadratic in n.     

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.     

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.     

Combining Markov-Chain Analysis and Drift Analysis

In their seminal article Droste, Jansen, and Wegener (Theor. Comput. Sci. 276:51–82, 2002) consider a basic direct-search heuristic with a global search operator, namely the so-called (1+1) Evolutionary Algorithm ((1+1) EA). They present the first theoretical analysis of the (1+1) EA’s expected runtime for the class of linear functions over the search space {0,1} ⁿ . In a rather long and involved proof they show that, for any linear function, the expected runtime is O(nlog n), i.e., that there are two constants c and n′ such that, for n≥n′, the expected number of iterations until a global optimum is generated is bounded above by c⋅nlog ₂ n. However, neither c nor n′ are specified—they would be pretty large. Here we reconsider this optimization scenario to demonstrate the potential of an analytical method that makes use of the distribution of the evolving candidate solution over the search space {0,1} ⁿ . Actually, an invariance property of this distribution is proved, which is then used to obtain a significantly improved bound on the drift, namely the expected change of a potential function, here the number of bits set correctly. Finally, this better estimate of the drift enables an upper bound on the expected number of iterations of 3.8nlog ₂ n+7.6log ₂ n for n≥2.     

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.     

Fitting a Step Function to a Point Set

We consider the problem of fitting a step function to a set of points. More precisely, given an integer k and a set P of n points in the plane, our goal is to find a step function f with k steps that minimizes the maximum vertical distance between f and all the points in P. We first give an optimal Θ(nlog n) algorithm for the general case. In the special case where the points in P are given in sorted order according to their x-coordinates, we give an optimal Θ(n) time algorithm. Then, we show how to solve the weighted version of this problem in time O(nlog ⁴ n). Finally, we give an O(nh ²log n) algorithm for the case where h outliers are allowed. The running time of all our algorithms is independent of k.     

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.     

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.     

Approximating the Bandwidth of Caterpillars

A caterpillar is a tree in which all vertices of degree three or more lie on one path, called the backbone. We present a polynomial time algorithm that produces a linear arrangement of the vertices of a caterpillar with bandwidth at most O(log n/log log n) times the local density of the caterpillar, where the local density is a well known lower bound on the bandwidth. This result is best possible in the sense that there are caterpillars whose bandwidth is larger than their local density by a factor of Ω(log n/log log n). The previous best approximation ratio for the bandwidth of caterpillars was O(log n). We show that any further improvement in the approximation ratio would require using linear arrangements that do not respect the order of the vertices of the backbone. We also show how to obtain a (1+ε) approximation for the bandwidth of caterpillars in time . This result generalizes to trees, planar graphs, and any family of graphs with treewidth .     

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.     

Universal routing schemes

Summary.  In this paper, we deal with the compact routing problem, that is implementing routing schemes that use a minimum memory size on each router. A universal routing scheme is a scheme that applies to all n-node networks. In [31], Peleg and Upfal showed that one cannot implement a universal routing scheme with less than a total of Ω(n ^1+1/(2s+4)) memory bits for any given stretch factor s≧1. We improve this bound for stretch factors s, 1≦s<2, by proving that any near-shortest path universal routing scheme uses a total of Ω(n ²) memory bits in the worst-case. This result is obtained by counting the minimum number of routing functions necessary to route on all n-node networks. Moreover, and more fundamentally, we give a tight bound of Θ(n log n) bits for the local minimum memory requirement of universal routing scheme of stretch factors s, 1≦s<2. More precisely, for any fixed constant ɛ, 0<ɛ<1, there exists a n-node network G on which at least Ω(n ^ɛ) routers require Θ(n log n) bits each to code any routing function on G of stretch factor <2. This means that, whatever you choose the routing scheme, there exists a network on which one cannot compress locally the routing information better than routing tables do. Received: August 1995 / Accepted: August 1996