Relay placement for fault tolerance in wireless networks in higher dimensions

In this paper we consider the problem of adding the smallest number of additional (relay) nodes to a network of static nodes with limited communication range so that the induced communication graph is 2-connected (we consider both edge and vertex connectivity). The problem is NP-hard. We develop algorithms that find close to optimal solutions for both edge and vertex connectivity. We prove the algorithms have an approximation ratio of 2M for nodes distributed in a d-dimensional Euclidean space, where M is the maximum node degree of a Minimum Spanning Tree in d dimensions using Euclidean metrics. In addition, our methods extend with the same approximation guarantees to a generalization when the locations of relays are required to avoid certain polygonal regions (obstacles).     

A finite algorithm for the continuousp-center location problem on a graph

LetG=(V,E) be an undirected graph with positive integer edge lengths. Letm be the number of edges inE, and letd be the sum of the edge lengths. We prove that the solution value to the continuousp-center location problem is a rationalp ₁/p ₂, where logp ₁=O(m ⁵ logd+m ⁶ logp),i=1,2. This result is then used to construct a finite algorithm for the continuousp-center problem.     

A projected Weiszfeld algorithm for the box-constrained Weber location problem

The Weber problem consists of finding a point in Rⁿ that minimizes the weighted sum of distances from m points in Rⁿ that are not collinear. An application that motivated this problem is the optimal location of facilities in the 2-dimensional case. A classical method to solve the Weber problem, proposed by Weiszfeld in 1937, is based on a fixed-point iteration.In this work we generalize the Weber location problem considering box constraints. We propose a fixed-point iteration with projections on the constraints and demonstrate descending properties. It is also proved that the limit of the sequence generated by the method is a feasible point and satisfies the KKT optimality conditions. Numerical experiments are presented to validate the theoretical results.     

On a class of finite rings

In [7], Corbas determined all finite rings in which the product of any two zero-divisors is zero, and showed that they are of two types, one of characteristic p ²and the other of characteristic p².

The purpose of this paper is to address the problem of the classification of finite rings such that.

(i)the set of all zero-divisors form an ideal M.

(ii)M ³=(0); and.

(iii)M ³≠(0).

Because of (i), these rings are called completely primary and we shall call a finite completely primary ring R which satisfies conditions (i), (ii) and (iii), a ring with property(T). These rings are of three types, namely, of characteristic p p ² and p ³. The characteristic p ² case is subdivided into cases in which p?M ² p?ann(M)?M ² and p?M ?ann(M), where ann(M) denotes the two-sided annihilator of where M in R.     

Embedding metric spaces into normed spaces and estimates of metric capacity

Let M^d{\cal M}^d be an arbitrary real normed space of finite dimension d ≥ 2. We define the metric capacity of M^d{\cal M}^d as the maximal m ? \Bbb Nm \in {\Bbb N} such that every m-point metric space is isometric to some subset of M^d{\cal M}^d (with metric induced by M^d{\cal M}^d ). We obtain that the metric capacity of M^d{\cal M}^d lies in the range from 3 to ë\frac32d û+1\left\lfloor\frac{3}{2}d\right\rfloor+1 , where the lower bound is sharp for all d, and the upper bound is shown to be sharp for d ∈ {2, 3}. Thus, the unknown sharp upper bound is asymptotically linear, since it lies in the range from d + 2 to ë\frac32d û+1\left\lfloor\frac{3}{2}d\right\rfloor+1 .     

Multi-Dimensional Pattern Matching with Dimensional Wildcards: Data Structures and Optimal On-Line Search Algorithms

We introduce a new multidimensional pattern matching problem that is a natural generalization of string matching, a well studied problem[1]. The motivation for its algorithmic study is mainly theoretical. LetA[1:n₁,…,1:n_d] be a text matrix withN = n₁…n_dentries andB[1:m₁,…,1:m_r] be a pattern matrix withM = m₁…m_rentries, whered ≥ r ≥ 1 (the matrix entries are taken from an ordered alphabet Σ). We study the problem of checking whether somer-dimensional submatrix ofAis equal toB(i.e., adecisionquery).Acan be preprocessed andBis given on-line. We define a new data structure for preprocessingAand propose CRCW-PRAM algorithms that build it inO(log N) time withN²/n_maxprocessors, wheren_max = max(n₁,…,n_d), such that the decision query forBtakesO(M) work andO(log M) time. By using known techniques, we would get the same preprocessing bounds but anO((^d_r)M) work bound for the decision query. The latter bound is undesirable since it can depend exponentially ond; our bound, in contrast, is independent ofdand optimal. We can also answer, in optimal work, two further types of queries: (a) anenumerationquery retrieving all ther-dimensional submatrices ofAthat are equal toBand (b) anoccurrencequery retrieving only the distinct positions inAthat correspond to all of these submatrices. As a byproduct, we also derive the first efficient sequential algorithms for the new problem.     

