A note on maximum independent sets in rectangle intersection graphs

Finding the maximum independent set in the intersection graph of n axis-parallel rectangles is NP-hard. We re-examine two known approximation results for this problem. For the case of rectangles of unit height, Agarwal, van Kreveld and Suri [Comput. Geom. Theory Appl. 11 (1998) 209-218] gave a (1+1/k)-factor algorithm with an O(nlogn+n^2k−1) time bound for any integer constant k?1; we describe a similar algorithm running in only O(nlogn+nΔ^k−1) time, where Δ?n denotes the maximum number of rectangles a point can be in. For the general case, Berman, DasGupta, Muthukrishnan and Ramaswami [J. Algorithms 41 (2001) 443-470] gave a ⌈log_kn⌉-factor algorithm with an O(n^k+1) time bound for any integer constant k?2; we describe similar algorithms running in O(nlogn+nΔ^k−2) and n^O(k/logk) time.     

The prism machine: An alternative to the pyramid

The prism machine is a stack of n cellular arrays, each of size 2ⁿ × 2ⁿ. Cell (i, j) on level k is connected to cells (i, j), (i + 2^k, j), and (i, j + 2^k) on level k + 1, 1 ≤ k < n, where the sums are modulo 2ⁿ. Such a machine can perform various operations (e.g., “Gaussian” convolutions or least-squares polynomial fits) on image neighborhoods of power-of-2 sizes in every position in O(n) time, unlike a pyramid machine which can do this only in sampled positions. It can also compute the discrete Fourier transform in O(n) time. It consists of n · 4ⁿ cells, while a pyramid consists of fewer than 4ⁿ⁺¹/3 cells; but in practice n would be at most 10, so that a prism would be at most about seven times as large as a pyramid.     

Computing convexity properties of images on a pyramid computer

We present efficient parallel algorithms for using a pyramid computer to determine convexity properties of digitized black/white pictures and labeled figures. Algorithms are presented for deciding convexity, identifying extreme points of convex hulls, and using extreme points in a variety of fashions. For a pyramid computer with a base ofn simple processing elements arranged in ann ^1/2 ×n ^1/2 square, the running times of the algorithms range from Θ(logn) to find the extreme points of a convex figure in a digitized picture, to Θ(n ^1/6) to find the diameter of a labeled figure, Θ(n ^1/4 logn) to find the extreme points of every figure in a digitized picture, to Θ(n ^1/2) to find the extreme points of every labeled set of processing elements. Our results show that the pyramid computer can be used to obtain efficient solutions to nontrivial problems in image analysis. We also show the sensitivity of efficient pyramid-computer algorithms to the rate at which essential data can be compressed. Finally, we show that a wide variety of techniques are needed to make full and efficient use of the pyramid architecture.     

Parallel computation of disease transforms

Distance transforms are an important computational tool for the processing of binary images. For ann ×n image, distance transforms can be computed in time \(\mathcal{O}\) (n) on a mesh-connected computer and in polylogarithmic time on hypercube related structures. We investigate the possibilities of computing distance transforms in polylogarithmic time on the pyramid computer and the mesh of trees. For the pyramid, we obtain a polynomial lower bound using a result by Miller and Stout, so we turn our attention to the mesh of trees. We give a very simple \(\mathcal{O}\) (logn) algorithm for the distance transform with respect to theL ₁-metric, an \(\mathcal{O}\) (log² n) algorithm for the transform with respect to theL _∞-metric, and find that the Euclidean metric is much more difficult. Based on evidence from number theory, we conjecture the impossibility of computing the Euclidean distance transform in polylogarithmic time on a mesh of trees. Instead, we approximate the distance transform up to a given error. This works for anyL _k -metric and takes time \(\mathcal{O}\) (log³ n).     

A faster parameterized algorithm for set packing

We present an efficient parameterized algorithm for the (k,t)-set packing problem, in which we are looking for a collection of k disjoint sets whose union consists of t elements. The complexity of the algorithm is O(²O(t)nNlogN). For the special case of sets of bounded size, this improves the O(k(ck)n) algorithm of Jia et al. [J. Algorithms 50 (1) (2004) 106].     

