Distributed construction of low-interference spanners

We propose a new low-interference topology for wireless ad hoc networks modeled by Quasi Unit Disk Graphs. Our topology combines two existing structures, the relaxed Greedy structure developed by Damian, Pandit and Pemmaraju, and the low-interference structure developed by Burkhart, von Rickenbach, Wattenhofer and Zollinger. Our main contribution is showing that, when applied on a QUDG G = (V, E), this new structure inherits most properties of the two underlying structures: (i) it is a t(1 + ε) spanner of G, for any t > 1 and ε > 0, (ii) it has optimal interference among all t-spanners for G, (iii) it has O(1) maximum degree, (iv) its total weight is within a factor of O(log Δ) of the weight of a minimum spanning tree for V, where Δ is the aspect ratio of G, and (v) it can be implemented efficiently in O(log Δ + log^* n) rounds of communication. This work was supported by NSF grant CCF-0728909. A preliminary version of this paper, titled “Distributed construction of bounded-degree low-interference spanners of low weight”, appeared in MobiHoc’08.     

Il metodo di Treffiz-Fichera per i semigruppi. potenziale di tipo potenza

A variation of the Trefftz-Fichera method is presented to compute lower bounds for the eigenvalues of a positive self-adjoint operator with discrete spectrum with grow at least in a logarithmic way as the index diverges. As suggested by Barnes et al. [2] to compute ground state, the semigroupe ^−βH, β>0, is used rather than the iterated resolvent(H+β) ⁻ⁿ,n=1,2,... As an example, the method is applied to the operatorH=−Δ+|x|^γ. inL ²(R), 1≤γ≤4.      

On Centralized Smooth Scheduling

This paper studies evenly distributed sets of natural numbers and their applications to scheduling in a centralized environment. Such sets, called smooth sets, have the property that their quantity within each interval is proportional to the size of the interval, up to a bounded additive deviation; namely, for ρ,Δ∈ℝ a set A of natural numbers is (ρ,Δ)-smooth if abs(|I|⋅ρ−|I∩A|)<Δ for any interval I⊂ℕ.     

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.     

When Does Eddy Viscosity Damp Subfilter Scales Sufficiently?

Large eddy simulation (LES) seeks to predict the dynamics of spatially filtered turbulent flows. The very essence is that the LES-solution contains only scales of size ≥Δ, where Δ denotes some user-chosen length scale. This property enables us to perform a LES when it is not feasible to compute the full, turbulent solution of the Navier-Stokes equations. Therefore, in case the large eddy simulation is based on an eddy viscosity model we determine the eddy viscosity such that any scales of size <Δ are dynamically insignificant. In this paper, we address the following two questions: how much eddy diffusion is needed to (a) balance the production of scales of size smaller than Δ; and (b) damp any disturbances having a scale of size smaller than Δ initially. From this we deduce that the eddy viscosity ν _e has to depend on the invariants q = \frac12tr(S²)q = \frac{1}{2}\mathrm{tr}(S^{2}) and r = -\frac13tr(S³)r= -\frac{1}{3}\mathrm{tr}(S^{3}) of the (filtered) strain rate tensor S. The simplest model is then given by n_e = \frac32(D/p)² |r|/q\nu_{e} = \frac{3}{2}(\Delta/\pi)^{2} |r|/q. This model is successfully tested for a turbulent channel flow (Re  _τ =590).     

A second step toward the strong polynomial-time hierarchy

In this paper we discuss the concepts ofimmunity andsimplicity in levels of the relativized Polynomial-time Hierarchy just aboveP. We consider various diagonalization techniques with which oracle sets can be constructed relative to which strong separations between language classes in the first two levels of this hierarchy are established. In particular, we build oracle sets for separation of relativized Σ ₂ ^P from relativizedNP with immunity, of relativized Σ ₂ ^P from relativizedNP with bi-immunity, of relativized Σ ₂ ^P from relativized Δ ₂ ^P with immunity, of relativized Π ₂ ^P from relativized Δ ₂ ^P with immunity, and finally of relativized Σ ₂ ^P from relativized Π ₂ ^P with simplicity.     

Distributed Approximation of Capacitated Dominating Sets

