Tight bounds for the cover time of multiple random walks

We study the cover time of multiple random walks on undirected graphs G=(V,E). We consider k parallel, independent random walks that start from the same vertex. The speed-up is defined as the ratio of the cover time of a single random walk to the cover time of these k random walks. Recently, Alon et al. (2008) [5] derived several upper bounds on the cover time, which imply a speed-up of Ω(k) for several graphs; however, for many of them, k has to be bounded by O(logn). They also conjectured that, for any 1?k?n, the speed-up is at most O(k) on any graph. We prove the following main results:

•

We present a new lower bound on the speed-up that depends on the mixing time. It gives a speed-up of Ω(k) on many graphs, even if k is as large as n.

•

We prove that the speed-up is O(klogn) on any graph. For a large class of graphs we can also improve this bound to O(k), matching the conjecture of Alon et al.

•

We determine the order of the speed-up for any value of 1?k?n on hypercubes, random graphs and degree restricted expanders. For d-dimensional tori with d>2, our bounds are tight up to logarithmic factors.

•

Our findings also reveal a surprisingly sharp threshold behaviour for certain graphs, e.g., the d-dimensional torus with d>2 and hypercubes: there is a value T such that the speed-up is approximately min{T,k} for any 1?k?n.

     

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.     

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.     

Clustering Large Graphs via the Singular Value Decomposition

We consider the problem of partitioning a set of m points in the n-dimensional Euclidean space into k clusters (usually m and n are variable, while k is fixed), so as to minimize the sum of squared distances between each point and its cluster center. This formulation is usually the objective of the k-means clustering algorithm (Kanungo et al. (2000)). We prove that this problem in NP-hard even for k = 2, and we consider a continuous relaxation of this discrete problem: find the k-dimensional subspace V that minimizes the sum of squared distances to V of the m points. This relaxation can be solved by computing the Singular Value Decomposition (SVD) of the m × n matrix A that represents the m points; this solution can be used to get a 2-approximation algorithm for the original problem. We then argue that in fact the relaxation provides a generalized clustering which is useful in its own right. Finally, we show that the SVD of a random submatrix—chosen according to a suitable probability distribution—of a given matrix provides an approximation to the SVD of the whole matrix, thus yielding a very fast randomized algorithm. We expect this algorithm to be the main contribution of this paper, since it can be applied to problems of very large size which typically arise in modern applications.     

Simulations among multidimensional turing machines

For all d ? 1 and all e >d, every deterministic multihead e-dimensional Turing machine of time complexity T(n) can be simulated on-line by a deterministic multihead d-dimensional Turing machine in time O(T(n)^1+1?d?1?(logT(n))⁰⁽¹⁾). This simulation almost achieves the known lower bound $\text{Ω(T(n)}{}^{\mathrm{1+1?}}\text{d?1?e)}$ on the time required. The simulation is interpreted in terms of dynamic embeddings among arrays with local access.     

A linear time algorithm for max-min length triangulation of a convex polygon

We consider the following planar max-min length triangulation problem: given a set of n points in the Euclidean plane, find a triangulation such that the length of the shortest edge in the triangulation is maximized. In this paper, a linear time algorithm is proposed for computing the max-min length triangulation of a set of points in convex position. In addition, an O(nlogn) time algorithm is proposed for computing the max-min length k-set triangulation of a set of points in convex position, where we are to compute a set of k vertices such that the max-min length triangulation on them is minimized over all possible k-set. We further show that the graph version of max-min length triangulation is NP-complete, and some common heuristics such as greedy algorithm are in general not able to give a bounded-ratio approximation to the max-min length triangulation.     

Diameter and Broadcast Time of Random Geometric Graphs in Arbitrary Dimensions

A random geometric graph (RGG) is defined by placing n points uniformly at random in [0,n ^1/d ] ^d , and joining two points by an edge whenever their Euclidean distance is at most some fixed r. We assume that r is larger than the critical value for the emergence of a connected component with Ω(n) nodes. We show that, with high probability (w.h.p.), for any two connected nodes with a Euclidean distance of $\omega (\frac{\log n}{r^{d-1}} )$ , their graph distance is only a constant factor larger than their Euclidean distance. This implies that the diameter of the largest connected component is Θ(n ^1/d /r) w.h.p. We also prove that the condition on the Euclidean distance above is essentially tight. We also analyze the following randomized broadcast algorithm on RGGs. At the beginning, only one node from the largest connected component of the RGG is informed. Then, in each round, each informed node chooses a neighbor independently and uniformly at random and informs it. We prove that w.h.p. this algorithm informs every node in the largest connected component of an RGG within Θ(n ^1/d /r+logn) rounds.     

