An optimal algorithm for constructing the weighted voronoi diagram in the plane

Let S denote a set of n points in the plane such that each point p has assigned a positive weight w(p) which expresses its capability to influence its neighbourhood. In this sense, the weighted distance of an arbitrary point x from p is given by d_e(x,p)/w(p) where d_e denotes the Euclidean distance function. The weighted Voronoi diagram for S is a subdivision of the plane such that each point p in S is associated with a region consisting of all points x in the plane for which p is a weighted nearest point of S.An algorithm which constructs the weighted Voronoi diagram for S in O(n²) time is outlined in this paper. The method is optimal as the diagram can consist of Θ(n²) faces, edges and vertices.     

Fast message dissemination in random geometric networks

We analyze information dissemination in random geometric networks, which consist of n nodes placed uniformly at random in the square ${[0,\sqrt{n}]^{2}}$ . In the corresponding graph two nodes u and v are connected by a (directed) edge, i.e., u is an (incoming) neighbor of v, if and only if the distance between u and v is smaller than the transmission radius assigned to u. In order to study the performance of distributed communication algorithms in such networks, we adopt here the ad-hoc radio communication model with no collision detection mechanism available. In this model the topology of network connections is not known in advance. Also a node v is capable of receiving a message from its neighbor u if u is the only (incoming) neighbor transmitting in a given step. Otherwise a collision occurs prompting interference that is not distinguishable from the background noise in the network. First, we consider networks modeled by random geometric graphs in which all nodes have the same radius ${r > \delta \sqrt{\log n}}$ , where δ is a sufficiently large constant. In such networks, we provide a rigorous study of the classical communication problem of distributed gossiping (all-to-all communication). We examine various scenarios depending on initial local knowledge and capabilities of network nodes. We show that in many cases an asymptotically optimal distributed O(D)-time gossiping is feasible, where D stands for the diameter of the network. Later, we consider networks in which the transmission radii of the nodes vary according to a power law distribution, i.e., any node is assigned a transmission radius r > r _min according to probability density function ρ(r) ~ r ^?α . More precisely, ${\rho(r) = (\alpha-1)r_{\min}^{\alpha-1} r^{-\alpha}}$ , where ${\alpha \in (1, 3)}$ and ${r_{\min} > \delta \sqrt{\log n}}$ with δ being a large constant. In this case, we develop a simple broadcasting algorithm that runs in time O(log log n) (i.e., O(D)) always surely, and we show that this result is asymptotically optimal. Finally, we consider networks in which any node is assigned a transmission radius r > c according to the probability density function ρ(r) =  (α?1)c ^α-1 r ^?α , where α is a constant from the same range as before and c is a constant. In this model the graph is usually not strongly connected, however, there is one giant component with Ω(n) nodes, and there is a directed path from each node of this giant component to every other node in the graph. We assume that the message which has to be disseminated is placed initially in one of the nodes of the giant component, and every node is aware of its own position in ${[0,\sqrt{n}] \times [0,\sqrt{n}]}$ . Then, we show that there exists a randomized algorithm which delivers the broadcast message to all nodes in the network in time O(D . (log log n)²), almost always surely, where D stands for the diameter of the giant component of the graph. One can conclude from our studies that setting the transmission radii of the nodes according to a power law distribution brings clear advantages. In particular, one can design energy efficient radio networks with low average transmission radius, in which broadcasting can be performed exponentially faster than in the (extensively studied) case where all nodes have the uniform low transmission power.     

Analysis of scalable data-privatization threading algorithms for hybrid MPI/OpenMP parallelization of molecular dynamics

We propose and analyze threading algorithms for hybrid MPI/OpenMP parallelization of a molecular-dynamics simulation, which are scalable on large multicore clusters. Two data-privatization thread scheduling algorithms via nucleation-growth allocation are introduced: (1) compact-volume allocation scheduling (CVAS); and (2) breadth-first allocation scheduling (BFAS). The algorithms combine fine-grain dynamic load balancing and minimal memory-footprint data privatization threading. We show that the computational costs of CVAS and BFAS are bounded by Θ(n ^5/3 p ^?2/3) and Θ(n), respectively, for p threads working on n particles on a multicore compute node. Memory consumption per node of both algorithms scales as O(n+n ^2/3 p ^1/3), but CVAS has smaller prefactors due to a geometric effect. Based on these analyses, we derive the selection criterion between the two algorithms in terms of the granularity, n/p. We observe that memory consumption is reduced by 75 % for p=16 and n=8,192 compared to a naïve data privatization, while maintaining thread imbalance below 5 %. We obtain a strong-scaling speedup of 14.4 with 16-way threading on a four quad-core AMD Opteron node. In addition, our MPI/OpenMP code achieves 2.58× and 2.16× speedups over the MPI-only implementation on 32,768 cores of BlueGene/P for 0.84 and 1.68 million particle systems, respectively.     

