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

Approximate Range Searching in External Memory

In this paper, we present two linear-size external memory data structures for approximate range searching. Our first structure, the BAR-B-tree, stores a set of N points in ℝ ^d and can report all points inside a query range Q by accessing O(log  _B N+ε ^γ +k _ε /B) disk blocks, where B is the disk block size, γ=1−d for convex queries and γ=−d otherwise, and k _ε is the number of points lying within a distance of ε⋅diam (Q) to the query range Q. Our second structure, the object-BAR-B-tree, is able to store objects of arbitrary shapes of constant complexity and provides similar query guarantees. In addition, both structures can support other types of range searching queries such as range aggregation and nearest-neighbor. Finally, we present I/O-efficient algorithms to build these structures.     

Analysis of Galerkin Methods for the Fully Nonlinear Monge-Ampère Equation

This paper develops and analyzes finite element Galerkin and spectral Galerkin methods for approximating viscosity solutions of the fully nonlinear Monge-Ampère equation det (D ² u ⁰)=f (>0) based on the vanishing moment method which was developed by the authors in Feng and Neilan (J. Sci. Comput. 38:74–98, 2009) and Feng (Convergence of the vanishing moment method for the Monge-Ampère equation, submitted). In this approach, the Monge-Ampère equation is approximated by the fourth order quasilinear equation −εΔ² u ^ε +det D ² u ^ε =f accompanied by appropriate boundary conditions. This new approach enables us to construct convergent Galerkin numerical methods for the fully nonlinear Monge-Ampère equation (and other fully nonlinear second order partial differential equations), a task which has been impracticable before. In this paper, we first develop some finite element and spectral Galerkin methods for approximating the solution u ^ε of the regularized problem. We then derive optimal order error estimates for the proposed numerical methods. In particular, we track explicitly the dependence of the error bounds on the parameter ε, for the error u^e-u^e_hu^{\varepsilon}-u^{\varepsilon}_{h}. Due to the strong nonlinearity of the underlying equation, the standard error estimate technique, which has been widely used for error analysis of finite element approximations of nonlinear problems, does not work here. To overcome the difficulty, we employ a fixed point technique which strongly makes use of the stability property of the linearized problem and its finite element approximations. Finally, using the Argyris finite element method as an example, we present a detailed numerical study of the rates of convergence in terms of powers of ε for the error u⁰-u_h^eu^{0}-u_{h}^{\varepsilon}, and numerically examine what is the “best” mesh size h in relation to ε in order to achieve these rates.     

Minimum Cost Source Location Problems with Flow Requirements

In this paper, we consider source location problems and their generalizations with three connectivity requirements (arc-connectivity requirements λ and two kinds of vertex-connectivity requirements κ and ), where the source location problems are to find a minimum-cost set S⊆V in a given graph G=(V,A) with a capacity function u:A→ℝ₊ such that for each vertex v∈V, the connectivity from S to v (resp., from v to S) is at least a given demand d ⁻(v) (resp., d ⁺(v)). We show that the source location problem with edge-connectivity requirements in undirected networks is strongly NP-hard, which solves an open problem posed by Arata et al. (J. Algorithms 42: 54–68, 2002). Moreover, we show that the source location problems with three connectivity requirements are inapproximable within a ratio of cln D for some constant c, unless every problem in NP has an O(N ^{log log N} )-time deterministic algorithm. Here D denotes the sum of given demands. We also devise (1+ln D)-approximation algorithms for all the extended source location problems if we have the integral capacity and demand functions. By the inapproximable results above, this implies that all the source location problems are Θ(ln ∑ _v∈V (d ⁺(v)+d ⁻(v)))-approximable. An extended abstract of this paper appeared in Sakashita et al. (Proceedings of LATIN 2006, Chile, LNCS, vol. 3887, pp. 769–780, March 2006).     

On Counting 3-D Matchings of Size <Emphasis Type="Italic">k</Emphasis>

