Randomized LU decomposition

Randomized algorithms play a central role in low rank approximations of large matrices. In this paper, the scheme of the randomized SVD is extended to a randomized LU algorithm. Several error bounds are introduced, that are based on recent results from random matrix theory related to subgaussian matrices. The bounds also improve the existing bounds of already known randomized SVD algorithm. The algorithm is fully parallelized and thus can utilize efficiently GPUs without any CPU–GPU data transfer. Numerical examples, which illustrate the performance of the algorithm and compare it to other decomposition methods, are presented.     

Resolvable even cycle decompositions of the tensor product of complete graphs

In this paper, we consider resolvable k-cycle decompositions (for short, k-RCD) of K_m×K_n, where × denotes the tensor product of graphs. It has been proved that the standard necessary conditions for the existence of a k-RCD of K_m×K_n are sufficient when k is even.     

Randomized and quantum algorithms yield a speed-up for initial-value problems

Quantum algorithms and complexity have recently been studied not only for discrete, but also for some numerical problems. Most attention has been paid so far to the integration and approximation problems, for which a speed-up is shown in many important cases by quantum computers with respect to deterministic and randomized algorithms on a classical computer. In this paper, we deal with the randomized and quantum complexity of initial-value problems. For this nonlinear problem, we show that both randomized and quantum algorithms yield a speed-up over deterministic algorithms. Upper bounds on the complexity in the randomized and quantum settings are shown by constructing algorithms with a suitable cost, where the construction is based on integral information. Lower bounds result from the respective bounds for the integration problem.     

A new approximation algorithm for the multilevel facility location problem

In this paper we propose a new integer programming formulation for the multilevel facility location problem and a novel 3-approximation algorithm based on LP-rounding. The linear program that we use has a polynomial number of variables and constraints, thus being more efficient than the one commonly used in the approximation algorithms for these types of problems.     

Decomposing tensors into frames

A symmetric tensor of small rank decomposes into a configuration of only few vectors. We study the variety of tensors for which this configuration is a unit norm tight frame.     

On randomized algorithms for the majority problem

In the majority problem, we are given n balls coloured black or white and we are allowed to query whether two balls have the same colour or not. The goal is to find a ball of majority colour in the minimum number of queries. The answer is known to be n−B(n) where B(n) is the number of 1’s in the binary representation of n. In this paper we study randomized algorithms for determining majority, which are allowed to err with probability at most ε. We show that any such algorithm must have expected running time at least . Moreover, we provide a randomized algorithm which shows that this result is best possible. These extend a result of De Marco and Pelc [G. De Marco, A. Pelc, Randomized algorithms for determining the majority on graphs, Combin. Probab. Comput. 15 (2006) 823-834].     

2p-cycle decompositions of some regular graphs and digraphs

In this paper, we consider $2k$-cycle decomposition of $K_m\times K_n$ and directed $2k$-cycle decompositions of ${(K_m°{\overline{K}}_n)}^1$ and ${(K_m\times K_n)}^1$, where $°$ and $\times$ denote the wreath product and tensor product of graphs, respectively. Using the results obtained here, we prove that for $m,n\ge 3$, the obvious necessary conditions for the existence of a $C_{2k}$-decomposition of $K_m\times K_n$ are sufficient whenever $k\in \{p,2^{?}\},$ where $p$ is a prime and $?\ge 2$. Also, we show that the necessary conditions for the existence of ${\overrightarrow{C}}_{2p}$-decompositions of ${(K_m°{\overline{K}}_n)}^1$ and ${(K_m\times K_n)}^1$ are sufficient whenever $p$ is a prime, where ${\overrightarrow{C}}_{2p}$ denotes the directed cycle of length $2p$.     

A survey of randomized algorithms for control synthesis and performance verification

In this paper, we present an overview of probabilistic techniques based on randomized algorithms for solving “hard’’ problems arising in performance verification and control of complex systems. This area is fairly recent, even though its roots lie in the robustness techniques for handling uncertain control systems developed in the 1980s. In contrast to these deterministic techniques, the main ingredient of the methods discussed in this survey is the use of probabilistic concepts. The introduction of probability and random sampling permits overcoming the fundamental tradeoff between numerical complexity and conservatism that lie at the roots of the worst-case deterministic methodology. The simplicity of implementation of randomized techniques may also help bridging the gap between theory and practical applications.     

Hamilton cycle decompositions of the tensor products of complete bipartite graphs and complete multipartite graphs

In this paper, it is shown that the tensor product of the complete bipartite graph, K_r,r,r≥2, and the regular complete multipartite graph, , is Hamilton cycle decomposable.     

Hamilton cycle decompositions of the tensor product of complete multipartite graphs