Fast Sequential Importance Sampling to Estimate the Graph Reliability Polynomial

The reliability polynomial of a graph counts its connected subgraphs of various sizes. Algorithms based on sequential importance sampling (SIS) have been proposed to estimate a graph’s reliability polynomial. We develop an improved SIS algorithm for estimating the reliability polynomial. The new algorithm runs in expected time O(mlogn α(m,n)) at worst and ≈m in practice, compared to Θ(m ²) for the previous algorithm. We analyze the error bounds of this algorithm, including comparison to alternative estimation algorithms. In addition to the theoretical analysis, we discuss methods for estimating the variance and describe experimental results on a variety of random graphs.     

The densest hemisphere problem

Given a set K of n points on the unit sphere S^d in d-dimensional Euclidean space, a hemisphere of S^d is densest if it contains a largest subset of K. In this paper we consider the problem of determining a densest hemisphere and present the following complementary results: (i) a discretized version of the original problem, restated as a feasibility question, is NP-complete when both n and d are arbitrary; (ii) when the number d of dimensions is fixed, there exists a polynomial time algorithm which solves the problem in time O(n_d?1 log n) on a random access machine with unit cost arithmetic operations.     

Sleeping on the Job: Energy-Efficient and Robust Broadcast for Radio Networks

We address the problem of minimizing power consumption when broadcasting a message from one node to all the other nodes in a radio network. To enable power savings for such a problem, we introduce a compelling new data streaming problem which we call the Bad Santa problem. Our results on this problem apply for any situation where: (1) a node can listen to a set of n nodes, out of which at least half are non-faulty and know the correct message; and (2) each of these n nodes sends according to some predetermined schedule which assigns each of them its own unique time slot. In this situation, we show that in order to receive the correct message with probability 1, it is necessary and sufficient for the listening node to listen to a \(\Theta(\sqrt{n})\) expected number of time slots. Moreover, if we allow for repetitions of transmissions so that each sending node sends the message O(log?^? n) times (i.e. in O(log?^? n) rounds each consisting of the n time slots), then listening to O(log?^? n) expected number of time slots suffices. We show that this is near optimal.We describe an application of our result to the popular grid model for a radio network. Each node in the network is located on a point in a two dimensional grid, and whenever a node sends a message m, all awake nodes within L _∞ distance r receive m. In this model, up to \(t<\frac{r}{2}(2r+1)\) nodes within any 2r+1 by 2r+1 square in the grid can suffer Byzantine faults. Moreover, we assume that the nodes that suffer Byzantine faults are chosen and controlled by an adversary that knows everything except for the random bits of each non-faulty node. This type of adversary models worst-case behavior due to malicious attacks on the network; mobile nodes moving around in the network; or static nodes losing power or ceasing to function. Let n=r(2r+1). We show how to solve the broadcast problem in this model with each node sending and receiving an expected \(O(n\log^{2}{|m|}+\sqrt{n}|m|)\) bits where |m| is the number of bits in m, and, after broadcasting a fingerprint of m, each node is awake only an expected \(O(\sqrt{n})\) time slots. Moreover, for t≤(1?ε)(r/2)(2r+1), for any constant ε>0, we can achieve an even better energy savings. In particular, if we allow each node to send O(log?^? n) times, we achieve reliable broadcast with each node sending O(nlog?²|m|+(log?^? n)|m|) bits and receiving an expected O(nlog?²|m|+(log?^? n)|m|) bits and, after broadcasting a fingerprint of m, each node is awake for only an expected O(log?^? n) time slots. Our results compare favorably with previous protocols that required each node to send Θ(|m|) bits, receive Θ(n|m|) bits and be awake for Θ(n) time slots.     

Note on the Structure of Kruskal’s Algorithm

We study the merging process when Kruskal’s algorithm is run with random graphs as inputs. Our aim is to analyze this process when the underlying graph is the complete graph on n vertices lying in [0,1] ^d , and edge set weighted with the Euclidean distance. The height of the binary tree explaining the merging process is proved to be Θ(n) on average. On the way to the proof, we obtain similar results for the complete graph and the d-dimensional square lattice with i.i.d. edge weights.     

An output sensitive algorithm for computing a maximum independent set of a circle graph

We present an output sensitive algorithm for computing a maximum independent set of an unweighted circle graph. Our algorithm requires O(nmin{d,α}) time at worst, for an n vertex circle graph where α is the independence number of the circle graph and d is its density. Previous algorithms for this problem required Θ(nd) time at worst.     

