CaltechAUTHORS
  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. http://resolver.caltech.edu/CaltechAUTHORS:20181101-121244788

[img] PDF - Submitted Version
See Usage Policy.

216Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20181101-121244788

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.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
https://doi.org/10.1109/ita.2018.8503261DOIArticle
https://arxiv.org/abs/1711.06656arXivDiscussion 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.
Funders:
Funding AgencyGrant Number
NSFCCF-1637598
NSFCNS-1518941
NSFCPS-154471
Ronald And Maxine Linde Institute for Economic and Management Sciences, CaltechUNSPECIFIED
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:http://resolver.caltech.edu/CaltechAUTHORS:20181101-121244788
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
Collection:CaltechAUTHORS
Deposited By: George Porter
Deposited On:01 Nov 2018 19:40
Last Modified:27 Jun 2019 18:33

Repository Staff Only: item control page