Approximating the solution to mixed packing and covering LPs in parallel O(^-3) time
From MaRDI portal
Publication:4598191
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
Cited in
(10)- Fair packing and covering on a relative scale
- Better and simpler error analysis of the Sinkhorn-Knopp algorithm for matrix scaling
- Nearly-linear time positive LP solver with faster convergence rate
- Nearly linear-time packing and covering LP solvers. Nearly linear-time packing and covering LP solvers, achieving width-independence and \(=(1/\varepsilon)\)-convergence
- Linear coupling: an ultimate unification of gradient and mirror descent
- Better and simpler error analysis of the Sinkhorn-Knopp algorithm for matrix scaling
- 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
- A nearly linear-time PTAS for explicit fractional packing and covering linear programs
- Unified acceleration method for packing and covering problems via diameter reduction
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)