The computational complexity of counting the number of matchings of size k in a given triple set has been open. It is conjectured that the problem is not fixed parameter tractable. In this paper, we present a fixed parameter tractable randomized approximation scheme (FPTRAS) for the problem. More precisely, we develop a randomized algorithm that, on given positive real numbers ε and δ, and a given set S of n triples and an integer k, produces a number h in time O(5.48^3k n ²ln (2/δ)/ε ²) such that

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

Richardson extrapolation technique for singularly perturbed parabolic convection–diffusion problems

This paper deals with the study of a post-processing technique for one-dimensional singularly perturbed parabolic convection–diffusion problems exhibiting a regular boundary layer. For discretizing the time derivative, we use the classical backward-Euler method and for the spatial discretization the simple upwind scheme is used on a piecewise-uniform Shishkin mesh. We show that the use of Richardson extrapolation technique improves the ε-uniform accuracy of simple upwinding in the discrete supremum norm from O (N ⁻¹ ln N + Δt) to O (N ⁻² ln² N + Δt ²), where N is the number of mesh-intervals in the spatial direction and Δt is the step size in the temporal direction. The theoretical result is also verified computationally by applying the proposed technique on two test examples.     

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.     

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.     

Approximability of Sparse Integer Programs

The main focus of this paper is a pair of new approximation algorithms for certain integer programs. First, for covering integer programs {min cx:Ax≥b,0≤x≤d} where A has at most k nonzeroes per row, we give a k-approximation algorithm. (We assume A,b,c,d are nonnegative.) For any k≥2 and ε>0, if P≠NP this ratio cannot be improved to k−1−ε, and under the unique games conjecture this ratio cannot be improved to k−ε. One key idea is to replace individual constraints by others that have better rounding properties but the same nonnegative integral solutions; another critical ingredient is knapsack-cover inequalities. Second, for packing integer programs {max cx:Ax≤b,0≤x≤d} where A has at most k nonzeroes per column, we give a (2k ²+2)-approximation algorithm. Our approach builds on the iterated LP relaxation framework. In addition, we obtain improved approximations for the second problem when k=2, and for both problems when every A _ij is small compared to b _i . Finally, we demonstrate a 17/16-inapproximability for covering integer programs with at most two nonzeroes per column.     

An Almost Space-Optimal Streaming Algorithm for Coresets in Fixed Dimensions

We present a new streaming algorithm for maintaining an ε-kernel of a point set in ℝ ^d using O((1/ε ^(d−1)/2)log (1/ε)) space. The space used by our algorithm is optimal up to a small logarithmic factor. This significantly improves (for any fixed dimension d ≥3) the best previous algorithm for this problem that uses O(1/ε ^d−(3/2)) space, presented by Agarwal and Yu. Our algorithm immediately improves the space complexity of the previous streaming algorithms for a number of fundamental geometric optimization problems in fixed dimensions, including width, minimum-volume bounding box, minimum-radius enclosing cylinder, minimum-width enclosing annulus, etc.     

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.     

Covering Many or Few Points with Unit Disks

Let P be a set of n weighted points. We study approximation algorithms for the following two continuous facility-location problems. In the first problem we want to place m unit disks, for a given constant m≥1, such that the total weight of the points from P inside the union of the disks is maximized. We present algorithms that compute, for any fixed ε>0, a (1−ε)-approximation to the optimal solution in O(nlog n) time. In the second problem we want to place a single disk with center in a given constant-complexity region X such that the total weight of the points from P inside the disk is minimized. Here we present an algorithm that computes, for any fixed ε>0, in O(nlog ² n) expected time a disk that is, with high probability, a (1+ε)-approximation to the optimal solution. A preliminary version of this work has appeared in Approximation and Online Algorithms—WAOA 2006, LNCS, vol. 4368.     

Error estimates for two-phase stefan problems in several space variables,II: Non-linear flux conditions

