CaltechAUTHORS
  A Caltech Library Service

Online Mixed Packing and Covering

Azar, Yossi and Bhaskar, Umang and Flesicher, Lisa and Panigrahi, Debmalya (2013) Online Mixed Packing and Covering. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM , Philadelphia, PA, pp. 85-100. ISBN 978-1-61197-251-1. https://resolver.caltech.edu/CaltechAUTHORS:20160420-163337656

[img] PDF - Published Version
See Usage Policy.

417Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20160420-163337656

Abstract

Recent work has shown that the classical framework of solving optimization problems by obtaining a fractional solution to a linear program (LP) and rounding it to an integer solution can be extended to the online setting using primal-dual techniques. The success of this new framework for online optimization can be gauged from the fact that it has led to progress in several longstanding open questions. However, to the best of our knowledge, this framework has previously been applied to LPs containing only packing or only covering constraints, or minor variants of these. We extend this framework in a fundamental way by demonstrating that it can be used to solve mixed packing and covering LPs online, where packing constraints are given offline and covering constraints are received online. The objective is to minimize the maximum multiplicative factor by which any packing constraint is violated, while satisfying the covering constraints. Our results represent the first algorithm that obtains a polylogarithmic competitive ratio for solving mixed LPs online. We then consider two canonical examples of mixed LPs: unrelated machine scheduling with startup costs, and capacity constrained facility location. We use ideas generated from our result for mixed packing and covering to obtain polylogarithmic-competitive algorithms for these problems. We also give lower bounds to show that the competitive ratios of our algorithms are nearly tight.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1137/1.9781611973105.6DOIPaper
http://epubs.siam.org/doi/abs/10.1137/1.9781611973105.6PublisherPaper
Additional Information:© 2013 SIAM. Yossi Azar was supported in part by the Israel Science Foundation grant 1404/10, Umang Bhaskar and Lisa Fleischer by NSF grants CCF-0728869 and CCF-1016778, and Debmalya Panigrahi by NSF grant CCF-1117381.
Funders:
Funding AgencyGrant Number
Israel Science Foundation1404/10
NSFCCF-0728869
NSFCCF-1016778
NSFCCF-1117381
Record Number:CaltechAUTHORS:20160420-163337656
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20160420-163337656
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:66343
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:20 Apr 2016 23:55
Last Modified:03 Oct 2019 09:55

Repository Staff Only: item control page