We study local, distributed algorithms for the capacitated minimum dominating set (CapMDS) problem, which arises in various distributed network applications. Given a network graph G=(V,E), and a capacity cap(v)∈ℕ for each node v∈V, the CapMDS problem asks for a subset S⊆V of minimal cardinality, such that every network node not in S is covered by at least one neighbor in S, and every node v∈S covers at most cap(v) of its neighbors. We prove that in general graphs and even with uniform capacities, the problem is inherently non-local, i.e., every distributed algorithm achieving a non-trivial approximation ratio must have a time complexity that essentially grows linearly with the network diameter. On the other hand, if for some parameter ε>0, capacities can be violated by a factor of 1+ε, CapMDS becomes much more local. Particularly, based on a novel distributed randomized rounding technique, we present a distributed bi-criteria algorithm that achieves an O(log Δ)-approximation in time O(log ³ n+log (n)/ε), where n and Δ denote the number of nodes and the maximal degree in G, respectively. Finally, we prove that in geometric network graphs typically arising in wireless settings, the uniform problem can be approximated within a constant factor in logarithmic time, whereas the non-uniform problem remains entirely non-local.     

Windows scheduling of arbitrary-length jobs on multiple machines

The generalized windows scheduling problem for n jobs on multiple machines is defined as follows: Given is a sequence, I=〈(w ₁,ℓ ₁),(w ₂,ℓ ₂),…,(w _n ,ℓ _n )〉 of n pairs of positive integers that are associated with the jobs 1,2,…,n, respectively. The processing length of job i is ℓ _i slots where a slot is the processing time of one unit of length. The goal is to repeatedly and non-preemptively schedule all the jobs on the fewest possible machines such that the gap (window) between two consecutive beginnings of executions of job i is at most w _i slots. This problem arises in push broadcast systems in which data are transmitted on multiple channels. The problem is NP-hard even for unit-length jobs and a (1+ε)-approximation algorithm is known for this case by approximating the natural lower bound W(I)=?_i=1ⁿ(1/w_i)W(I)=\sum_{i=1}^{n}(1/w_{i}). The techniques used for approximating unit-length jobs cannot be extended for arbitrary-length jobs mainly because the optimal number of machines might be arbitrarily larger than the generalized lower bound W(I)=?_i=1ⁿ(l_i/w_i)W(I)=\sum_{i=1}^{n}(\ell_{i}/w_{i}). The main result of this paper is an 8-approximation algorithm for the WS problem with arbitrary lengths using new methods, different from those used for the unit-length case. The paper also presents another algorithm that uses 2(1+ε)W(I)+logw _max machines and a greedy algorithm that is based on a new tree representation of schedules. The greedy algorithm is optimal for some special cases, and computational experiments show that it performs very well in practice.     

Perfect fluid Bianchi I model with variable G and Λ

We study how to attack through different techniques a perfect fluid Bianchi I model with variable G and Λ. These tactics are: Lie group method (LM), imposing a particular symmetry, self-similarity (SS), matter collineations (MC), and kinematic self-similarity (KSS). We compare the tactics since they are quite similar (symmetry principles). We arrive at the conclusion that the LM is too restrictive and yields only a flat FRW solution with G = const and Λ = 0. The SS, MC, and KSS approaches bring us to a solution where G is a decreasing time function and Λ ∼ t ⁻², its sign depending on the equation of state while the exponents of the scale factors must satisfy the conditions Σ _i=1³ α _i = 1 and Σ _i=1³ α _i ² < 1, ∀ω, i.e., the solution is valid for all equations of state, relaxing in this way the Kasner conditions.     

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.     

The Bit Complexity of Distributed Sorting

We study the bit complexity of the sorting problem for asynchronous distributed systems. We show that for every network with a tree topology T, every sorting algorithm must send at least bits in the worst case, where is the set of possible initial values, and Δ _T is the sum of distances from all the vertices to a median of the tree. In addition, we present an algorithm that sends at most bits for such trees. These bounds are tight if either L=Ω(N ^1+ε ) or Δ _T =Ω(N ² ). We also present results regarding average distributions. These results suggest that sorting is an inherently nondistributive problem, since it requires an amount of information transfer that is equal to the concentration of all the data in a single processor, which then distributes the final results to the whole network. The importance of bit complexity—as opposed to message complexity—stems also from the fact that, in the lower bound discussion, no assumptions are made as to the nature of the algorithm. Received May 2, 1994; revised December 22, 1995.     

