A parallel approximation algorithm for positive linear programming

DOI10.1145/167088.167211MaRDI QIDQ5248514zbMATH OpenOpenAlexFDO

Authors 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) Approximation algorithms (68W25) Parallel algorithms in computer science (68W10)

Cited in

(31)

• Approximation in (poly-) logarithmic space
• (De)randomized construction of small sample spaces in \(\mathcal{NC}\)
• Multicommodity network flows: A survey. II: Solution methods
• Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs
• Parallel approximation of optimization problems
• Hitting sets when the VC-dimension is small
• Parallel approximation schemes for problems on planar graphs
• The approximability of non-Boolean satisfiability problems and restricted integer programming
• Approximating minimum feedback sets and multi-cuts in directed graphs (extended summary)
• Solving LP relaxations of some NP-hard problems is as hard as solving any linear program
• Better and simpler error analysis of the Sinkhorn-Knopp algorithm for matrix scaling
• Distributed load balancing: a new framework and improved guarantees
• A sublinear-time randomized approximation algorithm for matrix games
• scientific article; zbMATH DE number 7559394 (Why is no real title available?)
• Parallel approximation to high multiplicity scheduling problemsVIAsmooth multi-valued quadratic programming
• Non-linear ski rental
• Approximation in (Poly-) Logarithmic Space
• A nearly linear-time PTAS for explicit fractional packing and covering linear programs
• The complexity of linear programming in \((\gamma ,\kappa )\)-form
• Parallel approximation of min-max problems
• Fast primal-dual distributed algorithms for scheduling and matching problems
• An efficient distributed algorithm for constructing small dominating sets
• Better and simpler error analysis of the Sinkhorn-Knopp algorithm for matrix scaling
• Fair packing and covering on a relative scale
• Pricing for fairness: distributed resource allocation for multiple objectives
• On the parallel approximability of a subclass of quadratic programming.
• 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/)-convergence
• Constant-time distributed dominating set approximation
• Greedy distributed optimization of multi-commodity flows
• Improved parallel approximation of a class of integer programming problems

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

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