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

Linear Time Algorithms for Exact Distance Transform

In 2003, Maurer et al. (IEEE Trans. Pattern Anal. Mach. Intell. 25:265–270, 2003) published a paper describing an algorithm that computes the exact distance transform in linear time (with respect to image size) for the rectangular binary images in the k-dimensional space ℝ ^k and distance measured with respect to L _p -metric for 1≤p≤∞, which includes Euclidean distance L ₂. In this paper we discuss this algorithm from theoretical and practical points of view. On the practical side, we concentrate on its Euclidean distance version, discuss the possible ways of implementing it as signed distance transform, and experimentally compare implemented algorithms. We also describe the parallelization of these algorithms and discuss the computational time savings associated with them. All these implementations will be made available as a part of the CAVASS software system developed and maintained in our group (Grevera et al. in J. Digit. Imaging 20:101–118, 2007). On the theoretical side, we prove that our version of the signed distance transform algorithm, GBDT, returns the exact value of the distance from the geometrically defined object boundary. We provide a complete proof (which was not given of Maurer et al. (IEEE Trans. Pattern Anal. Mach. Intell. 25:265–270, 2003) that all these algorithms work correctly for L _p -metric with 1<p<∞. We also point out that the precise form of the algorithm from Maurer et al. (IEEE Trans. Pattern Anal. Mach. Intell. 25:265–270, 2003) is not well defined for L ₁ and L _∞ metrics. In addition, we show that the algorithm can be used to find, in linear time, the exact value of the diameter of an object, that is, the largest possible distance between any two of its elements.     

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.     

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.     

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.     

Incremental Medians via Online Bidding

In the k-median problem we are given sets of facilities and customers, and distances between them. For a given set F of facilities, the cost of serving a customer u is the minimum distance between u and a facility in F. The goal is to find a set F of k facilities that minimizes the sum, over all customers, of their service costs. Following the work of Mettu and Plaxton, we study the incremental medians problem, where k is not known in advance. An incremental algorithm produces a nested sequence of facility sets F ₁⊆F ₂⊆⋅⋅⋅⊆F _n , where |F _k |=k for each k. Such an algorithm is called c -cost-competitive if the cost of each F _k is at most c times the optimum k-median cost. We give improved incremental algorithms for the metric version of this problem: an 8-cost-competitive deterministic algorithm, a 2e≈5.44-cost-competitive randomized algorithm, a (24+ε)-cost-competitive, polynomial-time deterministic algorithm, and a 6e+ε≈16.31-cost-competitive, polynomial-time randomized algorithm. We also consider the competitive ratio with respect to size. An algorithm is s -size-competitive if the cost of each F _k is at most the minimum cost of any set of k facilities, while the size of F _k is at most sk. We show that the optimal size-competitive ratios for this problem, in the deterministic and randomized cases, are 4 and e. For polynomial-time algorithms, we present the first polynomial-time O(log m)-size-approximation algorithm for the offline problem, as well as a polynomial-time O(log m)-size-competitive algorithm for the incremental problem. Our upper bound proofs reduce the incremental medians problem to the following online bidding problem: faced with some unknown threshold T∈ℝ⁺, an algorithm must submit “bids” b∈ℝ⁺ until it submits a bid b≥T, paying the sum of all its bids. We present folklore algorithms for online bidding and prove that they are optimally competitive. We extend some of the above results for incremental medians to approximately metric distance functions and to incremental fractional medians. Finally, we consider a restricted version of the incremental medians problem where k is restricted to one of two given values, for which we give a deterministic algorithm with a nearly optimal cost-competitive ratio. The conference version of this paper appeared in (Chrobak, M., et al. in Lecture Notes in Computer Science, vol. 3887, pp. 311–322, 2006). Research of M. Chrobak supported by NSF Grant CCR-0208856.     

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 ℝ⁷.     

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.     

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.     

Grade of Service Steiner Minimum Trees in the Euclidean Plane

Abstract. Let P = {p ₁ , p ₂ , \ldots, p _n } be a set of n {\lilsf terminal points} in the Euclidean plane, where point p _i has a {\lilsf service request of grade} g(p _i ) ∈ {1, 2, \ldots, n} . Let 0 < c(1) < c(2) < ⋅s < c(n) be n real numbers. The {\lilsf Grade of Service Steiner Minimum Tree (GOSST)} problem asks for a minimum cost network interconnecting point set P and some {\lilsf Steiner points} with a service request of grade 0 such that (1) between each pair of terminal points p _i and p _j there is a path whose minimum grade of service is at least as large as \min(g(p _i ), g(p _j )) ; and (2) the cost of the network is minimum among all interconnecting networks satisfying (1), where the cost of an edge with service of grade g is the product of the Euclidean length of the edge with c(g) . The GOSST problem is a generalization of the Euclidean Steiner minimum tree problem where all terminal points have the same grade of service request. When there are only two (three, respectively) different grades of service request by the terminal points, we present a polynomial time approximation algorithm with performance ratio \frac 4 3 ρ (((5+4\sqrt 2 )/7)ρ , respectively), where ρ is the performance ratio achieved by an approximation algorithm for the Euclidean Steiner minimum tree problem. For the general case, we prove that there exists a GOSST that is the minimum cost network under a full Steiner topology or its degeneracies. A powerful interior-point algorithm is used to find a (1+ε) -approximation to the minimum cost network under a given topology or its degeneracies in O(n ^1.5 (log n + log (1/ε))) time. We also prove a lower bound theorem which enables effective pruning in a branch-and-bound method that partially enumerates the full Steiner topologies in search for a GOSST. We then present a k -optimal heuristic algorithm to compute good solutions when the problem size is too large for the branch-and-bound algorithm. Preliminary computational results are presented.     

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.     

Parallel merging with restriction

In this paper, we study the merging of two sorted arrays and on EREW PRAM with two restrictions: (1) The elements of two arrays are taken from the integer range [1,n], where n=Max(n ₁,n ₂). (2) The elements are taken from either uniform distribution or non-uniform distribution such that , for 1≤i≤p (number of processors). We give a new optimal deterministic algorithm runs in time using p processors on EREW PRAM. For ; the running time of the algorithm is O(log ^(g) n) which is faster than the previous results, where log ^(g) n=log log ^(g−1) n for g>1 and log ⁽¹⁾ n=log n. We also extend the domain of input data to [1,n ^k ], where k is a constant.

Chordal Deletion is Fixed-Parameter Tractable

It is known to be NP-hard to decide whether a graph can be made chordal by the deletion of k vertices or by the deletion of k edges. Here we present a uniformly polynomial-time algorithm for both problems: the running time is f(k)⋅n ^α for some constant α not depending on k and some f depending only on k. For large values of n, such an algorithm is much better than trying all the O(n ^k ) possibilities. Therefore, the chordal deletion problem parameterized by the number k of vertices or edges to be deleted is fixed-parameter tractable. This answers an open question of Cai (Discrete Appl. Math. 127:415–429, 2003).     

Approximation Algorithms for Requirement Cut on Graphs

In this paper, we unify several graph partitioning problems including multicut, multiway cut, and k-cut, into a single problem. The input to the requirement cut problem is an undirected edge-weighted graph G=(V,E), and g groups of vertices X ₁,…,X _g ⊆V, with each group X _i having a requirement r _i between 0 and |X _i |. The goal is to find a minimum cost set of edges whose removal separates each group X _i into at least r _i disconnected components. We give an O(log n⋅log (gR)) approximation algorithm for the requirement cut problem, where n is the total number of vertices, g is the number of groups, and R is the maximum requirement. We also show that the integrality gap of a natural LP relaxation for this problem is bounded by O(log n⋅log (gR)). On trees, we obtain an improved guarantee of O(log (gR)). There is an Ω(log g) hardness of approximation for the requirement cut problem, even on trees.     

A randomized clustering of anonymous wireless ad hoc networks with an application to the initialization problem

The Distributed Mobility-Adaptive Clustering (DMAC) due to Basagni partitions the nodes of a mobile ad hoc network into clusters, thus giving the network a hierarchical organization. This algorithm supports the mobility of the nodes, even during the cluster formation. The main feature of DMAC is that in a weighted network (in which two or more nodes cannot have the same weight), nodes have to choose the clusterheads taking into account only the node weight, i.e. the mobility when a node weight is the inverse of its speed. In our approach many nodes may have the same speed and hence the same weight. We assume that nodes have no identities and the number of nodes, say n, is the only known parameter of the network. After the randomized clustering, we show that the initialization problem can be solved in a multi-hop ad hoc wireless network of n stations in O(k ^1/2log ^1/2 k)+D _b −1+O(log (max (P _i )+log ²max (P _i )) broadcast rounds with high probability, where k is the number of clusters, D _b is the blocking diameter and max (P _i ), 1≤i≤k, is the maximum number of nodes in a cluster. Thus the initialization protocol presented here uses less broadcast rounds than the one in Ravelemanana (IEEE Trans. Parallel Distributed Syst. 18(1):17–28 2007).     

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     

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

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.     

On Space Efficient Two Dimensional Range Minimum Data Structures

The two dimensional range minimum query problem is to preprocess a static m by n matrix (two dimensional array) A of size N=m⋅n, such that subsequent queries, asking for the position of the minimum element in a rectangular range within A, can be answered efficiently. We study the trade-off between the space and query time of the problem. We show that every algorithm enabled to access A during the query and using a data structure of size O(N/c) bits requires Ω(c) query time, for any c where 1≤c≤N. This lower bound holds for arrays of any dimension. In particular, for the one dimensional version of the problem, the lower bound is tight up to a constant factor. In two dimensions, we complement the lower bound with an indexing data structure of size O(N/c) bits which can be preprocessed in O(N) time to support O(clog ² c) query time. For c=O(1), this is the first O(1) query time algorithm using a data structure of optimal size O(N) bits. For the case where queries can not probe A, we give a data structure of size O(N⋅min {m,log n}) bits with O(1) query time, assuming m≤n. This leaves a gap to the space lower bound of Ω(Nlog m) bits for this version of the problem.     

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.