In this paper, tensor product of two regular complete multipartite graphs is shown to be Hamilton cycle decomposable. Using this result, it is immediate that the tensor product of two complete graphs with at least three vertices is Hamilton cycle decomposable thereby providing an alternate proof of this fact.     

Fault Tolerant Sorting—Theoretical and Empirical Analyses of the Randomized QuickMergesort Algorithm

This paper introduces a new paradigm in the design of sorting algorithms, viz., fault tolerance. Fault tolerance is an important concept in modern day computing and design workflows must accommodate this need. In general, there are a number of avenues for faults to occur and techniques to address the same; this paper focusses on only one source of faulty behavior, viz., process termination. Process termination, as a cause of faulty behavior, is important from the perspective of various applications in real-time scheduling. In order to measure the effectiveness of a fault tolerant protocol, it is necessary to define a suitable metric and analyze the performance of the protocol with respect to that metric. We measure the “unsortedness” of an array, as characterized by the number of inversion pairs that remain when the sorting algorithm (process) terminates. This paper proposes a new algorithm for sorting called the Randomized QuickMergesort (RQMS) algorithm. RQMS has a higher degree of fault tolerance than either Randomized Quicksort (RQS) or Mergesort (MS), in that fewer inversion pairs remain when it terminates. Likewise, RQMS has a lower comparison overhead than RQS and is more space-efficient than MS. Our empirical analysis, which was conducted over a wide variety of distributions, conclusively establishes that RQMS is the algorithm of choice, when fault tolerance is paramount in the application. This research was supported in part by the Air Force Office of Scientific Research under Contract FA9550-06-1-0050.     

On the Nyström and Column-Sampling Methods for the Approximate Principal Components Analysis of Large Datasets

In this article, we analyze approximate methods for undertaking a principal components analysis (PCA) on large datasets. PCA is a classical dimension reduction method that involves the projection of the data onto the subspace spanned by the leading eigenvectors of the covariance matrix. This projection can be used either for exploratory purposes or as an input for further analysis, for example, regression. If the data have billions of entries or more, the computational and storage requirements for saving and manipulating the design matrix in fast memory are prohibitive. Recently, the Nyström and column-sampling methods have appeared in the numerical linear algebra community for the randomized approximation of the singular value decomposition of large matrices. However, their utility for statistical applications remains unclear. We compare these approximations theoretically by bounding the distance between the induced subspaces and the desired, but computationally infeasible, PCA subspace. Additionally we show empirically, through simulations and a real data example involving a corpus of emails, the trade-off of approximation accuracy and computational complexity.     

Non-independent randomized rounding and coloring

We propose an advanced randomized coloring algorithm for the problem of balanced colorings of hypergraphs (discrepancy problem). Instead of independently coloring the vertices with a random color, we try to use structural information about the hypergraph in the design of the random experiment by imposing suitable dependencies. This yields colorings having smaller discrepancy. We also obtain more information about the coloring, or, conversely, we may enforce the random coloring to have special properties. There are some algorithmic advantages as well.We apply our approach to hypergraphs of d-dimensional boxes and to finite geometries. Among others results, we gain a factor 2^d/2 decrease in the discrepancy of the boxes, and reduce the number of random bits needed to generate good colorings for the geometries down to (from n). The latter also speeds up the corresponding derandomization by a factor of .     

On Approximate Range Counting and Depth

We improve the previous results by Aronov and Har-Peled (SODA’05) and Kaplan and Sharir (SODA’06) and present a randomized data structure of O(n) expected size which can answer 3D approximate halfspace range counting queries in expected time, where k is the actual value of the count. This is the first optimal method for the problem in the standard decision tree model; moreover, unlike previous methods, the new method is Las Vegas instead of Monte Carlo. In addition, we describe new results for several related problems, including approximate Tukey depth queries in 3D, approximate regression depth queries in 2D, and approximate linear programming with violations in low dimensions. A preliminary version of this paper appeared in Proc. 23rd Sympos. Comput. Geom., pp. 337–343, 2007. Work of the second author was supported by NSERC.     

Optimal algorithms for page migration in dynamic networks

We present an extension of a classical data management subproblem, the page migration. The problem is investigated in dynamic networks, where costs of communication between different nodes may change with time. We construct asymptotically optimal online algorithms for this problem, both in deterministic and randomized scenarios.     

Stable routing under the Spanning Tree Protocol

The Spanning Tree Protocol routes traffic on shortest path trees. If some edges fail, the traffic has to be rerouted consequently, setting up alternative trees. In this paper we design efficient algorithms to compute polynomial-size integer weights so as to enforce the following stability property: if q=O(1) edges fail, traffic demands that are not affected by the failures are not redirected. Stability is a goal pursued by network operators in order to minimize transmission delays due to the restoration process.