Narrow Results

We consider the problem of scattering n robots in a two dimensional continuous space. As this problem is impossible to solve in a deterministic manner, all solutions must be probabilistic. We investigate the amount of randomness (that is, the number of random bits used by the robots) that is required to achieve scattering.

We first prove that n log n random bits are necessary to scatter n robots in any setting. Also, we give a sufficient condition for a scattering algorithm to be random bit optimal. As it turns out that previous solutions for scattering satisfy our condition, they are hence proved random bit optimal for the scattering problem.

Then, we investigate the time complexity of scattering when strong multiplicity detection is not available. We prove that such algorithms cannot converge in constant time in the general case and in o(log log n) rounds for random bits optimal scattering algorithms. However, we present a family of scattering algorithms that converge as fast as needed without using multiplicity detection. Also, we put forward a specific protocol of this family that is random bit optimal (O(n log n) random bits are used) and time optimal (O(log log n) rounds are used). This improves the time complexity of previous results in the same setting by a log n factor.

Aside from characterizing the random bit complexity of mobile robot scattering, our study also closes the time complexity gap with and without strong multiplicity detection (that is, O(1) time complexity is only achievable when strong multiplicity detection is available, and it is possible to approach a constant value as desired otherwise).

We study the computational complexity of computing optimal solutions (the solutions themselves, not just their cost) for NP optimization problems where the costs of feasible solutions are bounded above by a polynomial in the length of their instances (we simply denote by NPOP such an NP optimization problem). It is of particular interest to find a computational structure (or equivalently, a complexity class) which. captures that complexity, if we consider the problems of computing optimal solutions for NPOP’s as a class of functions giving those optimal solutions. In this paper, we will observe that the class of functions computable in polynomial-time with one free evaluation of unbounded parallel queries to NP oracle sets, captures that complexity. We first show that for any NPOP Π, there exists a polynomial-time bounded randomized algorithm which, given an instance of Π, uses one free evaluation of parallel queries to an NP oracle set and outputs some optimal solution of the instance with very high probability. We then show that for several natural NPOP’s, any function giving those optimal solutions is at least as computationally hard as all functions in . To show the hardness results, we introduce a property of NPOP’s, called paddability, and we show a general result that if Π is a paddable NPOP and its associated decision problem is NP-hard, then all functions in are computable in polynomial-time with one free evaluation of an arbitrary function giving optimal solutions for instances of Π. The hardness results are applications of this general result. Among the NPOP’s, we include MAXIMUM CLIQUE, MINIMUM COLORING, LONGEST PATH, LONGEST CYCLE, 0–1 TRAVELING SALESPERSON, and 0–1 INTEGER PROGRAMMING.

In this paper, we propose a randomized scheduling algorithm on a fully connected homogeneous multiprocessor environment. This is a randomized version of our earlier algorithm in which we used priority of modules that was dependent on the computation and the communication times associated with the modules. First we propose a generalization of our earlier scheduling algorithm with restricted number of clusters to reduce the time complexity. Then we apply randomization to the generalized algorithm and demonstrate its superiority over our previous work. We show the complexity of our proposed algorithm as O(ab |V| (|V|+|E|) log (|V|+|E|)). Here a is the number of randomization steps, and b is a limit on the number of clusters formed. If we use a and b as constants, then this gives a better complexity in comparison with the complexity of our previous algorithm that was O(|V|²(|V|+|E|) log (|V|+|E|)). In comparison with our previous work we get a performance improvement of up to 6.63% and a performance improvement of up to 12.56% when compared with Sarkar's Edge Zeroing algorithm.

Randomization is a technique to improve efficiency and computability of distributed computing. In this paper, we investigate fault tolerance of distributed computing against faults of random number generators. We introduce an RNG (Random Number Generator)-fault as a new class of faults; a random number generator on an RNG-faulty process outputs the same number deterministically. This paper is the first work that considers faults of randomness in distributed computing.

We investigate the role of randomization by observing the impact of RNG-faults on performance of a self-stabilizing token circulation algorithm on unidirectional n-node ring networks. In the analysis, we assume there exist n_f (0 ≤ n_f ≤ n−1) RNG-faulty nodes and each RNG-faulty node always transfers a token to the next node. Our results are threefold: (1) We derive the upper bound on the expected convergence time in the case of n_f = n − 1. (2) Our simulation result shows that the expected convergence time is maximum when n_f = n − 1. (3) We derive the expected token circulation time for each n_f (0 ≤ n_f ≤ n − 1).

The LOCAL(A, B) randomized task scheduling algorithm is proposed for fully connected multiprocessors. It combines two given task scheduling algorithms (A, and B) using local neighborhood search to give a hybrid of the two given algorithms. Objective is to show that such type of hybridization can give much better performance results in terms of parallel execution times. Two task scheduling algorithms are selected: DSC (Dominant Sequence Clustering as algorithm A), and CPPS (Cluster Pair Priority Scheduling as algorithm B) and a hybrid is created (the LOCAL(DSC, CPPS) or simply the LOCAL task scheduling algorithm). The LOCAL task scheduling algorithm has time complexity O(|V||E|(|V |+|E|)), where V is the set of vertices, and E is the set of edges in the task graph. The LOCAL task scheduling algorithm is compared with six other algorithms: CPPS, DCCL (Dynamic Computation Communication Load), DSC, EZ (Edge Zeroing), LC (Linear Clustering), and RDCC (Randomized Dynamic Computation Communication). Performance evaluation of the LOCAL task scheduling algorithm shows that it gives up to 80.47 % improvement of NSL (Normalized Schedule Length) over other algorithms.

