In the field of online algorithms paging is one of the most studied problems. For randomized paging algorithms a tight bound of H (k) on the competitive ratio has been known for decades, yet existing algorithms matchi...
详细信息
ISBN:
(纸本)9783642291159
In the field of online algorithms paging is one of the most studied problems. For randomized paging algorithms a tight bound of H (k) on the competitive ratio has been known for decades, yet existing algorithms matching this bound have high running times. We present a new randomized paging algorithm OnlineMin that has optimal competitiveness and allows fast implementations. In fact, if k pages fit in internal memory the best previous solution required O(k (2)) time per request and O(k) space. We present two implementations of OnlineMin which use O(k) space, but only O(logk) worst case time and O(logk/loglogk) worst case time per page request respectively.
Boarding or holding in the Emergency Department (ED) reduces capacity of the ED and delays patients from receiving specialized care. Estimating accurately the number of admissions from the ED can help determine approp...
详细信息
ISBN:
(纸本)9780769549132;9781467346511
Boarding or holding in the Emergency Department (ED) reduces capacity of the ED and delays patients from receiving specialized care. Estimating accurately the number of admissions from the ED can help determine appropriate level of staffing to reduce holding. We propose a randomized non-linear regression algorithm, RT-KGERS, to estimate the number of admissions a week in advance. We also devise features based on cyclical patterns found with a Fast Fourier Transform analysis on the hospital admission data. We evaluate the accuracy and efficiency of RT-KGERS and three existing algorithms in a dataset provided by a local hospital. We then compare our features with related features. Initial experimental results from RT-KGERS encouraged the hospital and us to conduct a live trial study which yielded similar levels of accuracy using RT-KGERS and the six features we devised.
Gaussian elimination is a key technique for solving dense, non-symmetric systems of linear equations. Pivoting is used to ensure numerical stability but can introduce significant overheads. We propose replacing pivoti...
详细信息
ISBN:
(纸本)9780738110509
Gaussian elimination is a key technique for solving dense, non-symmetric systems of linear equations. Pivoting is used to ensure numerical stability but can introduce significant overheads. We propose replacing pivoting with recursive butterfly transforms (RBTs) and iterative refinement. RBTs use an FFT-like structure and randomized elements to provide an efficient, two-sided preconditioner for factoring. This approach was implemented and tested using Software for Linear Algebra Targeting Exascale (SLATE). In numerical experiments, our implementation was more robust than Gaussian elimination with no pivoting (GENP) but failed to solve all the problems solvable with Gaussian elimination with partial pivoting (GEPP). Furthermore, the proposed solver was able to outperform GEPP when distributed on GPU-accelerated nodes.
A trend in machine learning is the application of existing algorithms to ever-larger datasets. Support Vector Machines (SVM) have been shown to be very effective, but have been difficult to scale to large-data problem...
详细信息
ISBN:
(纸本)9780769549132;9781467346511
A trend in machine learning is the application of existing algorithms to ever-larger datasets. Support Vector Machines (SVM) have been shown to be very effective, but have been difficult to scale to large-data problems. Some approaches have sought to scale SVM training by approximating and parallelizing the underlying quadratic optimization problem. This paper pursues a different approach. Our algorithm, which we call Sampled SVM, uses an existing SVM training algorithm to create a new SVM training algorithm. It uses randomized data sampling to better extend SVMs to large data applications. Experiments on several datasets show that our method is faster than and comparably accurate to both the original SVM algorithm it is based on and the Cascade SVM, the leading data organization approach for SVMs in the literature. Further, we show that our approach is more amenable to parallelization than Cascade SVM.
In this paper we introduce a novel matrix decomposition algorithm termed Subspace-Orbit randomized Singular Value Decomposition (SOR-SVD). It is computed by using random sampling techniques to give a low-rank approxim...
详细信息
ISBN:
(纸本)9789082797015
In this paper we introduce a novel matrix decomposition algorithm termed Subspace-Orbit randomized Singular Value Decomposition (SOR-SVD). It is computed by using random sampling techniques to give a low-rank approximation to an input matrix. Given a large and dense data matrix of size mxn, SOR-SVD requires a few passes through data to compute a rank-k approximation in O(mnk) floating-point operations. Furthermore, SOR-SVD can utilize advanced computer architectures and, as a result, it can be optimized for maximum efficiency. The SOR-SVD algorithm is simple, accurate, and provably correct, and outperforms previously reported techniques in terms of accuracy and efficiency.
Recently, Charikar et al. investigated the problem of evaluating AND/OR trees, with non-uniform costs on its leaves, from the perspective of the competitive analysis. For an AND/OR tree T they presented a mu(T)-compet...
详细信息
ISBN:
(纸本)9783540212362
Recently, Charikar et al. investigated the problem of evaluating AND/OR trees, with non-uniform costs on its leaves, from the perspective of the competitive analysis. For an AND/OR tree T they presented a mu(T)-competitive deterministic polynomial time algorithm, where mu(T) is the number of leaves that must be read, in the worst case, in order to determine the value of T. Furthermore, they proved that mu(T) is a lower bound on the deterministic competitiveness, which assures the optimality of their algorithm. The power of randomization in this context has remained as an open question. Here, we take a step towards solving this problem by presenting a 5/6 mu(T)-competitive randomized polynomial time algorithm. This contrasts with the best known lower bound mu(T)/2. (c) 2008 Elsevier B.V. All rights reserved.
We propose an approach for analyzing the average performance of a given (randomized) local search algorithm, for a constraint satisfaction problem. Our approach consists of two approximations. Using a randomized algor...
详细信息
ISBN:
(纸本)3540201033
We propose an approach for analyzing the average performance of a given (randomized) local search algorithm, for a constraint satisfaction problem. Our approach consists of two approximations. Using a randomized algorithm for LDPCC decoding, we experimentally investigate the reliability of these approximations and show that they could be used as a tool for analyzing the average performance of randomized local search algorithms.
This paper addresses the issues of conservativeness and computational complexity of probabilistie robustness analysis. The authors solve both issues by defining a new sampling strategy and robustness measure. The new ...
详细信息
This paper addresses the issues of conservativeness and computational complexity of probabilistie robustness analysis. The authors solve both issues by defining a new sampling strategy and robustness measure. The new measure is shown to be much less conservative than the existing one. The new sampling strategy enables the definition of efficient hierarchical sample reuse algorithms that reduce significantly the computational complexity and make it independent of the dimension of the uncertainty space. Moreover, the authors show that there exists a one to one correspondence between the new and the existing robustness measures and provide a computationally simple algorithm to derive one from the other.
The random priority (RP) mechanism is a popular way to allocate n objects to n agents with strict ordinal preferences over the objects. In the RP mechanism, an ordering over the agents is selected uniformly at random;...
详细信息
The random priority (RP) mechanism is a popular way to allocate n objects to n agents with strict ordinal preferences over the objects. In the RP mechanism, an ordering over the agents is selected uniformly at random;the first agent is then allocated his most-preferred object, the second agent is allocated his most-preferred object among the remaining ones, and so on. The outcome of the mechanism is a bi-stochastic matrix in which entry (i, a) represents the probability that agent i is given object a. It is shown that the problem of computing the RP allocation matrix is #P-complete. Furthermore, it is NP-complete to decide if a given agent i receives a given object a with positive probability under the RP mechanism, whereas it is possible to decide in polynomial time whether or not agent i receives object a with probability 1. The implications of these results for approximating the RP allocation matrix as well as on finding constrained Pareto optimal matchings are discussed.
We further develop the study of testing graph properties as initiated by Goldreich, Goldwasser and Ron. Loosely speaking, given an oracle access to a graph, we wish to distinguish the case when the graph has a pre-det...
详细信息
We further develop the study of testing graph properties as initiated by Goldreich, Goldwasser and Ron. Loosely speaking, given an oracle access to a graph, we wish to distinguish the case when the graph has a pre-determined property from the case when it is "far" from having this property. Whereas they view graphs as represented by their adjacency matrix and measure the distance between graphs as a fraction of all possible vertex pairs, we view graphs as represented by bounded-length incidence lists and measure the distance between graphs as a fraction of the maximum possible number of edges. Thus, while the previous model is most appropriate for the study of dense graphs, our model is most appropriate for the study of bounded-degree graphs. In particular, we present randomized algorithms for testing whether an unknown bounded-degree graph is connected, k-connected (for k > 1), cycle-free and Eulerian. Our algorithms work in time polynomial in Ile, always accept the graph when it has the tested property, and reject with high probability if the graph is E-far from having the property. For example, the 2-connectivity algorithm rejects (with high probability) any N-vertex d-degree graph for which more than epsilon dN edges need to be added in order to make the graph 2-edge-connected. In addition we prove lower bounds of Omega(rootN) on the query complexity of testing algorithms for the bipartite and expander properties.
暂无评论