Randomized MWU for positive LPs

zbMATH Open1403.68332MaRDI QIDQ4607903FDOQ4607903

Authors: Chandra Chekuri, Kent Quanrud 

Publication date: 15 March 2018

Full work available at URL: http://dl.acm.org/citation.cfm?id=3175292

Recommendations

• A combinatorial bound for linear programming and related problems
• Approximating the solution to mixed packing and covering LPs in parallel \(\widetilde O(\varepsilon^{-3})\) time
• A randomized scheme for speeding up algorithms for linear and convex programming problems with high constraints-to-variables ratio
• A subexponential bound for linear programming
• A randomized polynomial-time simplex algorithm for linear programming

Mathematics Subject Classification ID

Linear programming (90C05) Randomized algorithms (68W20) Analysis of algorithms (68W40) Approximation algorithms (68W25)

Cited In (8)

• A multiplicative weights update algorithm for packing and covering semi-infinite linear programs
• A multiplicative weights update algorithm for MINLP
• Approximating the solution to mixed packing and covering LPs in parallel \(\widetilde O(\varepsilon^{-3})\) time
• Fast and Deterministic Approximations for k-Cut.
• Maximization of monotone non-submodular functions with a knapsack constraint over the integer lattice
• A multiplicative weight updates algorithm for packing and covering semi-infinite linear programs
• Streaming algorithms for monotone non-submodular function maximization under a knapsack constraint on the integer lattice
• Multiplicative auction algorithm for approximate maximum weight bipartite matching

This page was built for publication: Randomized MWU for positive LPs

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