Neural Information Processing Systems http://nips.cc/

In this paper, we give a faster width-dependent algorithm for mixed packingcovering LPs. Mixed packing-covering LPs are fundamental to combinatorial optimization in computer science and operations research. Our algorithm finds a 1 ` ε approximate solution in time OpNw{εq, where N is number of nonzero entries in the constraint matrix, and w is the maximum number of nonzeros in any constraint. This algorithm is faster than Nesterov's smoothing algorithm which requires OpN? nw{εq time, where n is the dimension of the problem. Our work utilizes the framework of area convexity introduced in [Sherman-FOCS'17] to obtain the best dependence on ε while breaking the infamous l