Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published February 2018 | public
Book Section - Chapter Open

A Parallelizable Acceleration Framework for Packing Linear Programs

Abstract

This paper presents an acceleration framework for packing linear programming problems where the amount of data available is limited, i.e., where the number of constraints m is small compared to the variable dimension n . The framework can be used as a black box to speed up linear programming solvers dramatically, by two orders of magnitude in our experiments. We present worst-case guarantees on the quality of the solution and the speedup provided by the algorithm, showing that the framework provides an approximately optimal solution while running the original solver on a much smaller problem. The framework can be used to accelerate exact solvers, approximate solvers, and parallel/distributed solvers. Further, it can be used for both linear programs and integer linear programs.

Additional Information

© 2018 Association for the Advancement of Artificial Intelligence. PL, SV, and AW were supported in part by NSF grants AitF-1637598, CNS-1518941, CPS-154471 and the Linde Institute. HY was supported by the International Teochew Doctors Association Zheng Hanming Visiting Scholar Award Scheme.

Attached Files

Submitted - 1711.06656.pdf

Files

1711.06656.pdf
Files (221.3 kB)
Name Size Download all
md5:e0c64db9b41340d5635c6e74cd7b0fc1
221.3 kB Preview Download

Additional details

Created:
August 21, 2023
Modified:
August 21, 2023