A parallel approximation algorithm for positive linear programming

DOI10.1145/167088.167211zbMath1310.68224OpenAlexW2063241141MaRDI QIDQ5248514

Michael Luby, Noam Nisan

Publication date: 7 May 2015

Published in: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/167088.167211

Mathematics Subject Classification ID

Linear programming (90C05) Parallel algorithms in computer science (68W10) Approximation algorithms (68W25)

Related Items (30)

Fast primal-dual distributed algorithms for scheduling and matching problems ⋮ Greedy distributed optimization of multi-commodity flows ⋮ The complexity of linear programming in \((\gamma ,\kappa )\)-form ⋮ Parallel approximation of min-max problems ⋮ A sublinear-time randomized approximation algorithm for matrix games ⋮ (De)randomized construction of small sample spaces in \(\mathcal{NC}\) ⋮ Parallel approximation schemes for problems on planar graphs ⋮ Unnamed Item ⋮ A multiplicative weight updates algorithm for packing and covering semi-infinite linear programs ⋮ Nearly linear-time packing and covering LP solvers. Nearly linear-time packing and covering LP solvers, achieving width-independence and \(=(1/\varepsilon)\)-convergence ⋮ Approximating minimum feedback sets and multi-cuts in directed graphs ⋮ Non-linear ski rental ⋮ Parallel approximation to high multiplicity scheduling problemsVIAsmooth multi-valued quadratic programming ⋮ Unnamed Item ⋮ An efficient distributed algorithm for constructing small dominating sets ⋮ Fair Packing and Covering on a Relative Scale ⋮ A nearly linear-time PTAS for explicit fractional packing and covering linear programs ⋮ Improved parallel approximation of a class of integer programming problems ⋮ Pricing for fairness: distributed resource allocation for multiple objectives ⋮ The approximability of non-Boolean satisfiability problems and restricted integer programming ⋮ On the parallel approximability of a subclass of quadratic programming. ⋮ Unnamed Item ⋮ Approximation in (Poly-) logarithmic space ⋮ Constant-time distributed dominating set approximation ⋮ Better and simpler error analysis of the Sinkhorn-Knopp algorithm for matrix scaling ⋮ On randomized fictitious play for approximating saddle points over convex sets ⋮ Approximation in (Poly-) Logarithmic Space ⋮ Solving LP Relaxations of Some NP-Hard Problems Is As Hard As Solving Any Linear Program ⋮ Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs ⋮ Hitting sets when the VC-dimension is small

This page was built for publication: A parallel approximation algorithm for positive linear programming