On computing the diameter of a point set in high dimensional Euclidean space

We consider the problem of computing the diameter of a set of n points in d-dimensional Euclidean space under Euclidean distance function. We describe an algorithm that in time O(dnlogn+n²) finds with high probability an arbitrarily close approximation of the diameter. For large values of d the complexity bound of our algorithm is a substantial improvement over the complexity bounds of previously known exact algorithms. Computing and approximating the diameter are fundamental primitives in high dimensional computational geometry and find practical application, for example, in clustering operations for image databases.     

How much precision is needed to compare two sums of square roots of integers?

In this paper, we investigate the problem of the minimum nonzero difference between two sums of square roots of integers. Let r(n,k) be the minimum positive value of where ai and bi are integers not larger than integer n. We prove by an explicit construction that r(n,k)=O(n−2k+3/2) for fixed k and any n. Our result implies that in order to compare two sums of k square roots of integers with at most d digits per integer, one might need precision of as many as digits. We also prove that this bound is optimal for a wide range of integers, i.e., r(n,k)=Θ(n−2k+3/2) for fixed k and for those integers in the form of and , where n^′ is any integer satisfied the form and i is any integer in [0,k−1]. We finally show that for k=2 and any n, this bound is also optimal, i.e., r(n,2)=Θ(n−7/2).     

Two New Perspectives on Multi-Stage Group Testing

The group testing problem asks to find d?n defective elements out of n elements, by testing subsets (pools) for the presence of defectives. In the strict model of group testing, the goal is to identify all defectives if at most d defectives exist, and otherwise to report that more than d defectives are present. If tests are time-consuming, they should be performed in a small constant number s of stages of parallel tests. It is known that a test number O(dlogn), which is optimal up to a constant factor, can be achieved already in s=2 stages. Here we study two aspects of group testing that have not found major attention before. (1) Asymptotic bounds on the test number do not yet lead to optimal strategies for specific n,d,s. Especially for small n we show that randomized strategies significantly save tests on average, compared to worst-case deterministic results. Moreover, the only type of randomness needed is a random permutation of the elements. We solve the problem of constructing optimal randomized strategies for strict group testing completely for the case when d=1 and s≤2. A byproduct of our analysis is that optimal deterministic strategies for strict group testing for d=1 need at most 2 stages. (2) Usually, an element may participate in several pools within a stage. However, when the elements are indivisible objects, every element can belong to at most one pool at the same time. For group testing with disjoint simultaneous pools we show that Θ(sd(n/d)^1/s ) tests are sufficient and necessary. While the strategy is simple, the challenge is to derive tight lower bounds for different s and different ranges of d versus n.     

Birth and growth of multicyclic components in random hypergraphs

Define an ?-component to be a connected b-uniform hypergraph with k edges and k(b−1)−? vertices. In this paper, we investigate the growth of size and complexity of connected components of a random hypergraph process. We prove that the expected number of creations of ?-components during a random hypergraph process tends to 1 as b is fixed and ? tends to infinity with the total number of vertices n while remaining ?=o(n^1/3). We also show that the expected number of vertices that ever belong to an ?-component is ∼12^1/3?^1/3n^2/3(b−1)^−1/3. We prove that the expected number of times hypertrees are swallowed by ?-components is ∼2^1/33^−1/3n^1/3?^−1/3(b−1)^−5/3. It follows that with high probability the largest ?-component during the process is of size of order O(?^1/3n^2/3(b−1)^−1/3). Our results give insight into the size of giant components inside the phase transition of random hypergraphs and generalize previous results about graphs.     

Boolean-width of graphs

We introduce the graph parameter boolean-width, related to the number of different unions of neighborhoods-Boolean sums of neighborhoods-across a cut of a graph. For many graph problems, this number is the runtime bottleneck when using a divide-and-conquer approach. For an n-vertex graph given with a decomposition tree of boolean-width k, we solve Maximum Weight Independent Set in time O(n²k2^2k) and Minimum Weight Dominating Set in time O(n²+nk2^3k). With an additional n² factor in the runtime, we can also count all independent sets and dominating sets of each cardinality.Boolean-width is bounded on the same classes of graphs as clique-width. boolean-width is similar to rank-width, which is related to the number of GF(2)-sums of neighborhoods instead of the Boolean sums used for boolean-width. We show for any graph that its boolean-width is at most its clique-width and at most quadratic in its rank-width. We exhibit a class of graphs, the Hsu-grids, having the property that a Hsu-grid on Θ(n²) vertices has boolean-width Θ(logn) and rank-width, clique-width, tree-width, and branch-width Θ(n).     

The lower bounds on the second order nonlinearity of three classes of Boolean functions with high nonlinearity

