A Caltech Library Service

A Parallelizable Acceleration Framework for Packing Linear Programs

London, Palma and Vardi, Shai and Wierman, Adam and Yi, Hanling (2018) A Parallelizable Acceleration Framework for Packing Linear Programs. In: 2018 Information Theory and Applications Workshop (ITA). IEEE , Piscataway, NJ, pp. 1-10. ISBN 9781728101248.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper
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.
Funding AgencyGrant Number
Linde Institute of Economic and Management ScienceUNSPECIFIED
International Teochew Doctors AssociationUNSPECIFIED
Subject Keywords:Approximation algorithms; Acceleration; Parallel algorithms; Cloning; Linear programming; Markov random fields; Task analysis
Record Number:CaltechAUTHORS:20181101-121244788
Persistent URL:
Official Citation:P. London, S. Vardi, A. Wierman and H. Yi, "A Parallelizable Acceleration Framework for Packing Linear Programs," 2018 Information Theory and Applications Workshop (ITA), San Diego, CA, USA, 2018, pp. 1-10. doi: 10.1109/ITA.2018.8503261
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:90570
Deposited By: George Porter
Deposited On:01 Nov 2018 19:40
Last Modified:09 Jul 2020 21:51

Repository Staff Only: item control page