Randomized MWU for positive LPs

We describe and analyze a simple randomized multiplicative weight update (MWU) based algorithm for approximately solving positive linear programming problems, in particular, mixed packing and covering LPs. Given m explicit linear packing and covering constraints over n variables specified by N nonzero entries, Young [36] gave a deterministic algorithm returning an (1 + ϵ)-approximate feasible solution (if a feasible solution exists) in Õ N/ϵ2 ϵ time. We show that a simple randomized implementation matches this bound, and that randomization can be further exploited to improve the running time to Õ N/ϵ + m/ϵ2 + n/ϵ3 ϵ (both with high probability). For instances that are not very sparse (with at least ~!(1/ϵ) nonzeroes per column on average), this improves the running time of Õ N/ϵ2 ϵ. The randomized algorithm also gives improved running times for some implicitly defined problems that arise in combinatorial and geometric optimization.