Approximation Algorithms for the Class Cover Problem

We introduce the class cover problem, a variant of disk cover with forbidden regions, with applications to classification and facility location problems. We prove similar hardness results to disk cover. We then present a polynomial-time approximation algorithm for class cover that performs within a ln?n+1 factor of optimal, which is nearly tight under standard hardness assumptions. In the special case that the points lie in a d-dimensional space with Euclidean norm, for some fixed constant d, we obtain a polynomial time approximation scheme.     

Computing the relative neighborhood graph in the L1 and L∞ metrics

The Relative Neighborhood Graph (RNG) of a set of nk-dimensional points connects “relatively close” neighbors: two points are connected by an edge if they are at least as close to each other as to any other point. Toussaint recently investigated the properties of the RNG in the Euclidean metric and proposed algorithms for its computation. This note examines one of the open problems listed by Toussaint: the extension of the analysis to non-Euclidean metrics. It is shown that Bentley's range query data structures may be used to improve the speed of the best known RNG algorithm in the L_∞ (for k ? 2) and L₁ (for k = 2) metrics.     

Complete path embeddings in crossed cubes

Crossed cubes are popular variants of hypercubes. In this paper, we study path embeddings between any two distinct nodes in crossed cubes. We prove two important results in the n-dimensional crossed cube: (a) for any two nodes, all paths whose lengths are greater than or equal to the distance between the two nodes plus 2 can be embedded between the two nodes with dilation 1; (b) for any two integers n ? 2 and l with , there always exist two nodes x and y whose distance is l, such that no path of length l + 1 can be embedded between x and y with dilation 1. The obtained results are optimal in the sense that the dilations of path embeddings are all 1. The results are also complete, because the embeddings of paths of all possible lengths between any two nodes are considered.     

Optimal algorithms for some intersection radius problems

The intersection radius of a set ofn geometrical objects in ad-dimensional Euclidean space,E ^d , is the radius of the smallest closed hypersphere that intersects all the objects of the set. In this paper, we describe optimal algorithms for some intersection radius problems. We first present a linear-time algorithm to determine the smallest closed hypersphere that intersects a set of hyperplanes inE ^d , assumingd to be a fixed parameter. This is done by reducing the problem to a linear programming problem in a (d+1)-dimensional space, involving 2n linear constraints. We also show how the prune-and-search technique, coupled with the strategy of replacing a ray by a point or a line can be used to solve, in linear time, the intersection radius problem for a set ofn line segments in the plane. Currently, no algorithms are known that solve these intersection radius problems within the same time bounds.     

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

An interpretation of Mahalanobis distance in the dual space

Using the concept of a dual space, nk-dimensional vectors can be viewed as k points in an n-dimensional co-ordinate system. The relationships between the basic statistical properties of a k-variate sample and the geometrical properties of such a space are developed and the concept extended to two samples drawn from different populations, with derivation of the geometrical meaning of Mahalanobis distance. This geometrical approach provides valuable insight into why different feature subsets may or may not have high discriminatory potential, and shows that clustering in the dual space, or its subspaces, does not necessarily yield an effective feature selection technique.     

On using deterministic functions to reduce randomness in probabilistic algorithms

We show the existence of nonuniform schemes for the following sampling problem: Given a sample space with n points, an unknown set of size n/2, and s random points, it is possible to generate deterministically from them s + k points such that the probability of not hitting the unknown set is exponentially smaller in k than 2^−s. Tight bounds are given for the quality of such schemes. Explicit, uniform versions of these schemes could be used for efficiently reducing the error probability of randomized algorithms. A survey of known constructions (whose quality is very far from the existential result) is included.     

Acyclic and k-distance coloring of the grid

