An Approximate, Efficient LP Solver for LP Rounding
Abstract
Many problems in machine learning can be solved by rounding the solution of an appropriate linear program. We propose a scheme that is based on a quadratic program relaxation which allows us to use parallel stochastic-coordinate-descent to approximately solve large linear programs efficiently. Our software is an order of magnitude faster than Cplex (a commercial linear programming solver) and yields similar solution quality. Our results include a novel perturbation analysis of a quadratic-penalty formulation of linear programming and a convergence result, which we use to derive running time and quality guarantees.
Cite
Text
Sridhar et al. "An Approximate, Efficient LP Solver for LP Rounding." Neural Information Processing Systems, 2013.Markdown
[Sridhar et al. "An Approximate, Efficient LP Solver for LP Rounding." Neural Information Processing Systems, 2013.](https://mlanthology.org/neurips/2013/sridhar2013neurips-approximate/)BibTeX
@inproceedings{sridhar2013neurips-approximate,
title = {{An Approximate, Efficient LP Solver for LP Rounding}},
author = {Sridhar, Srikrishna and Wright, Stephen and Re, Christopher and Liu, Ji and Bittorf, Victor and Zhang, Ce},
booktitle = {Neural Information Processing Systems},
year = {2013},
pages = {2895-2903},
url = {https://mlanthology.org/neurips/2013/sridhar2013neurips-approximate/}
}