Constant-time hough transform on the processor arrays with reconfigurable bus systems

We develop constant-time algorithms to compute the Hough transform on a processor array with a reconfigurable bus system (abbreviated to PARBS). The PARBS is a comptuation model which consists of a processor array and a reconfigurable bus system. It is a very powerful computation model in that many problems can be solved efficiently. In this paper, we introduce the concept of iterative-PARBS which is similar to the FOR-loop construct in sequential programming languages. The iterative-PARBS is a building block in which the processing data can be routed through it several times. We can think it as a “hardware subroutine”. Based on this scheme, we are able to explore constant-time Hough transform algorithms on PARBS. The following new results are derived in this study:

1. The sum ofn bits can be computed in O(1) times on a PARBS with O(n ^1+?) processors for any fixed ?>0.
2. The weights of each simple path of ann*n image can be computed in O(1) time on a 3-D PARBS with O(n ^2+?) processors for any fixed ?>0.
3. Thep angle Hough transform of ann*n image can be computed in O(1) time on a PARBS with O(p*n ^2+?) processors for any fixed ?>0 withp copies of the image pretiled.
4. Thep angle Hough transform of ann*n image can be computed in O(1) time on a PARBS with O(p*n ³) processors.

     

A posteriori error estimation for discontinuous Galerkin solutions of hyperbolic problems

We analyze the spatial discretization errors associated with solutions of one-dimensional hyperbolic conservation laws by discontinuous Galerkin methods (DGMs) in space. We show that the leading term of the spatial discretization error with piecewise polynomial approximations of degree p is proportional to a Radau polynomial of degree p+1 on each element. We also prove that the local and global discretization errors are O(Δx^2(p+1)) and O(Δx^2p+1) at the downwind point of each element. This strong superconvergence enables us to show that local and global discretization errors converge as O(Δx^p+2) at the remaining roots of Radau polynomial of degree p+1 on each element. Convergence of local and global discretization errors to the Radau polynomial of degree p+1 also holds for smooth solutions as p→∞. These results are used to construct asymptotically correct a posteriori estimates of spatial discretization errors that are effective for linear and nonlinear conservation laws in regions where solutions are smooth.     

Scheduling imprecise computation tasks on uniform processors

We consider the problem of preemptively scheduling n imprecise computation tasks on m?1 uniform processors, with each task Ti having two weights wi and . Three objectives are considered: (1) minimizing the maximum w^′-weighted error; (2) minimizing the total w-weighted error subject to the constraint that the maximum w^′-weighted error is minimized; (3) minimizing the maximum w^′-weighted error subject to the constraint that the total w-weighted error is minimized. For these objectives, we give polynomial time algorithms with time complexity O(mn⁴), O(mn⁴) and O(kmn⁴), respectively, where k is the number of distinct w-weights. We also present alternative algorithms for the three objectives, with time complexity O(cmn³), O(cmn³+mn⁴) and O(kcmn³), respectively, where c is a parameter-dependent number.     

Improved Algorithms for Constructing Fault-Tolerant Spanners

Let S be a set of n points in a metric space, and let k be a positive integer. Algorithms are given that construct k -fault-tolerant spanners for S . If in such a spanner at most k vertices and/ or edges are removed, then each pair of points in the remaining graph is still connected by a ``short'' path. First, an algorithm is given that transforms an arbitrary spanner into a k -fault-tolerant spanner. For the Euclidean metric in R ^d , this leads to an O(n log n + c ^k n) -time algorithm that constructs a k -fault-tolerant spanner of degree O(c ^k ) , whose total edge length is O(c ^k ) times the weight of a minimum spanning tree of S , for some constant c . For constant values of k , this result is optimal. In the second part of the paper, algorithms are presented for the Euclidean metric in R ^d . These algorithms construct (i) in O(n log n + k ² n) time, a k -fault-tolerant spanner with O(k ² n) edges, and (ii) in O(k n log n) time, such a spanner with O(k n log n) edges.     

