We present an intelligent workload factoring service for enterprise customers to make the best use of public cloud services along with their privately-owned (legacy) data centers. It enables federation between on- and...
详细信息
ISBN:
(纸本)9781424449309
We present an intelligent workload factoring service for enterprise customers to make the best use of public cloud services along with their privately-owned (legacy) data centers. It enables federation between on- and off-premise infrastructures for hosting Internet-based applications, and the intelligence lies in the explicit segregation of base workload and trespassing workload, the two naturally different components composing the application workload. The core technology of the intelligent workload factoring service is a fast frequent data item detection algorithm, which enables factoring incoming requests not only on volume but also on data content, upon changing application data popularity.
We consider the problem of efficiently designing sets (codes) of equal-length DNA strings (words) that satisfy certain combinatorial constraints. This problem has numerous motivations including DNA self-assembly and D...
详细信息
We consider the problem of efficiently designing sets (codes) of equal-length DNA strings (words) that satisfy certain combinatorial constraints. This problem has numerous motivations including DNA self-assembly and DNA computing. Previous work has extended results from coding theory to obtain bounds on code size for new biologically motivated constraints and has applied heuristic local search and genetic algorithm techniques for code design. This article proposes a natural optimization formulation of the DNA code design problem in which the goal is to design n strings that satisfy a given set of constraints while minimizing the length of the strings. For multiple sets of constraints, we provide simple randomized algorithms that run in time polynomial in n and any given constraint parameters, and output strings of length within a constant factor of the optimal with high probability. To the best of our knowledge, this work is the first to consider this type of optimization problem in the context of DNA code design.
It has been suggested recently that the uncertainty randomization approach may offer numerical advantages when applied to robust control problems. This paper investigates new possibilities which this approach may offe...
详细信息
It has been suggested recently that the uncertainty randomization approach may offer numerical advantages when applied to robust control problems. This paper investigates new possibilities which this approach may offer in relation to the robust stability and control of stochastic systems governed by uncertain discrete-state Markov processes.
In this paper, we consider the design of globally asymptotically stabilizing state-dependent switching rules for multimodal systems, first restricting attention to linear time-invariant (LTI) systems with only two sta...
详细信息
In this paper, we consider the design of globally asymptotically stabilizing state-dependent switching rules for multimodal systems, first restricting attention to linear time-invariant (LTI) systems with only two states for the switch, and then generalizing the results to multimodal LTI systems and to nonlinear systems. In all cases, the systems considered do not allow the construction of a single quadratic Lyapunov function and, hence, fall in the class of problems that require multiple Lyapunov functions and thus are nonconvex. To address the challenge of nonconvexity, we introduce probabilistic algorithms, and prove their probability-one convergence under a new notion of convergence. Then, to reduce complexity, we develop modified versions of the algorithm. We also present a class of more general nonconvex problems to which this approach can be applied. The results are illustrated using two- and three-dimensional systems with multiple switch states.
In this work we present an in-depth study of randomized relaxed K-d trees. It covers two fundamental aspects: the randomized algorithms that allow to preserve the random properties of relaxed K-d trees and the mathema...
详细信息
In this work we present an in-depth study of randomized relaxed K-d trees. It covers two fundamental aspects: the randomized algorithms that allow to preserve the random properties of relaxed K-d trees and the mathematical analysis of the expected performance of these algorithms. In particular, we describe randomized update algorithms for K-d trees based on the split and join algorithms of Duch et al. [1998]. We carry out an analysis of the expected cost of all these algorithms, using analytic combinatorics techniques. We show that the average cost of split and join is of the form zeta(K) . n(phi(K)) + o(n(phi(K))), with 1 <= phi(K) < 1.561552813, and we give explicit formulae for both zeta(K) and phi(K). These results on the average performance of split and join imply that the expected cost of an insertion or a deletion is Theta(n(phi(K)-1)) when K > 2 and Theta(log n) for K = 2.
Finding the convex hull of n points in the plane requires O(n log n) time in general. In Devroye and Toussaint [1993] and Golin et al. [2002] the problem of computing the convex hull of the intersection points of n li...
详细信息
Finding the convex hull of n points in the plane requires O(n log n) time in general. In Devroye and Toussaint [1993] and Golin et al. [2002] the problem of computing the convex hull of the intersection points of n lines was considered, where the lines are chosen randomly according to two various models. In both models, linear-time algorithms were developed. Here we improve the results of Devroye and Toussaint [1993] by giving a universal algorithm for a wider range of distributions.
In this paper a distributed clock synchronization algorithm is proposed. The algorithm requires gossip asynchronous communication between the nodes of the network, and because of its proportional-integral (PI) structu...
详细信息
In this paper a distributed clock synchronization algorithm is proposed. The algorithm requires gossip asynchronous communication between the nodes of the network, and because of its proportional-integral (PI) structure it is able to compensate both initial offsets and different clock speeds. Convergence of the algorithm is proved and analysed with respect to the controller parameter, while scalability issues are addressed by simulations.
Search engines utilize numerous measures to rank the webpages in the search results. At Google, the so-called PageRank algorithm provides crucial information by quantifying the importance of webpages. The PageRank val...
详细信息
Search engines utilize numerous measures to rank the webpages in the search results. At Google, the so-called PageRank algorithm provides crucial information by quantifying the importance of webpages. The PageRank values are considered to be objective since the algorithm requires only the data of the web link structure. In this paper, we first introduce the original PageRank algorithm and give a brief overview of the distributed randomized approach recently proposed by the authors. Then, we consider the problem of computing the variation in the PageRank values that can be caused by erroneous data in the web structure when some links are fragile. An efficient (centralized) algorithm in the form of linear programming is proposed. This approach employs results from the field of interval matrices. Numerical examples are given to verify the effectiveness of the approach.
Classical problems of sorting and searching assume an underlying linear ordering of the objects being compared. In this paper, we study these problems in the context of partially ordered sets, in which some pairs of o...
详细信息
Classical problems of sorting and searching assume an underlying linear ordering of the objects being compared. In this paper, we study these problems in the context of partially ordered sets, in which some pairs of objects are incomparable. This generalization is interesting from a combinatorial perspective, and it has immediate applications in ranking scenarios where there is no underlying linear ordering, e.g., conference submissions. It also has applications in reconstructing certain types of networks, including biological networks. Our results represent significant progress over previous results from two decades ago by Faigle and Turan. In particular, we present the first algorithm that sorts a width-w poset of size n with optimal query complexity O(n(w + logn)). We also describe a variant of Merge-sort with query complexity O(wn log (n/w)) and total complexity O(w~2n log (n/w)); an algorithm with the same query complexity was given by Faigle and Turan, but no efficient implementation of that algorithm is known. Both our sorting algorithms can be applied with negligible overhead to the more general problem of reconstructing transitive relations. We also consider two related problems: finding the minimal elements, and its generalization to finding the bottom k "levels", called the k-selection problem. We give efficient deterministic and randomized algorithms for finding the minimal elements with O(wn) query and total complexity. We provide matching lower bounds for the query complexity up to a factor of 2 and generalize the results to the k-selection problem. Finally, we present efficient algorithms for computing a linear extension of a poset and computing the heights of all elements.
We propose a randomized algorithm aimed at reaching, in finite time, exact consensus among a set of agents that are linked though a connected, possibly time-varying, graph. The information exchanged among neighboring ...
详细信息
ISBN:
(纸本)9781424445233
We propose a randomized algorithm aimed at reaching, in finite time, exact consensus among a set of agents that are linked though a connected, possibly time-varying, graph. The information exchanged among neighboring agents is limited in size, by randomly selecting the content from an agent internal state. The time needed to reach the agreement is a random variable, whose empirical cumulative distribution function is utilized to determine a stopping rule that ensures consensus is achieved with a prescribed confidence level. Simulation results show that the consensus-reaching time obtained with a prescribed confidence level compares relatively well to local-averaging-based algorithms. The algorithm is shown to be robust, to some extent, to lossy communications and is demonstrated on a weapon-target assignment problem.
暂无评论