In this paper, we give a relatively simple though very efficient way to color the d-dimensional grid G(n₁,n₂,…,n_d) (with n_i vertices in each dimension 1?i?d), for two different types of vertex colorings: (1) acyclic coloring of graphs, in which we color the vertices such that (i) no two neighbors are assigned the same color and (ii) for any two colors i and j, the subgraph induced by the vertices colored i or j is acyclic; and (2) k-distance coloring of graphs, in which every vertex must be colored in such a way that two vertices lying at distance less than or equal to k must be assigned different colors. The minimum number of colors needed to acyclically color (respectively k-distance color) a graph G is called acyclic chromatic number of G (respectively k-distance chromatic number), and denoted a(G) (respectively χ_k(G)).The method we propose for coloring the d-dimensional grid in those two variants relies on the representation of the vertices of G_d(n₁,…,n_d) thanks to its coordinates in each dimension; this gives us upper bounds on a(G_d(n₁,…,n_d)) and χ_k(G_d(n₁,…,n_d)).We also give lower bounds on a(G_d(n₁,…,n_d)) and χ_k(G_d(n₁,…,n_d)). In particular, we give a lower bound on a(G) for any graph G; surprisingly, as far as we know this result was never mentioned before. Applied to the d-dimensional grid G_d(n₁,…,n_d), the lower and upper bounds for a(G_d(n₁,…,n_d)) match (and thus give an optimal result) when the lengths in each dimension are “sufficiently large” (more precisely, if ). If this is not the case, then these bounds differ by an additive constant at most equal to . Concerning χ_k(G_d(n₁,…,n_d)), we give exact results on its value for (1) k=2 and any d?1, and (2) d=2 and any k?1.In the case of acyclic coloring, we also apply our results to hypercubes of dimension d, H_d, which are a particular case of G_d(n₁,…,n_d) in which there are only 2 vertices in each dimension. In that case, the bounds we obtain differ by a multiplicative constant equal to 2.     

A study of fault tolerance in star graph

The bounds on f(n,k), the number of faulty nodes to make every (n−k)-dimensional substar Sn−k in an n-dimensional star network Sn, have been derived. The exact value for f(n,k) is determined when n is prime and k=2, or when n−2?k?n. For 2<k<n−2, a general method is presented to derive a set of faulty nodes which damage all Sn−k's in Sn.     

Embedding meshes into crossed cubes

Crossed cubes are important variants of hypercubes. In this paper, we consider embeddings of meshes in crossed cubes. The major research findings in this paper are: (1) For any integer n ? 1, a 2 × 2ⁿ⁻¹ mesh can be embedded in the n-dimensional crossed cube with dilation 1 and expansion 1. (2) For any integer n ? 4, two node-disjoint 4 × 2ⁿ⁻³ meshes can be embedded in the n-dimensional crossed cube with dilation 1 and expansion 2. The obtained results are optimal in the sense that the dilations of the embeddings are 1. The embedding of the 2 × 2ⁿ⁻¹ mesh is also optimal in terms of expansion because it has the smallest expansion 1.     

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 approximation algorithm for a bottleneck k-Steiner tree problem in the Euclidean plane

We study a bottleneck Steiner tree problem: given a set P={p₁,p₂,…,p_n} of n terminals in the Euclidean plane and a positive integer k, find a Steiner tree with at most k Steiner points such that the length of the longest edges in the tree is minimized. The problem has applications in the design of wireless communication networks. We give a ratio-1.866 approximation algorithm for the problem.     

Cellular automata with limited inter-cell bandwidth

A d-dimensional cellular automaton is a d-dimensional grid of interconnected interacting finite automata. There are models with parallel and sequential input modes. In the latter case, the distinguished automaton at the origin, the communication cell, is connected to the outside world and fetches the input sequentially. Often in the literature this model is referred to as an iterative array. In this paper, d-dimensional iterative arrays and one-dimensional cellular automata are investigated which operate in real and linear time and whose inter-cell communication bandwidth is restricted to some constant number of different messages independent of the number of states. It is known that even one-dimensional two-message iterative arrays accept rather complicated languages such as {a^p∣p prime} or {a²ⁿ∣n∈N} (H. Umeo, N. Kamikawa, Real-time generation of primes by a 1-bit-communication cellular automaton, Fund. Inform. 58 (2003) 421-435). Here, the computational capacity of d-dimensional iterative arrays with restricted communication is investigated and an infinite two-dimensional hierarchy with respect to dimensions and messages is shown. Furthermore, the computational capacity of the one-dimensional devices in question is compared with the power of two-way and one-way cellular automata with restricted communication. It turns out that the relations between iterative arrays and cellular automata are quite different from the relations in the unrestricted case. Additionally, an infinite strict message hierarchy for real-time two-way cellular automata is obtained as well as a very dense time hierarchy for k-message two-way cellular automata. Finally, the closure properties of one-dimensional iterative arrays with restricted communication are investigated and differences to the unrestricted case are shown as well.