NeurIPS 2019
Sun Dec 8th through Sat the 14th, 2019 at Vancouver Convention Center
Paper ID:8763
Title:Faster width-dependent algorithm for mixed packing and covering LPs


		
This paper shows that Mixed Packing Covering Linear programs can be eps-approximated in O(1/eps) iterations. This work builds on Sherman's approach to max flow. This is a strong result on an important class of problems. Optimization problems of this nature arise frequently in machine learning applications and reducing the eps dependence from quadratic to linear is a significant improvement. The reviewers liked the result and the presentation and strongly supported acceptance. One aspect that could be improved is the motivation. While optimization problem are central to ML, mentioning some applications of these problems to ML applications (e.g. to optimal transport) would make the connection to this conference more explicit. While the paper is well-written the authors are encouraged to remind the general Neurips audience of the significance of these results to ML applications.