Optimal location with equitable loads

The problem considered in this paper is to find p locations for p facilities such that the weights attracted to each facility will be as close as possible to one another. We model this problem as minimizing the maximum among all the total weights attracted to the various facilities. We propose solution procedures for the problem on a network, and for the special cases of the problem on a tree or on a path. The complexity of the problem is analyzed, O(n) algorithms and an O(pn ³) dynamic programming algorithm are proposed for the problem on a path respectively for p=2 and p>2 facilities. Heuristic algorithms (two types of a steepest descent approach and tabu search) are proposed for its solution. Extensive computational results are presented.     

Multiple Symmetric Solutions for Discrete Lidstone Boundary Value Problems

We offer criteria for the existence of single, double and multiple positive symmetric solutions for the boundary value problem ?^{2m y(k-m)= f(y(k), ?²y(k-1)….,?SUP>2i y(k-i),…,?2(m-1)} y(k-(m-1))), k∈{a+1,…,b+1} ?²ⁱ y(a+1-m)=?²ⁱ y(b+1+m-2i)=0, 0≤i≤m-1 where m ≥ 1 and (-1)^m f can either be positive or the condition can be relaxed.     

Sharp Lp decay of oscillatory integral operators with certain homogeneous polynomial phases in several variables

In this paper, we obtain the L~p decay of oscillatory integral operators T_λ with certain homogeneous polynomial phase functions of degree d in(n + n)-dimensions; we require that d 2 n. If d/(d-n) p d/n,the decay is sharp and the decay rate is related to the Newton distance. For p = d/n or d/(d-n), we obtain the almost sharp decay, where "almost" means that the decay contains a log(λ) term. For otherwise, the L~p decay of T_λ is also obtained but not sharp. Finally, we provide a counterexample to show that d/(d-n) p d/n is not necessary to guarantee the sharp decay.     

Simulation of Stationary Gaussian Processes in [0, 1] d

Abstract

A method for simulating a stationary Gaussian process on a fine rectangular grid in [0, 1]^d ??^d is described. It is assumed that the process is stationary with respect to translations of ?^d, but the method does not require the process to be isotropic. As with some other approaches to this simulation problem, our procedure uses discrete Fourier methods and exploits the efficiency of the fast Fourier transform. However, the introduction of a novel feature leads to a procedure that is exact in principle when it can be applied. It is established that sufficient conditions for it to be possible to apply the procedure are (1) the covariance function is summable on ?^d, and (2) a certain spectral density on the d-dimensional torus, which is determined by the covariance function on ?^d, is strictly positive. The procedure can cope with more than 50,000 grid points in many cases, even on a relatively modest computer. An approximate procedure is also proposed to cover cases where it is not feasible to apply the procedure in its exact form.     

An algorithm for then×n optimum assignment problem

In this paper we present an algorithm for finding an optimum assignment for ann×n matrixM inn iterations. The method uses systematic permutations on the rows ofM and is based on the properties of optimum assignments. The implementation presented in the paper requires at mostO(n ³) in time andn ²+6n memory locations for solving a densen×n problem.This work was supported by the National Science Foundation Grant NSF ENG 74-19788.     

Automatic Smoothing Spline Projection Pursuit

Abstract

A highly flexible nonparametric regression model for predicting a response y given covariates {x_k}^d _k=1 is the projection pursuit regression (PPR) model ? = h(x) = β₀ + Σ_jβ_jf_j(α^T _jx) where the f_j , are general smooth functions with mean 0 and norm 1, and Σ^d _k=1α² _kj=1. The standard PPR algorithm of Friedman and Stuetzle (1981) estimates the smooth functions f_j using the supersmoother nonparametric scatterplot smoother. Friedman's algorithm constructs a model with M _max linear combinations, then prunes back to a simpler model of size M ≤ M _max, where M and M _max are specified by the user. This article discusses an alternative algorithm in which the smooth functions are estimated using smoothing splines. The direction coefficients α_j, the amount of smoothing in each direction, and the number of terms M and M _max are determined to optimize a single generalized cross-validation measure.     

Weak ɛ-Nets for Points on a Hypersphere