We propose a self-stabilizing algorithm for computing a maximal matching in an anonymous network. The complexity is O(²) moves with high probability, under the adversarial distributed daemon. Among all adversarial distributed daemons and with the anonymous assumption, our algorithm provides the best known complexity. Moreover, the previous best known algorithm working under the same daemon and using identity has a O(m) complexity leading to the same order of growth than our anonymous algorithm. Finally, we do not make the common assumption that a node can determine whether one of its neighbors points to it or to another node, and still we present a solution with the same asymptotic behavior.

An asynchronous, CRCW PRAM (or APRAM) algorithm for linked list ranking, proposed by Martel and Subramonian, performs EO(n log log n) expected work employing processors. Motivated by their unique approach, this paper proposes two EREW list ranking algorithms – one deterministic and the other randomized. The deterministic algorithm performs in time using p processors, where n≥p log p. Thus, for p=O(n/log n), it requires O(log n log log n) time and O(n log log n) work. Although not work-optimal, this algorithm is very simple compared to the known work-optimal (deterministic) EREW algorithms for list ranking and has the added advantage of small constant factors in the time and space requirements. The randomized algorithm follows the same line of approach, but uses randomization in one step to decrease the time complexity, thus improving on the time complexity of the original algorithm. It requires expected time, and hence it is an EO(log n) expected time, work-optimal algorithm employing p=O(n/log n) processors. Furthermore, the randomized algorithm uses less space than the deterministic algorithm.

We describe a randomized parallel algorithm to solve the single function coarsest partition problem. The algorithm runs in O(log n) time using O(n) operations with high probability on the Priority CRCW PRAM. The previous best known algorithms run in O(log² n) time using O(n log² n) operations on the CREW PRAM and O(log n) time using O(n log log n) operations on the Arbitrary CRCW PRAM. The technique presented can be used to generate the Euler tour of a rooted tree optimally from the parent representation.

A set of n distinct points in the plane defines lines by joining each pair of distinct points. The median slope of these O(n²) lines was proposed by Theil as a robust estimator for the slope of the line of best fit for the points. We present a randomized algorithm for selecting the k-th smallest slope of such a set of lines which runs in expected O(n log n) time. An efficient implementation of the algorithm and practical experience with the algorithm are discussed.

For a polygon P, the bounded Voronoi diagram of P is a partition of P into regions assigned to the vertices of P. A point p inside P belongs to the region of a vertex v if and only if v is the closest vertex of P visible from p. We present a randomized algorithm that builds the bounded Voronoi diagram of a simple polygon in linear expected time. Among other applications, we can construct within the same time bound the generalized Delaunay triangulation of P and the minimal spanning tree on P’s vertices that is contained in P.

We give a practical and provably good Monte Carlo algorithm for approximating center points. Let P be a set of n points in R^d. A point c∈R^d is a β-center point of P if every closed halfspace containing c contains at least βn points of P. Every point set has a 1/(d+1)-center point; our algorithm finds an Ω(1/d²)-center point with high probability. Our algorithm has a small constant factor and is the first approximate center point algorithm whose complexity is subexponential in d. Moreover, it can be optimally parallelized to require O(log²d log log n) time. Our algorithm has been used in mesh partitioning methods and can be used in the construction of high breakdown estimators for multivariate datasets in statistics. It has the potential to improve results in practice for constructing weak ∊-nets. We derive a variant of our algorithm whose time bound is fully polynomial in d and linear in n, and show how to combine our approach with previous techniques to compute high quality center points more quickly.

We describe a robust, dynamic algorithm to compute the arrangement of a set of line segments in the plane, and its implementation. The algorithm is robust because, following Greene⁷ and Hobby,¹¹ it rounds the endpoints and intersections of all line segments to representable points, but in a way that is globally topologically consistent. The algorithm is dynamic because, following Mulmuley,¹⁶ it uses a randomized hierarchy of vertical cell decompositions to make locating points, and inserting and deleting line segments, efficient. Our algorithm is novel because it marries the robustness of the Greene and Hobby algorithms with Mulmuley's dynamic algorithm in a way that preserves the desirable properties of each.

The problem considered in this paper is: Given an integer k > 0 and a set P of n points in the plane each with a corresponding nonnegative weight, find a step function f with k steps that minimize the maximum weighted vertical distance between f and all the points in P. We present a randomized algorithm to solve the problem in O(n log n) expected running time. The bound is obviously optimal for the unsorted input. The previously best known algorithm runs in O(n log² n) worst-case time. Another merit of the algorithm is its simplicity. The algorithm is just a randomized implementation of Frederickson and Johnson's matrix searching technique, and it only exploits a simple data structure.