Time Bounded Frequency Computations

(1) We obtain two new results concerning the inclusion problem of polynomial time frequency classes with equal numbers of errors. 1. (m, m+d) P(m+1, m+d+1) Pform<2^d. 2. (m, m+d) P=(m+1, m+d+1) Pformc(d) wherec(d) is large enough. This disproves a conjecture of Kinber. (2) We give a transparent proof of a generalization of Kinber's result that there exist arbitrarily complex problems admitting a polynomial time frequency computation. Several corollaries provide more insight into the structure of the hierarchy of polynomial time frequency classes. (3) The relationships between polynomial time frequency classes and selectivity classes are studied.     

Minimizing migrations in fair multiprocessor scheduling of persistent tasks

Suppose that we are given n persistent tasks (jobs) that need to be executed in an equitable way on m processors (machines). Each machine is capable of performing one unit of work in each integral time unit and each job may be executed on at most one machine at a time. The schedule needs to specify which job is to be executed on each machine in each time window. The goal is to find a schedule that minimizes job migrations between machines while guaranteeing a fair schedule. We measure the fairness by the drift d defined as the maximum difference between the execution times accumulated by any two jobs. As jobs are persistent we measure the quality of the schedule by the ratio of the number of migrations to time windows. We show a tradeoff between the drift and the number of migrations. Let n = qm + r with 0 < r < m (the problem is trivial for n ≤ m and for r = 0). For any d ≥ 1, we show a schedule that achieves a migration ratio less than r(m − r)/(n(q(d − 1)) + ∊ > 0; namely, it asymptotically requires r(m − r) job migrations every n(q(d − 1) + 1) time windows. We show how to implement the schedule efficiently. We prove that our algorithm is almost optimal by proving a lower bound of r(m − r)/(nqd) on the migration ratio. We also give a more complicated schedule that matches the lower bound for a special case when 2q ≤ d and m = 2r. Our algorithms can be extended to the dynamic case in which jobs enter and leave the system over time.     

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.     

On quorum systems for group resources allocation

We present a problem, called (n, m, k, d)-resource allocation, to model allocation of group resources with bounded capacity. Specifically, the problem concerns the scheduling of k identical resources among n processes which belong to m groups. Each resource can be used by at most d processes of the same group at a time, but no two processes of different groups can use a resource simultaneously. The problem captures two fundamental types of conflicts in mutual exclusion: k-exclusion’s amount constraint on the number of processes that can share a resource, and group mutual exclusion’s type constraint on the class of processes that can share a resource. We then study the problem in the message passing paradigm, and investigate quorum systems for the problem. We begin by establishing some basic and general results for quorum systems for the case of k = 1, based on which quorum systems for the general case can be understood and constructed. We found that the study of quorum systems for (n, m, 1, d)-resource allocation is related to some classical problems in combinatorics and in finite projective geometries. By applying the results there, we are able to obtain some optimal/near-optimal quorum systems.     

Orthogonal queries in segments

We consider theorthgonal clipping problem in a set of segments: Given a set ofn segments ind-dimensional space, we preprocess them into a data structure such that given an orthogonal query window, the segments intersecting it can be counted/reported efficiently. We show that the efficiency of the data structure significantly depends on a geometric discrete parameterK named theProjected-image complexity, which becomes Θ(n ²) in the worst case but practically much smaller. If we useO(m) space, whereK log^4d−7 n≥m≥n log^4d−7 n, the query time isO((K/m)^1/2 log^{max{4, 4d−5}} n). This is near to an Ω((K/m)^1/2) lower bound.     

Parallel algorithms for arrangements

We give the first efficient parallel algorithms for solving the arrangement problem. We give a deterministic algorithm for the CREW PRAM which runs in nearly optimal bounds ofO (logn log^* n) time andn ²/logn processors. We generalize this to obtain anO (logn log^* n)-time algorithm usingn ^d /logn processors for solving the problem ind dimensions. We also give a randomized algorithm for the EREW PRAM that constructs an arrangement ofn lines on-line, in which each insertion is done in optimalO (logn) time usingn/logn processors. Our algorithms develop new parallel data structures and new methods for traversing an arrangement.This work was supported by the National Science Foundation, under Grants CCR-8657562 and CCR-8858799, NSF/DARPA under Grant CCR-8907960, and Digital Equipment Corporation. A preliminary version of this paper appeared at the Second Annual ACM Symposium on Parallel Algorithms and Architectures [3].     

Near-Optimum Folding for a Reconfigurable Snake-Like Robot

To improve reachability of a snake-like robot depending on the problem, the links of the robot need to be resizable. In such a case folding links of the robot help to better plan obstacle avoidance. Optimum folding of the robot is the aim of our paper. We introduce a practical idea to construct reconfigurable and resizable snake robots which can be folded and an approximation algorithm to find near-optimum folding for the robot. Since an open chain is an abstract model of a snake-like robot, folding algorithms for the proposed robot are given in terms of an open chain. Ruler folding is a well-known NP-Complete problem. It considers folding of an n-link open chain linkage to the minimum length. The best previously known approximation algorithm for this problem has been developed by Hopcroft et al. They achieved the upper bound of 2m ₁ for the length of the folded chain in all cases, where m ₁ is the length of the longest link of the given chain. Already there are no any algorithms for open chain folding which guarante that the folded length of the open chain is less than 2m ₁. In this paper, we introduce an approximation algorithm which runs in O (n log n) using O (n) space. We introduce a function for the upper bound of the folded chain which depends to the lengths of all links in the given chain. Our experimental results show that for more than 95% of the problem instances we can achieve the same results in O (n) time. Using our folding algorithm, we can design the length of each link in an open chain to get x · m ₁ folded length where 1 < x < 2 is given and m ₁ is the length of the longest link of the chain. We introduce how to design a snake-like robot for which it can be folded in the given interval.     

Online Variable Sized Covering

We consider one-dimensional and multidimensional vector covering with variable sized bins. In the one-dimensional case, we consider variable sized bin covering with bounded item sizes. For every finite set of bins B, and upper bound 1/m on the size of items for some integer m, we define a ratio r(B, m). We prove this is the best possible competitive ratio for the set of bins B and the parameter m by giving both an algorithm with competitive ratio r(B, m) and an upper bound of r(B, m) on the competitive ratio of any online deterministic or randomized algorithm. The ratio satisfies r(B, m)≥m/(m+1) and equals this number if all bins are of size 1. For multidimensional vector covering we consider the case where each bin is a binary d-dimensional vector. It was shown by N. Alon, Y. Azar, J. Csirik, L. Epstein, S. V. Sevastianov, A. P. A. Vestjens, and G. J. Woeginger (1998, Algorithmica 21, 104–118) that if B contains a single bin which is all 1, then the best competitive ratio is Θ(1/d). We show an upper bound of 1/2^d(1−o(1)) for the general problem, and consider four special case variants. We show an algorithm with optimal competitive ratio 1/2 for the model where each bin in B is a standard basis vector. We consider the model where B consists of all unit prefix vectors. A unit prefix vector has i leftmost components of 1, and all other components are 0. We show that this model is harder than the case of standard basis vector bins by giving an upper bound of O(1/log d) on the competitive ratio of any deterministic or randomized algorithm. Next, we discuss the model where B contains all binary vectors. We show this model is easier than the model of one bin type which is all 1 by giving an algorithm with competitive ratio Ω(1/log d). The most interesting multidimensional case is d=2. The results of N. Alon et al. give a 0.25-competitive algorithm for B={(1, 1)} and an upper bound of 0.4 on the competitive ratio of any algorithm. In this paper we consider all other models for d=2. For standard basis vectors, we give an algorithm with optimal competitive ratio 1/2. For unit prefix vectors we give an upper bound of 4/9 on the competitive ratio of any deterministic or randomized algorithm. For the model where B consists of all binary vectors, we design an algorithm with ratio larger than 0.4. These results show that all above relations between models hold for d=2 as well.     

Complexity and Approximations for Multimessage Multicasting

We consider multimessage multicasting over thenprocessor complete (or fully connected) static network (MM_C). First we present a linear time algorithm that constructs for every degreedproblem instance a communication schedule with total communication time at mostd², wheredis the maximum number of messages that each processor may send or receive. Then we present degreedproblem instances such that all their communication schedules have total communication time at leastd². We observe that our lower bound applies when the fan-out (maximum number of processors receiving any given message) is huge, and thus the number of processors is also huge. Since this environment is not likely to arise in the near future, we turn our attention to the study of important subproblems that are likely to arise in practice. We show that when each message has fan-outk=1 theMM_Cproblem corresponds to the makespan openshop preemptive scheduling problem which can be solved in polynomial time and show that fork?2 our problem is NP-complete and remains NP-complete even when forwarding is allowed. We present an algorithm to generate a communication schedule with total communication time 2d−1 for any degreedproblem instance with fan-outk=2. Our main result is anO(q·d·e) time algorithm, wheree?nd(the input length), with an approximation bound ofqd+k^1/q(d−1), for any integerqsuch thatk>q?2. Our algorithms are centralized and require all the communication information ahead of time. Applications where all of this information is readily available include iterative algorithms for solving linear equations, and most dynamic programming procedures. The Meiko CS-2 machine and computer systems with processors communicating via dynamic permutation networks whose basic switches can act as data replicators (e.g.,nbynBenes network with 2 by 2 switches that can also act as data replicators) will also benefit from our results at the expense of doubling the number of communication phases.     

An Efficient Parallel Strategy for ComputingK-Terminal Reliability and Finding Most Vital Edges in 2-Trees and Partial 2-Trees

In this paper, we first develop a parallel algorithm for computingK-terminal reliability, denoted byR(G_K), in 2-trees. Based on this result, we can also computeR(G_K) in partial 2-trees using a method that transforms, in parallel, a given partial 2-tree into a 2-tree. Finally, we solve the problem of finding most vital edges with respect toK-terminal reliability in partial 2-trees. Our algorithms takeO(log n) time withC(m, n) processors on a CRCW PRAM, whereC(m, n) is the number of processors required to find the connected components of a graph withmedges andnvertices in logarithmic time.     

Data Mining with Sparse Grids

O (h _n ⁻¹ n ^{d −1}) instead of O(h _n ^−d ) grid points and unknowns are involved. Here d denotes the dimension of the feature space and h _n = 2 ⁻ⁿ gives the mesh size. To be precise, we suggest to use the sparse grid combination technique [42] where the classification problem is discretized and solved on a certain sequence of conventional grids with uniform mesh sizes in each coordinate direction. The sparse grid solution is then obtained from the solutions on these different grids by linear combination. In contrast to other sparse grid techniques, the combination method is simpler to use and can be parallelized in a natural and straightforward way. We describe the sparse grid combination technique for the classification problem in terms of the regularization network approach. We then give implementational details and discuss the complexity of the algorithm. It turns out that the method scales only linearly with the number of instances, i.e. the amount of data to be classified. Finally we report on the quality of the classifier built by our new method. Here we consider standard test problems from the UCI repository and problems with huge synthetical data sets in up to 9 dimensions. It turns out that our new method achieves correctness rates which are competitive to that of the best existing methods. Received April 25, 2001     

Efficient Algorithms for k-Terminal Cuts on Planar Graphs

The minimum k-terminal cut problem is of considerable theoretical interest and arises in several applied areas such as parallel and distributed computing, VLSI circuit design, and networking. In this paper we present two new approximation and exact algorithms for this problem on an n-vertex undirected weighted planar graph G. For the case when the k terminals are covered by the boundaries of m > 1 faces of G, we give a min{O(n ² log n logm), O(m ² n ^1.5 log² n + k n)} time algorithm with a (2–2/k)-approximation ratio (clearly, m \le k). For the case when all k terminals are covered by the boundary of one face of G, we give an O(n k3 + (n log n)k ²) time exact algorithm, or a linear time exact algorithm if k = 3, for computing an optimal k-terminal cut. Our algorithms are based on interesting observations and improve the previous algorithms when they are applied to planar graphs. To our best knowledge, no previous approximation algorithms specifically for solving the k-terminal cut problem on planar graphs were known before. The (2–2/k)-approximation algorithm of Dahlhaus et al. (for general graphs) takes O(k n ² log n) time when applied to planar graphs. Our approximation algorithm for planar graphs runs faster than that of Dahlhaus et al. by at least an O(k/logm) factor (m \le k).     

A Sequential Algorithm for Generating Random Graphs

We present a nearly-linear time algorithm for counting and randomly generating simple graphs with a given degree sequence in a certain range. For degree sequence (d _i ) _i=1 ⁿ with maximum degree d _max?=O(m ^1/4?τ ), our algorithm generates almost uniform random graphs with that degree sequence in time O(md _max?) where $m=\frac{1}{2}\sum_{i}d_{i}We present a nearly-linear time algorithm for counting and randomly generating simple graphs with a given degree sequence in a certain range. For degree sequence (d _i ) _i=1 ⁿ with maximum degree d _max=O(m ^1/4−τ ), our algorithm generates almost uniform random graphs with that degree sequence in time O(md _max) where m=\frac12?_id_im=\frac{1}{2}\sum_{i}d_{i} is the number of edges in the graph and τ is any positive constant. The fastest known algorithm for uniform generation of these graphs (McKay and Wormald in J. Algorithms 11(1):52–67, 1990) has a running time of O(m ² d _max²). Our method also gives an independent proof of McKay’s estimate (McKay in Ars Combinatoria A 19:15–25, 1985) for the number of such graphs.     

Efficient Algorithms for <Emphasis Type="Italic">k</Emphasis>-Terminal Cuts on Planar Graphs

The minimum k-terminal cut problem is of considerable theoretical interest and arises in several applied areas such as parallel and distributed computing, VLSI circuit design, and networking. In this paper we present two new approximation and exact algorithms for this problem on an n-vertex undirected weighted planar graph G. For the case when the k terminals are covered by the boundaries of m > 1 faces of G, we give a min{O(n ² log n logm), O(m ² n ^1.5 log² n + k n)} time algorithm with a (2–2/k)-approximation ratio (clearly, m \le k). For the case when all k terminals are covered by the boundary of one face of G, we give an O(n k3 + (n log n)k ²) time exact algorithm, or a linear time exact algorithm if k = 3, for computing an optimal k-terminal cut. Our algorithms are based on interesting observations and improve the previous algorithms when they are applied to planar graphs. To our best knowledge, no previous approximation algorithms specifically for solving the k-terminal cut problem on planar graphs were known before. The (2–2/k)-approximation algorithm of Dahlhaus et al. (for general graphs) takes O(k n ² log n) time when applied to planar graphs. Our approximation algorithm for planar graphs runs faster than that of Dahlhaus et al. by at least an O(k/logm) factor (m \le k).     

Quasi-optimal upper bounds for simplex range searching and new zone theorems

This paper presents quasi-optimal upper bounds for simplex range searching. The problem is to preprocess a setP ofn points in ?^d so that, given any query simplexq, the points inP ∩q can be counted or reported efficiently. Ifm units of storage are available (n <m <n ^d ), then we show that it is possible to answer any query inO(n ^1+?/m ^1/d ) query time afterO(m ^1+?) preprocessing. This bound, which holds on a RAM or a pointer machine, is almost tight. We also show how to achieveO(logn) query time at the expense ofO(n ^d+?) storage for any fixed ? > 0. To fine-tune our results in the reporting case we also establish new zone theorems for arrangements and merged arrangements of planes in 3-space, which are of independent interest.     

Implementing Shared Memory on Mesh-Connected Computers and on the Fat-Tree

We present deterministic upper and lower bounds on the slowdown required to simulate an (n, m)-PRAM on a variety of networks. The upper bounds are based on a novel scheme that exploits the splitting and combining of messages. This scheme can be implemented on an n-node d-dimensional mesh (for constant d) and on an n-leaf pruned butterfly and attains the smallest worst-case slowdown to date for such interconnections, namely, O(n^1/d(log(m/n))^1-1/d) for the d-dimensional mesh (with constant d) and O( ) for the pruned butterfly. In fact, the simulation on the pruned butterfly is the first PRAM simulation scheme on an area-universal network. Finally, we prove restricted and unrestricted lower bounds on the slowdown of any deterministic PRAM simulation on an arbitrary network, formulated in terms of the bandwidth properties of the interconnection as expressed by its decomposition tree.     

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.     

On Approximating Polygonal Curves in Two and Three Dimensions

Given a polygonal curve P =[p₁, p₂, . . . , p_n], the polygonal approximation problem considered calls for determining a new curve P′ = [p′₁, p′₂, . . . , p′_m] such that (i) m is significantly smaller than n, (ii) the vertices of P′ are an ordered subset of the vertices of P, and (iii) any line segment [p′_A, p′_{A + 1} of P′ that substitutes a chain [p_B, . . . , p_C] in P is such that for all i where B ≤ i ≤ C, the approximation error of p_i with respect to [p′_A, p′_{A + 1}], according to some specified criterion and metric, is less than a predetermined error tolerance. Using the parallel-strip error criterion, we study the following problems for a curve P in R^d, where d = 2, 3: (i) minimize m for a given error tolerance and (ii) given m, find the curve P′ that has the minimum approximation error over all curves that have at most m vertices. These problems are called the min-# and min-ϵ problems, respectively. For R² and with any one of the L₁, L₂, or L_∞ distance metrics, we give algorithms to solve the min-# problem in O(n²) time and the min-ϵ problem in O(n² log n) time, improving the best known algorithms to date by a factor of log n. When P is a polygonal curve in R³ that is strictly monotone with respect to one of the three axes, we show that if the L₁ and L_∞ metrics are used then the min-# problem can be solved in O(n²) time and the min-ϵ problem can be solved in O(n³) time. If distances are computed using the L₂ metric then the min-# and min-ϵ problems can be solved in O(n³) and O(n³ log n) time, respectively. All of our algorithms exhibit O(n²) space complexity. Finally, we show that if it is not essential to minimize m, simple modifications of our algorithms afford a reduction by a factor of n for both time and space.     

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.     

Asymptotically Optimal Solutions for Small World Graphs

We consider the problem of determining constructions with an asymptotically optimal oblivious diameter in small world graphs under the Kleinberg’s model. In particular, we give the first general lower bound holding for any monotone distance distribution, that is induced by a monotone generating function. Namely, we prove that the expected oblivious diameter is Ω(log ² n) even on a path of n nodes. We then focus on deterministic constructions and after showing that the problem of minimizing the oblivious diameter is generally intractable, we give asymptotically optimal solutions, that is with a logarithmic oblivious diameter, for paths, trees and Cartesian products of graphs, including d-dimensional grids for any fixed value of d. The research was partially funded by the European project COST Action 293, “Graphs and Algorithms in Communication Networks” (GRAAL).