The DOI matches its Crossref record.
Online Primal-Dual Algorithms for Covering and Packing
Abstract
We study a wide range of online covering and packing optimization problems. In an online covering problem, a linear cost function is known in advance, but the linear constraints that define the feasible solution space are given one by one, in rounds. In an online packing problem, the profit function as well as the packing constraints are not known in advance. In each round additional information (i.e., a new variable) about the profit function and the constraints is revealed. An online algorithm needs to maintain a feasible solution in each round; in addition, the solutions generated over the different rounds need to satisfy a monotonicity property. We provide general deterministic primal-dual algorithms for online fractional covering and packing problems. We also provide deterministic algorithms for several integral online covering and packing problems. Our algorithms are designed via a novel online primal-dual technique and are evaluated via competitive analysis.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cited by
Xie, J., Yu, F. R., Huang, T., Xie, R., Liu, J., Wang, C., & Liu, Y. (2019) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2018.2866942 · Cited by 700
Han, S., Shen, H., Philipose, M., Agarwal, S., Wolman, A., & Krishnamurthy, A. (2016) · Proceedings of the 14th Annual International Conference on Mobile Systems, Applications, and Services · doi:10.1145/2906388.2906396 · Cited by 367
Greedy Δ-Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost
Koufogiannakis, C., & Young, N. E. (2013) · Algorithmica · doi:10.1007/s00453-012-9629-3 · Cited by 53
(2015) · Cited by 14
Caching with rental cost and zapping
Khare, M., & Young, N. E. (2012) · arXiv · doi:10.48550/arxiv.1208.2724 · Cited by 1
“oth the models, and an O(log2k)-competitive randomized algorithm for the general case. The onlineprimal dual analysis was introduced by Young [14]. This work was extended to the randomized setting in [3, 4, 5]. Adamaszek et al. [2] use the primal-dual approach and give an O(logk)-competitive for the general case. Kouf…”
Metadata
- Authors
- Buchbinder, N., & Naor, J. (.
- Venue
- Mathematics of Operations Research
- Published
- 2009-05
- Volume
- 34
- Issue
- 2
- Pages
- 270-286
- ISSN
- 0364-765X (ISSN-L)
- 1526-5471
- OpenAlex
- W2122886291
- Cited by
- 192
- References
- 0
- FWCI
- 9.15
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Online Primal-Dual Algorithms for Covering and Packing. https://app.cochat.ai/papers/10.1287/moor.1080.0363
- The paper
- Buchbinder, N., & Naor, J. (. (2009). Online Primal-Dual Algorithms for Covering and Packing. Mathematics of Operations Research. https://doi.org/10.1287/moor.1080.0363
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.