𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Improved Algorithms via Approximations of Probability Distributions

✍ Scribed by Suresh Chari; Pankaj Rohatgi; Aravind Srinivasan

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
235 KB
Volume
61
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

We present two techniques for constructing sample spaces that approximate probability distributions. The first is a simple method for constructing the small-bias probability spaces introduced by Naor and Naor. We show how to efficiently combine this construction with the method of conditional probabilities to yield improved parallel algorithms for problems such as set discrepancy, finding large cuts in graphs, and finding large acyclic subgraphs. The second is a construction of small probability spaces approximating general independent distributions which are of smaller size than the constructions of Even, Goldreich, Luby, Nisan, and Velic kovic .

πŸ“œ SIMILAR VOLUMES

Improving interpretability in approximat
Improving interpretability in approximative fuzzy models via multiobjective evolutionary algorithms
✍ A.F. GΓ³mez-Skarmeta; F. JimΓ©nez; G. SΓ‘nchez πŸ“‚ Article πŸ“… 2007 πŸ› John Wiley and Sons 🌐 English βš– 830 KB

Current research lines in fuzzy modeling mostly tackle improving the accuracy in descriptive models and improving of the interpretability in approximative models. This article deals with the second issue, approaching the problem by means of multiobjective optimization in which accuracy and interpret

Design and Performance of Parallel and D
Design and Performance of Parallel and Distributed Approximation Algorithms for Maxcut
✍ Steven Homer; Marcus Peinado πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 327 KB

We develop and experiment with a new parallel algorithm to approximate the maximum weight cut in a weighted undirected graph. Our implementation starts with the recent (serial) algorithm of Goemans and Williamson for this problem. We consider several different versions of this algorithm, varying the

An Improved Approach for Estimating the
An Improved Approach for Estimating the Mean and Standard Deviation of a Subjective Probability Distribution
✍ HON-SHIANG LAU; AMY HING-LING LAU; YUE ZHANG πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 236 KB πŸ‘ 2 views

The literature oers many formulas for estimating the mean and standard deviation of a subjective probability distribution (a well-known example is the PERT formulas). This paper shows that some basic underlying assumptions behind most of these formulas are inappropriate; a more appropriate framework