Improved parallel approximation of a class of integer programming problems

DOI10.1007/BF02523683zbMATH Open0869.68054OpenAlexW2028457507MaRDI QIDQ676274FDOQ676274

Authors: Noga Alon, Aravind Srinivasan 

Publication date: 4 September 1997

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02523683

Recommendations

• scientific article; zbMATH DE number 2102778
• New approaches to covering and packing problems
• The probabilistic method yields deterministic parallel algorithms
• Parallel approximation algorithms by positive linear programming

zbMATH Keywords

derandomizationNC approximation algorithmsVLSI gate arrays

Mathematics Subject Classification ID

Distributed algorithms (68W15)

Cites Work

• Probability Inequalities for Sums of Bounded Random Variables
• On the ratio of optimal integral and fractional covers
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Simple Constructions of Almost k-wise Independent Random Variables
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• Chernoff–Hoeffding Bounds for Applications with Limited Independence
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• Title not available (Why is that?)
• A parallel approximation algorithm for positive linear programming
• Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• Title not available (Why is that?)
• Fast Approximation Algorithms for Fractional Packing and Covering Problems
• Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
• Removing randomness in parallel computation without a processor penalty
• The probabilistic method yields deterministic parallel algorithms
• Improved algorithms via approximations of probability distributions
• Simulating (log ^c n )-wise independence in NC
• Optima of dual integer linear programs
• Randomized algorithms and pseudorandom numbers
• The Ring Loading Problem

Cited In (10)

• Derandomized Concentration Bounds for Polynomials, and Hypergraph Maximal Independent Set
• On parallel versus sequential approximation
• Computational experience with a software framework for parallel integer programming
• Improved algorithms via approximations of probability distributions
• Extending NC and RNC algorithms
• Generation of feasible integer solutions on a massively parallel computer using the feasibility pump
• Title not available (Why is that?)
• Parallel approximation to high multiplicity scheduling problemsVIAsmooth multi-valued quadratic programming
• Title not available (Why is that?)
• On the parallel approximability of a subclass of quadratic programming.

This page was built for publication: Improved parallel approximation of a class of integer programming problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q676274)