In this paper we derive L²-error estimates for multidimensional two-phase Stefan problems involving further non-linearities such as non-linear flux conditions. We approximate the enthalpy formulation by a regularization procedure combined with a C⁰-piecewise linear finite element scheme in space, and the implicit Euler scheme in time. Under some restrictions on the initial datum and on the finite element mesh, we obtain an L²-rate of convergence of order ε^1/2 for regularized problems, and an L²-rate of convergence of order (h|log h|^k+τ+ε)^1/2 for the discrete problems (k=0,1). These estimates lead to the choice h∼ε∼τ and yeild a global L²-rate essentially of order h^1/2. The a priori relationship between the approximation parameters allows the discrete problem to satisfy a maximum principle (without a lumping procedure); from which a priori bounds and monotonicity properties of the discrete solutions are shown. This work was supported by the “Consejo Nacional de Investigaciones Científicas y Técnicas de la República Argentina”.     

Some notes on maximal arc intersection of spherical polygons: its \mathcal{NP} -hardness and approximation algorithms

Finding a sequence of workpiece orientations such that the number of setups is minimized is an important optimization problem in manufacturing industry. In this paper we present some interesting notes on this optimal workpiece setup problem. These notes show that (1) The greedy algorithm proposed in Comput. Aided Des. 35 (2003), pp. 1269–1285 for the optimal workpiece setup problem has the performance ratio bounded by O(ln n−ln ln n+0.78), where n is the number of spherical polygons in the ground set; (2) In addition to greedy heuristic, linear programming can also be used as a near-optimal approximation solution; (3) The performance ratio by linear programming is shown to be tighter than that of greedy heuristic in some cases.     

Indexing Factors with Gaps

Indexing of factors or substrings is a widely used and useful technique in stringology and can be seen as a tool in solving diverse text algorithmic problems. A gapped-factor is a concatenation of a factor of length k, a gap of length d and another factor of length k′. Such a gapped factor is called a (k−d−k′)-gapped-factor. The problem of indexing the gapped-factors was considered recently by Peterlongo et al. (In: Stringology, pp. 182–196, 2006). In particular, Peterlongo et al. devised a data structure, namely a gapped factor tree (GFT) to index the gapped-factors. Given a text of length n over the alphabet Σ and the values of the parameters k, d and k′, the construction of GFT requires O(n|Σ|) time. Once GFT is constructed, a given (k−d−k′)-gapped-factor can be reported in O(k+k′+Occ) time, where Occ is the number of occurrences of that factor in  . In this paper, we present a new improved indexing scheme for the gapped-factors. The improvements we achieve come from two aspects. Firstly, we generalize the indexing data structure in the sense that, unlike GFT, it is independent of the parameters k and k′. Secondly, our data structure can be constructed in O(nlog ^1+ε n) time and space, where 0<ε<1. The only price we pay is a slight increase, i.e. an additional log log n term, in the query time. Preliminary version appeared in [29]. C.S. Iliopoulos is supported by EPSRC and Royal Society grants. M.S. Rahman is supported by the Commonwealth Scholarship Commission in the UK under the Commonwealth Scholarship and Fellowship Plan (CSFP). M.S. Rahman is on leave from Department of CSE, BUET, Dhaka 1000, Bangladesh.     

Constructions of Low-degree and Error-Correcting ε-Biased Generators

In this work we give two new constructions of ε-biased generators. Our first construction significantly extends a result of Mossel et al. (Random Structures and Algorithms 2006, pages 56-81), and our second construction answers an open question of Dodis and Smith (STOC 2005, pages 654-663). In particular we obtain the following results:

A family of non-conforming elements and the analysis of Nitsche’s method for a singularly perturbed fourth order problem

In this paper we address several issues arising from a singularly perturbed fourth order problem with small parameter ε. First, we introduce a new family of non-conforming elements. We then prove that the corresponding finite element method is robust with respect to the parameter ε and uniformly convergent to order h ^1/2. In addition, we analyze the effect of treating the Neumann boundary condition weakly by Nitsche’s method. We show that such treatment is superior when the parameter ε is smaller than the mesh size h and obtain sharper error estimates. Such error analysis is not restricted to the proposed elements and can easily be carried out to other elements as long as the Neumann boundary condition is imposed weakly. Finally, we discuss the local error estimates and the pollution effect of the boundary layers in the interior of the domain.