A weak ε -net for a set of points M, is a set of points W (not necessarily in M) where every convex set containing ε |M| points in M must contain at least one point in W. Weak ε-nets have applications in diverse areas such as computational geometry, learning theory, optimization, and statistics. Here we show that if M is a set of points quasi-uniformly distributed on a unit sphere S ^d-1 , then there is a weak ε-net of size for M, where k _d is exponential in d. A set of points M is quasi-uniformly distributed on S ^d-1 if, for any spherical cap , we have for three positive constants c_1, c_2, and c ₃ . Further, we show that reducing our upper bound by asymptotically more than a factor directly implies the solution of a long unsolved problem of Danzer and Rogers. Received April 12, 1995, and in revised form May 8, 1995.     

Spherical Maximal Operators on Radial Functions

Let A_tf(x) denote the mean of f over a sphere of radius t and center x. We prove sharp estimates for the maximal function M_E f(X) = sup_t∈_E |Atf(x)| where E is a fixed set in IR⁺ and f is a radial function ∈ L^p(IR^d). Let P_d = d/(d?1) (the critical exponent for Stein's maximal function). For the cases (i) p < p_d, d ? 2, and (ii) p = p_d, d ? 3, and for p ? q ? ∞ we prove necessary and sufficient conditions on E for M_E to map radial functions in L^p to the Lorentz space L^P,q.     

The limiting angle of certain riemannian brownian motions

Let M be a Cartan-Hadamard manifold of dimension d ≧ 3, let p ? M and x = exp {r(x)θ(x)} be geodesic polar coordinates with pole p and let X be the Brownian motion on M. Let Sect_M(x) denote the sectional curvature of any plane section in M_x. We prove that for each c > 2, there is a 0 < β < 1 such that if - L²r(x)^2β ≦ Sect_M(x) ≦ -cr(x)^?2 for all x in the complement of a compact set, then lim_{t → ∞} θ(X_t) exists a.s. and defines a nontrivial invariant random variable. The Dirichlet problem at infinity and a conjecture of Greene and Wu are also discussed.     

Triangulating Smooth Submanifolds with Light Scaffolding

We propose an algorithm to sample and mesh a k-submanifold M{\mathcal{M}} of positive reach embedded in \mathbbR^d{\mathbb{R}^{d}} . The algorithm first constructs a crude sample of M{\mathcal{M}} . It then refines the sample according to a prescribed parameter e{\varepsilon} , and builds a mesh that approximates M{\mathcal{M}} . Differently from most algorithms that have been developed for meshing surfaces of \mathbbR ³{\mathbb{R} ^3} , the refinement phase does not rely on a subdivision of \mathbbR ^d{\mathbb{R} ^d} (such as a grid or a triangulation of the sample points) since the size of such scaffoldings depends exponentially on the ambient dimension d. Instead, we only compute local stars consisting of k-dimensional simplices around each sample point. By refining the sample, we can ensure that all stars become coherent leading to a k-dimensional triangulated manifold [^(M)]{\hat{\mathcal{M}}} . The algorithm uses only simple numerical operations. We show that the size of the sample is O(e^-k){O(\varepsilon ^{-k})} and that [^(M)]{\hat{\mathcal{M}}} is a good triangulation of M{\mathcal{M}} . More specifically, we show that M{\mathcal{M}} and [^(M)]{\hat{\mathcal{M}}} are isotopic, that their Hausdorff distance is O(e²){O(\varepsilon ^{2})} and that the maximum angle between their tangent bundles is O(e){O(\varepsilon )} . The asymptotic complexity of the algorithm is T(e) = O(e^-k2-k){T(\varepsilon) = O(\varepsilon ^{-k^2-k})} (for fixed M, d{\mathcal{M}, d} and k).     

Volume,diameter and the minimal mass of a stationary 1-cycle

In this paper we present upper bounds on the minimal mass of a non-trivial stationary 1-cycle. The results that we obtain are valid for all closed Riemannian manifolds. The first result is that the minimal mass of a stationary 1-cycle on a closed n-dimensional Riemannian manifold Mⁿ is bounded from above by (n + 2)!d/4, where d is the diameter of a manifold Mⁿ. The second result is that the minimal mass of a stationary 1-cycle on a closed Riemannian manifold Mⁿ is bounded from above by where where is the filling radius of a manifold, and where is its volume.     

Geodesic loops and periodic geodesics on a Riemannian manifold diffeomorphic to <Emphasis Type="Italic">S</Emphasis><Superscript>3</Superscript>

Let M ⁿ be a closed 2-connected Riemannian manifold, such that π₃(M ⁿ ) ≠ { 0 }. In this paper we prove that either there exists a periodic geodesic on M ⁿ of length ≤ 6d, where d is the diameter of M ⁿ , or at each point p ∈ M ⁿ there exists a geodesic loop of length ≤ 2d.