An improved algorithm for the maximum agreement subtree problem

In this paper, we solve the maximum agreement subtree problem for a set T of k rooted leaf-labeled evolutionary trees on n leaves where T contains a binary tree. We show that the O(kn³)-time dynamic-programming algorithm proposed by Bryant [Building trees, hunting for trees, and comparing trees: theory and methods in phylogenetic analysis, Ph.D. thesis, Dept. Math., University of Canterbury, 1997, pp. 174-182] can be implemented in O(kn²+n²logk−2nloglogn) and O(kn3−1/(k−1)) time by using multidimensional range search related data structures proposed by Gabow et al. [Scaling and related techniques for geometry problems, in: Proc. 16th Annual ACM Symp. on Theory of Computing, 1984, pp. 135-143] and Bentley [Multidimensional binary search trees in database applications, IEEE Trans. Softw. Eng. SE-5 (4) (1979) 333-340], respectively. When k<2+(logn−logloglogn)/(loglogn), the first implementation will be significantly faster than Bryant's algorithm. For k=3, it yields the best known algorithm which runs in O(n²lognloglogn)-time.     

On constructing the relative neighborhood graphs in EuclideanK-dimensional spaces

In this paper, a new algorithm for constructing the relative neighborhood graph(RNG) of ann points set in Euclideank-dimensional space is presented, for fixedk≥3. The worst case running time of the algorithm isO(n ^2?a(k) (logn)^1?a(k) ), fora(k)=2^?(k+1), which is under the assumption that no three input points form an isosceles triangle. Previous algorithms needO(n ²) time. Our algorithm proceeds in two phases. First, a supergraph ofRNG withO(n) edges is constructed and then those edges which do not belong toRNG are eliminated.     

A deterministic (2−2/(k+1))n algorithm for k-SAT based on local search

Local search is widely used for solving the propositional satisfiability problem. Papadimitriou (1991) showed that randomized local search solves 2-SAT in polynomial time. Recently, Schöning (1999) proved that a close algorithm for k-SAT takes time (2−2/k)ⁿ up to a polynomial factor. This is the best known worst-case upper bound for randomized 3-SAT algorithms (cf. also recent preprint by Schuler et al.).We describe a deterministic local search algorithm for k-SAT running in time (2−2/(k+1))ⁿ up to a polynomial factor. The key point of our algorithm is the use of covering codes instead of random choice of initial assignments. Compared to other “weakly exponential” algorithms, our algorithm is technically quite simple. We also describe an improved version of local search. For 3-SAT the improved algorithm runs in time 1.481ⁿ up to a polynomial factor. Our bounds are better than all previous bounds for deterministic k-SAT algorithms.     

Time-space trade-offs for compressed suffix arrays

Given a binary string of length n, we give a representation of its suffix array that takes O(nt(lgn)^1/t) bits of space such that given i,1?i?n, the ith entry in the suffix array of the string can be retrieved in O(t) time, for any parameter 1?t?lglgn. For t=lglgn, this gives a compressed suffix array representation of Grossi and Vitter [Proc. Symp. on Theory Comput., 2000, pp. 397-406]. For t=O(1/ε), this gives the best known (in terms of space) compressed suffix array representation with constant query time. From this representation one can construct a suffix tree structure for a text of length n, that uses o(nlgn) bits of space which can be used to find all the k occurrences of a given pattern of length m in O(m/lgn+k) time. No such structure was known earlier.     

Almost k-wise independence versus k-wise independence

We say that a distribution over {0,1}ⁿ is (ε,k)-wise independent if its restriction to every k coordinates results in a distribution that is ε-close to the uniform distribution. A natural question regarding (ε,k)-wise independent distributions is how close they are to some k-wise independent distribution. We show that there exist (ε,k)-wise independent distributions whose statistical distance is at least n^O(k)·ε from any k-wise independent distribution. In addition, we show that for any (ε,k)-wise independent distribution there exists some k-wise independent distribution, whose statistical distance is n^O(k)·ε.     

