Approximating the solution to mixed packing and covering LPs in parallel O(^-3) time
From MaRDI portal
Publication:4598191
DOI10.4230/LIPICS.ICALP.2016.52zbMATH Open1388.68310MaRDI QIDQ4598191FDOQ4598191
Authors: Michael W. Mahoney, Satish Rao, Di Wang, Peng Zhang 
Publication date: 19 December 2017
Recommendations
- Nearly linear-time packing and covering LP solvers. Nearly linear-time packing and covering LP solvers, achieving width-independence and \(=(1/\varepsilon)\)-convergence
- Nearly-linear time positive LP solver with faster convergence rate
- A nearly linear-time PTAS for explicit fractional packing and covering linear programs
- Using optimization to break the epsilon barrier: a faster and simpler width-independent algorithm for solving positive linear programs in parallel
- Randomized MWU for positive LPs
Linear programming (90C05) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Approximation algorithms (68W25) Parallel algorithms in computer science (68W10)
Cited In (10)
- Linear coupling: an ultimate unification of gradient and mirror descent
- Nearly-linear time positive LP solver with faster convergence rate
- Unified acceleration method for packing and covering problems via diameter reduction
- Better and simpler error analysis of the Sinkhorn-Knopp algorithm for matrix scaling
- A nearly linear-time PTAS for explicit fractional packing and covering linear programs
- Better and simpler error analysis of the Sinkhorn-Knopp algorithm for matrix scaling
- Fair packing and covering on a relative scale
- Using optimization to break the epsilon barrier: a faster and simpler width-independent algorithm for solving positive linear programs in parallel
- Nearly linear-time packing and covering LP solvers. Nearly linear-time packing and covering LP solvers, achieving width-independence and \(=(1/\varepsilon)\)-convergence
- Randomized MWU for positive LPs
This page was built for publication: Approximating the solution to mixed packing and covering LPs in parallel \(\widetilde O(\varepsilon^{-3})\) time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4598191)
