We consider nearly linear time approximations for explicit mixed packing and covering LPs, a class of linear programs with many applications. Young gave a O(N log(m)/ε~2) deterministic algorithm based on the multiplicative weight update (MWU) framework, where N is the total number of nonzeroes, m is the number of constraints, and ε is the relative error parameter. The key technical ingredient was a data structure for managing the "multiplicative weight updates" more efficiently, which is nontrivial. One can also obtain the same running time by randomly sampling the multiplicative weight updates, but the probabilistic analysis is technical. We give a different deterministic algorithm that runs in O(N log(m)(log log(n) + log(l/ε))/ε~2) time. The new algorithm is also based on the MWU framework, and simply replaces the so-called "width-independent step size" with a maximal step size found by binary search; a.k.a. a line search. It does not require data structures or randomization to manage the weights; one just recomputes the weights as needed.
展开▼