Two-way deterministic multi-weak-counter machines

In this paper, we consider two-way deterministic machines which have counters, each capable of storing any nonnegative integer, but not having the ability to detect empty counter, and which accept by final state. We call these machines two-way deterministic multi-weak-counter machines. Let 2NWC^(k) and 2DWC^(k) denote the classes of languages recognized by two-way nondeterministic and deterministic k-weak-counter machines, respectively. In particular, for k = 1, we denote the corresponding classes by 2NWC and 2DWC. The following results are shown: (1) 2DWC^(k) = 2DWCfork ?1. (2) A bounded language in 2DWC is a bounded semilinear language. (3) 2NWC ≠ 2DWC.     

Jebelean-Weber's algorithm without spurious factors

Tudor Jebelean and Ken Weber introduced an algorithm for finding (a,b)-pairs satisfying au+bv≡0 (mod k), with . It is based on Sorenson's “k-ary reduction”. This algorithm does not preserve the GCD and its related GCD algorithm has an O(n²) time bit complexity in the worst case. We present a modified version which avoids this problem. We show that a slightly modified GCD algorithm has an O(n²/logn) running time in the worst case, where n is the number of bits of the larger input.     

Preprocess, Set, Query!

Thorup and Zwick (J. ACM 52(1):1–24, 2005 and STOC’01) in their seminal work introduced the notion of distance oracles. Given an n-vertex weighted undirected graph with m edges, they show that for any integer k≥1 it is possible to preprocess the graph in $\tilde {O}(mn^{1/k})$ time and generate a compact data structure of size O(kn ^1+1/k ). For each pair of vertices, it is then possible to retrieve an estimated distance with multiplicative stretch 2k?1 in O(k) time. For k=2 this gives an oracle of O(n ^1.5) size that produces in constant time estimated distances with stretch 3. Recently, Pǎtra?cu and Roditty (In: Proc. of 51st FOCS, 2010) broke the theoretical status-quo in the field of distance oracles and obtained a distance oracle for sparse unweighted graphs of O(n ^5/3) size that produces in constant time estimated distances with stretch 2. In this paper we show that it is possible to break the stretch 2 barrier at the price of non-constant query time in unweighted undirected graphs. We present a data structure that produces estimated distances with 1+ε stretch. The size of the data structure is O(nm ^1?ε′) and the query time is $\tilde {O}(m^{1-\varepsilon '})$ . Using it for sparse unweighted graphs we can get a data structure of size O(n ^1.87) that can supply in O(n ^0.87) time estimated distances with multiplicative stretch 1.75.     

Smallest k-point enclosing rectangle and square of arbitrary orientation

Given a set of n points in 2D, the problem of identifying the smallest rectangle of arbitrary orientation, and containing exactly k(?n) points is studied in this paper. The worst case time and space complexities of the proposed algorithm are O(n²logn+nk(n−k)(n−k+logk)) and O(n), respectively. The algorithm is then used to identify the smallest square of arbitrary orientation, and containing exactly k points in O(n²logn+kn²(n−k)logn) time.     

Improved deterministic algorithms for weighted matching and packing problems

Based on the method of (n,k)-universal sets, we present a deterministic parameterized algorithm for the weighted rd-matching problem with time complexity O^∗(4^{(r−1)k+o(k)}), improving the previous best upper bound O^∗(4^rk+o(k)). In particular, the algorithm applied to the unweighted 3d-matching problem results in a deterministic algorithm with time O^∗(16^k+o(k)), improving the previous best result O^∗(21.26^k). For the weighted r-set packing problem, we present a deterministic parameterized algorithm with time complexity O^∗(2^{(2r−1)k+o(k)}), improving the previous best result O^∗(2^2rk+o(k)). The algorithm, when applied to the unweighted 3-set packing problem, has running time O^∗(32^k+o(k)), improving the previous best result O^∗(43.62^k+o(k)). Moreover, for the weighted r-set packing and weighted rd-matching problems, we give a kernel of size O(k^r), which is the first kernelization algorithm for the problems on weighted versions.