Improved parallel approximation of a class of integer programming problems
From MaRDI portal
Publication:676274
DOI10.1007/BF02523683zbMath0869.68054MaRDI QIDQ676274
Publication date: 4 September 1997
Published in: Algorithmica (Search for Journal in Brave)
68W15: Distributed algorithms
Related Items
On the parallel approximability of a subclass of quadratic programming., Improved algorithms via approximations of probability distributions, Parallel approximation to high multiplicity scheduling problemsVIAsmooth multi-valued quadratic programming
Cites Work
- Unnamed Item
- Unnamed Item
- Optima of dual integer linear programs
- Randomized rounding: A technique for provably good algorithms and algorithmic proofs
- Probabilistic construction of deterministic algorithms: approximating packing integer programs
- On the ratio of optimal integral and fractional covers
- Removing randomness in parallel computation without a processor penalty
- The probabilistic method yields deterministic parallel algorithms
- Improved algorithms via approximations of probability distributions
- Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Randomized algorithms and pseudorandom numbers
- Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
- Simple Constructions of Almost k-wise Independent Random Variables
- Simulating (log c n )-wise independence in NC
- The Ring Loading Problem
- Chernoff–Hoeffding Bounds for Applications with Limited Independence
- Fast Approximation Algorithms for Fractional Packing and Covering Problems
- A parallel approximation algorithm for positive linear programming
- Probability Inequalities for Sums of Bounded Random Variables
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
