Randomized MWU for positive LPs

MaRDI QIDQ4607903zbMATH OpenFDO

Authors Chandra Chekuri, Kent Quanrud

Publication date 15 March 2018

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

Mathematics Subject Classification ID

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

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

Cited in

(8)

• Multiplicative auction algorithm for approximate maximum weight bipartite matching
• 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

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)