Solving the generalized sylvester matrix equation Σ i=1p AiXBi + Σ j=1q CjYDj=E over reflexive and anti-reflexive matrices

A matrix P ∈ ℝ ^n×n is called a generalized reflection if P ^T = P and P ²=I. An n×n matrix A is said to be a reflexive (anti-reflexive) with respect to P if A PAP (A = −PAP). In the present paper, two iterative methods are derived for solving the generalized Sylvester matrix equation Σ _i=1 ^p A _i XB _i + Σ _j=1 ^q C _j YD _j =E (including the Sylvester and Lyapunov matrix equations as special cases) over reflexive and anti-reflexive matrices respectively. It is proven that the iterative methods, respectively, consistently converge to the reflexive and anti-reflexive solutions of the matrix equation for any initial reflexive and anti-reflexive matrices. Finally, a numerical example is given to demonstrate the effectiveness of the derived methods.     

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.     

Graphic representation of the evolutionary processes of the compositions of multicomponent objects of any nature

A method for the graphic representation of evolutionary processes of compositions is described. Preparation of materials includes descending ranking of contents of components and standardization of the length of the obtained sequences while discarding excess contents. The following three parameters are calculated for the persistent distribution of contents: (1) information entropy H = −Σp _ilogp _i as a measure of complexity of the system’s composition, (2) anentropy A = −Σlogp _i as a measure of the composition purity, and (3) tolerance T = log[(Σ1/p _i)/n] as a measure of special purity. In order to represent the process of compositional change, paired diagrams with the axes En, An, and T are used. The obtained entropy diagrams describe separation and mixing processes that occur in nature, technology, and society in the most adequate manner.     

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.     

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.     

Efficiently Testing Sparse <Emphasis Type="Italic">GF</Emphasis>(2) Polynomials

We give the first algorithm that is both query-efficient and time-efficient for testing whether an unknown function f:{0,1} ⁿ →{−1,1} is an s-sparse GF(2) polynomial versus ε-far from every such polynomial. Our algorithm makes poly(s,1/ε) black-box queries to f and runs in time n⋅poly(s,1/ε). The only previous algorithm for this testing problem (Diakonikolas et al. in Proceedings of the 48th Annual Symposium on Foundations of Computer Science, FOCS, pp. 549–558, 2007) used poly(s,1/ε) queries, but had running time exponential in s and super-polynomial in 1/ε.     

Self-intersection elimination in metamorphosis of two-dimensional curves

H :[0, 1]× ³→ ³, where H(t, r) for t=0 and t=1 are two given planar curves C ₁(r) and C ₂(r). The first t parameter defines the time of fixing the intermediate metamorphosis curve. The locus of H(t, r) coincides with the ruled surface between C ₁(r) and C ₂(r), but each isoparametric curve of H(t, r) is self-intersection free. The second algorithm suits morphing operations of planar curves. First, it constructs the best correspondence of the relative parameterizations of the initial and final curves. Then it eliminates the remaining self-intersections and flips back the domains that self-intersect.     

New Linear-Time Algorithms for Edge-Coloring Planar Graphs

We show efficient algorithms for edge-coloring planar graphs. Our main result is a linear-time algorithm for coloring planar graphs with maximum degree Δ with max {Δ,9} colors. Thus the coloring is optimal for graphs with maximum degree Δ≥9. Moreover for Δ=4,5,6 we give linear-time algorithms that use Δ+2 colors. These results improve over the algorithms of Chrobak and Yung (J. Algorithms 10:35–51, 1989) and of Chrobak and Nishizeki (J. Algorithms 11:102–116, 1990) which color planar graphs using max {Δ,19} colors in linear time or using max {Δ,9} colors in time. R. Cole supported in part by NSF grants CCR0105678 and CCF0515127 and IDM0414763. Ł. Kowalik supported in part by KBN grant 4T11C04425. Part of this work was done while Ł. Kowalik was staying at the Max Planck Institute in Saarbruecken, Germany.