The rth order nonlinearity of Boolean functions is an important cryptographic criterion associated with some attacks on stream and block ciphers. It is also very useful in coding theory, since it is related to the covering radii of Reed-Muller codes. This paper tightens the lower bounds of the second order nonlinearity of three classes of Boolean functions in the form f(x)=tr(x^d) in n variables, where (1) d=2^m+1+3 and n=2m, or (2) , n=2m and m is odd, or (3) d=2^2r+2^r+1+1 and n=4r.     

Maximum number of edges joining vertices on a cube

Let E_d(n) be the number of edges joining vertices from a set of n vertices on a d-dimensional cube, maximized over all such sets. We show that E_d(n)=∑_i=0^r−1(l_i/2+i)2^l_i, where r and l₀>l₁>?>l_r−1 are nonnegative integers defined by n=∑_i=0^r−12^l_i.     

Solving the Euclidean bottleneck matching problem byk-relative neighborhood graphs

Given a set of pointsV in the plane, the Euclidean bottleneck matching problem is to match each point with some other point such that the longest Euclidean distance between matched points, resulting from this matching, is minimized. To solve this problem, we definek-relative neighborhood graphs, (kRNG) which are derived from Toussaint's relative neighborhood graphs (RNG). Two points are calledk-relative neighbors if and only if there are less thank points ofV which are closer to both of the two points than the two points are to each other. AkRNG is an undirected graph (V,E _r ^k ) whereE _r ^k is the set of pairs of points ofV which arek-relative neighbors. We prove that there exists an optimal solution of the Euclidean bottleneck matching problem which is a subset ofE _r ¹⁷ . We also prove that ¦E _r ^k ¦ < 18kn wheren is the number of points in setV. Our algorithm would construct a 17RNG first. This takesO(n ²) time. We then use Gabow and Tarjan's bottleneck maximum cardinality matching algorithm for general graphs whose time-complexity isO((n logn)^0.5 m), wherem is the number of edges in the graph, to solve the bottleneck maximum cardinality matching problem in the 17RNG. This takesO(n ^1.5 log^0.5 n) time. The total time-complexity of our algorithm for the Euclidean bottleneck matching problem isO(n ² +n ^1.5 log^0.5 n).     

Optimal Routing in a Small-World Network

Substantial research has been devoted to the modelling of the small-world phenomenon that arises in nature as well as human society. Earlier work has focused on the static properties of various small-world models. To examine the routing aspects, Kleinberg proposes a model based on a d-dimensional toroidal lattice with long-range links chosen at random according to the d-harmonic distribution. Kleinberg shows that, by using only local information, the greedy routing algorithm performs in O（lg^2 n） expected number of hops. We extend Kleinberg＇s small-world model by allowing each node x to have two more random links to nodes chosen uniformly and randomly within （lg n）2/d Manhattan distance from x. Based on this extended model, we then propose an oblivious algorithm that can route messages between any two nodes in O（lg n） expected number of hops. Our routing algorithm keeps only O（（lgn）β＋1） bits of information on each node, where 1 〈 β 〈 2, thus being scalable w.r.t, the network size. To our knowledge, our result is the first to achieve the optimal routing complexity while still keeping a poly-logarithmic number of bits of information stored on each node in the small-world networks.     

Two-layer channel routing with vertical unit-length overlap

We show that anyn-net 2-terminal channel routing problem of densityd can be wired on a two-layer grid of widthw =d +O(d ^2/3) when vertical wire segments are allowed to overlap for a distance of length 1. This is a considerable asymptotic improvement over the best known, and optimal, channel width of 2d-1 for models in which no vertical overlap is allowed [RBM, PL]. Our result also improves the 3d/2+O(1) channel width achieved by a recent algorithm [G] for the same vertical overlap model. The algorithm presented in this paper produces at most 4 overlaps of unit length between any two nets, usesO(n) contacts, and can be implemented to run inO(nd ^2/3) time. We also generalize the algorithm to multi-terminal channel routing problems for which our algorithm uses a width ofw = 2d +O(d ^2/3).     

On measuring the distance between histograms

A distance measure between two histograms has applications in feature selection, image indexing and retrieval, pattern classification and clustering, etc. We propose a distance between sets of measurement values as a measure of dissimilarity of two histograms. The proposed measure has the advantage over the traditional distance measures regarding the overlap between two distributions; it takes the similarity of the non-overlapping parts into account as well as that of overlapping parts. We consider three versions of the univariate histogram, corresponding to whether the type of measurement is nominal, ordinal, and modulo and their computational time complexities are Θ(b), Θ(b) and O(b²) for each type of measurements, respectively, where b is the number of levels in histograms.