pith. sign in

arxiv: 1907.00312 · v1 · pith:MCCL7F5Ynew · submitted 2019-06-30 · 🧮 math.OC · cs.LG· stat.ML

Competitive Algorithms for Online Budget-Constrained Continuous DR-Submodular Problems

Omid Sadeghi , Reza Eghbali , Maryam Fazel This is my paper

Pith reviewed 2026-05-25 13:06 UTC · model grok-4.3

classification 🧮 math.OC cs.LGstat.ML
keywords online optimizationDR-submodular maximizationcompetitive ratioprimal-dual algorithmlinear packing constraintsbudget constraintsdiminishing returns
0
0 comments X

The pith

A primal-dual algorithm achieves the first competitive ratio bound for online monotone DR-submodular maximization under linear packing constraints that matches the linear case.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper examines online maximization of monotone continuous functions satisfying the diminishing returns property, subject to linear packing budget constraints. It analyzes the Generalized Sequential primal-dual algorithm and derives a competitive ratio bound for this class of problems. The bound is proven to match the known tight bound that holds when the objective reduces to a linear function. A sympathetic reader would care because the result extends optimal-ratio guarantees from linear objectives to a strictly larger family of non-concave functions while using the same algorithmic structure.

Core claim

The Generalized Sequential algorithm obtains the first bound on the competitive ratio of online monotone DR-submodular function maximization subject to linear packing constraints, matching the known tight bound in the special case of linear objective function.

What carries the argument

The Generalized Sequential primal-dual algorithm, which performs sequential updates that preserve the diminishing returns property to establish the competitive ratio.

If this is right

  • The same ratio guarantee applies to any monotone continuous DR-submodular objective, not only linear ones.
  • The algorithm directly solves a wider set of online budget-constrained problems without loss of the competitive ratio.
  • The analysis shows that the DR property is sufficient to carry the primal-dual updates through to the linear-case bound.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The result suggests the competitive ratio is governed primarily by the packing constraints rather than further curvature details beyond DR-submodularity.
  • Similar primal-dual updates could be tested on discrete DR-submodular settings or on packing constraints with mild nonlinearities.
  • Applications such as online resource allocation with submodular utilities become candidates for the same ratio without new algorithmic machinery.

Load-bearing premise

The objective must be monotone and continuous DR-submodular and the constraints must be linear packing constraints for the primal-dual analysis to deliver the matching ratio.

What would settle it

An explicit monotone continuous DR-submodular function together with linear packing constraints on which the algorithm's realized competitive ratio falls below the known tight bound for linear objectives would falsify the claim.

read the original abstract

In this paper, we study a certain class of online optimization problems, where the goal is to maximize a function that is not necessarily concave and satisfies the Diminishing Returns (DR) property under budget constraints. We analyze a primal-dual algorithm, called the Generalized Sequential algorithm, and we obtain the first bound on the competitive ratio of online monotone DR-submodular function maximization subject to linear packing constraints which matches the known tight bound in the special case of linear objective function.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper studies online maximization of monotone continuous DR-submodular objective functions subject to linear packing constraints. It introduces the Generalized Sequential primal-dual algorithm and proves that its competitive ratio matches the known tight bound for the linear-objective special case.

Significance. The result supplies the first competitive-ratio guarantee for the DR-submodular case that specializes exactly to the linear tight bound. The analysis in Sections 3–4 applies the DR property only to bound the integrals of marginal gains in the standard primal-dual fashion; the derivation contains no hidden parameters or post-hoc adjustments.

minor comments (3)
  1. [Section 3] §3, Algorithm 1: the pseudocode for the Generalized Sequential updates is described in prose only; an explicit listing of the primal and dual update rules would improve readability.
  2. [Abstract] The abstract states that the ratio 'matches the known tight bound' but does not record the explicit numerical value (1-1/e); adding the value would make the claim self-contained.
  3. [Section 5] Table 1 (if present) or the experimental section: the reported ratios for non-linear DR-submodular instances should include a direct comparison column against the linear-case benchmark to illustrate the matching property.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary and significance assessment, which correctly identifies that our Generalized Sequential primal-dual algorithm yields the first competitive-ratio guarantee for the DR-submodular case that exactly recovers the known tight bound for linear objectives. We appreciate the recommendation of minor revision.

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper presents a primal-dual analysis deriving a competitive ratio for the Generalized Sequential algorithm on monotone continuous DR-submodular maximization under linear packing constraints. This bound is obtained by integrating marginal gains using the DR property in the standard way (Sections 3-4) and is shown to match the known tight ratio for the linear-objective special case as an external benchmark; no step reduces by construction to a fitted parameter, self-citation load, or renamed input, and the central claim remains independent of the target result.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on standard mathematical axioms of online competitive analysis and the definition of DR-submodularity; no free parameters, new entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)
  • domain assumption Standard assumptions of adversarial online input model and access to marginal gains or gradients at decision times.
    Implicit in any competitive analysis of online algorithms as described in the abstract.

pith-pipeline@v0.9.0 · 5610 in / 1160 out tokens · 25773 ms · 2026-05-25T13:06:11.969923+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

34 extracted references · 34 canonical work pages · 6 internal anchors

  1. [1]

    An optimal algorithm for on-line bipartite matching

    Richard M Karp, Umesh V V azirani, and Vijay V V azirani. An optimal algorithm for on-line bipartite matching. In Proceedings of the twenty-second annual ACM symposium on Th eory of computing, pages 352–358. ACM, 1990. 13

    work page 1990

  2. [2]

    Adwords and generalized online matching

    Aranyak Mehta, Amin Saberi, Umesh V azirani, and Vijay V azirani. Adwords and generalized online matching. Journal of the ACM (JACM), 54(5):22, 2007

    work page 2007

  3. [3]

    Online primal-dual algorithms for maxi- mizing ad-auctions revenue

    Niv Buchbinder, Kamal Jain, and Joseph Seffi Naor. Online primal-dual algorithms for maxi- mizing ad-auctions revenue. In European Symposium on Algorithms, pages 253–264. Springer, 2007

    work page 2007

  4. [4]

    Combinat orial auctions with decreasing marginal utilities

    Benny Lehmann, Daniel Lehmann, and Noam Nisan. Combinat orial auctions with decreasing marginal utilities. Games and Economic Behavior , 55(2):270–296, 2006

    work page 2006

  5. [5]

    Online primal-dual algo rithms for covering and packing

    Niv Buchbinder and Joseph Naor. Online primal-dual algo rithms for covering and packing. Mathematics of Operations Research, 34(2):270–286, 2009

    work page 2009

  6. [6]

    Online algorithms for covering and packing problems with convex objectives

    Y ossi Azar, Niv Buchbinder, TH Hubert Chan, Shahar Chen, Ilan Reuven Cohen, Anupam Gupta, Zhiyi Huang, Ning Kang, Viswanath Nagarajan, Joseph Naor, et al. Online algorithms for covering and packing problems with convex objectives. I n F oundations of Computer Sci- ence (FOCS), 2016 IEEE 57th Annual Symposium on , pages 148–157. IEEE, 2016

    work page 2016

  7. [7]

    Worst Case Competitive Analysis of Online Algorithms for Conic Optimization

    Reza Eghbali and Maryam Fazel. Worst case competitive an alysis of online algorithms for conic optimization. arXiv preprint arXiv:1611.00507, 2016

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  8. [8]

    The design of com petitive online algorithms via a primal–dual approach

    Niv Buchbinder, Joseph Seffi Naor, et al. The design of com petitive online algorithms via a primal–dual approach. F oundations and Trends R⃝ in Theoretical Computer Science , 3(2– 3):93–263, 2009

    work page 2009

  9. [9]

    A multiple-choice secretary algorit hm with applications to online auctions

    Robert Kleinberg. A multiple-choice secretary algorit hm with applications to online auctions. In Proceedings of the sixteenth annual ACM-SIAM symposium on D iscrete algorithms, pages 630–631. Society for Industrial and Applied Mathematics, 2 005

    work page

  10. [10]

    Optimal bidding strat- egy for brand advertising

    Takanori Maehara, Atsuhiro Narita, Jun Baba, and Takay uki Kawabata. Optimal bidding strat- egy for brand advertising. In IJCAI, pages 424–432, 2018

    work page 2018

  11. [11]

    Optimal approximation for the submodular welfare problem in the value oracle model

    Jan V ondrák. Optimal approximation for the submodular welfare problem in the value oracle model. In Proceedings of the fortieth annual ACM symposium on Theory o f computing, pages 67–74. ACM, 2008

    work page 2008

  12. [12]

    Guaranteed Non-convex Optimization: Submodular Maximization over Continuous Domains

    Andrew An Bian, Baharan Mirzasoleiman, Joachim M Buhma nn, and Andreas Krause. Guar- anteed non-convex optimization: Submodular maximization over continuous domains. arXiv preprint arXiv:1606.05615, 2016

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  13. [13]

    Comp etitive online algorithms for re- source allocation over the positive semidefinite cone

    Reza Eghbali, James Saunderson, and Maryam Fazel. Comp etitive online algorithms for re- source allocation over the positive semidefinite cone. Mathematical Programming, pages 1–26, 2018

    work page 2018

  14. [14]

    Maximizing a submodular set function subject to a matroid constraint

    Gruia Calinescu, Chandra Chekuri, Martin Pál, and Jan V ondrák. Maximizing a submodular set function subject to a matroid constraint. In International Conference on Integer Programming and Combinatorial Optimization , pages 182–196. Springer, 2007

    work page 2007

  15. [15]

    Monot one closure of relaxed constraints in submodular optimization: Connections between minimizati on and maximization: Extended version

    Rishabh Iyer, Stefanie Jegelka, and Jeff Bilmes. Monot one closure of relaxed constraints in submodular optimization: Connections between minimizati on and maximization: Extended version. 2014

    work page 2014

  16. [16]

    Optimal DR-Submodular Maximization and Applications to Provable Mean Field Inference

    An Bian, Joachim M Buhmann, and Andreas Krause. Optimal dr-submodular maximization and applications to provable mean field inference. arXiv preprint arXiv:1805.07482, 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  17. [17]

    Continuous dr-submodular maximization: Structure and algorithms

    An Bian, Kfir Levy, Andreas Krause, and Joachim M Buhmann . Continuous dr-submodular maximization: Structure and algorithms. In Advances in Neural Information Processing Sys- tems, pages 486–496, 2017

    work page 2017

  18. [18]

    Welfare maximization with production costs: A primal dual approach

    Zhiyi Huang and Anthony Kim. Welfare maximization with production costs: A primal dual approach. Games and Economic Behavior , 2018

    work page 2018

  19. [19]

    Budget constrained bidding in keyword auctions and online knapsack problems

    Y unhong Zhou, Deeparnab Chakrabarty, and Rajan Lukose . Budget constrained bidding in keyword auctions and online knapsack problems. In International W orkshop on Internet and Network Economics, pages 566–576. Springer, 2008. 14

    work page 2008

  20. [20]

    Convergence Rate of Frank-Wolfe for Non-Convex Objectives

    Simon Lacoste-Julien. Convergence rate of frank-wolf e for non-convex objectives. arXiv preprint arXiv:1607.00345, 2016

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  21. [21]

    Submodular se t functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizatio ns of the rado-edmonds theorem

    Michele Conforti and Gérard Cornuéjols. Submodular se t functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizatio ns of the rado-edmonds theorem. Discrete applied mathematics, 7(3):251–274, 1984

    work page 1984

  22. [22]

    Maximizing a monotone submodular function subject to a matroid constraint

    Gruia Calinescu, Chandra Chekuri, Martin Pál, and Jan V ondrák. Maximizing a monotone submodular function subject to a matroid constraint. SIAM Journal on Computing, 40(6):1740– 1766, 2011

    work page 2011

  23. [23]

    Maximizin g submodular set functions subject to multiple linear constraints

    Ariel Kulik, Hadas Shachnai, and Tami Tamir. Maximizin g submodular set functions subject to multiple linear constraints. In Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms, pages 545–554. Society for Industrial and Applied Mathema tics, 2009

    work page 2009

  24. [24]

    Subm odular function maximization via the multilinear relaxation and contention resolution sche mes

    Chandra Chekuri, Jan V ondrák, and Rico Zenklusen. Subm odular function maximization via the multilinear relaxation and contention resolution sche mes. SIAM Journal on Computing , 43(6):1831–1879, 2014

    work page 2014

  25. [25]

    On multipl icative weight updates for concave and submodular function maximization

    Chandra Chekuri, TS Jayram, and Jan V ondrák. On multipl icative weight updates for concave and submodular function maximization. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science , pages 201–210. ACM, 2015

    work page 2015

  26. [26]

    A unified c ontinuous greedy algorithm for submodular maximization

    Moran Feldman, Joseph Naor, and Roy Schwartz. A unified c ontinuous greedy algorithm for submodular maximization. In F oundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on , pages 570–579. IEEE, 2011

    work page 2011

  27. [27]

    Constrained submodular maxi mization: Beyond 1/e

    Alina Ene and Huy L Nguyen. Constrained submodular maxi mization: Beyond 1/e. In F oun- dations of Computer Science (FOCS), 2016 IEEE 57th Annual Sy mposium on, pages 248–257. IEEE, 2016

    work page 2016

  28. [28]

    Constrained Submodular Maximization via a Non-symmetric Technique

    Niv Buchbinder and Moran Feldman. Constrained submodu lar maximization via a non- symmetric technique. arXiv preprint arXiv:1611.03253, 2016

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  29. [29]

    Submodular functio n maximization., 2014

    Andreas Krause and Daniel Golovin. Submodular functio n maximization., 2014

    work page 2014

  30. [30]

    Submodular function s maximization problems

    Niv Buchbinder and Moran Feldman. Submodular function s maximization problems. 2017

    work page 2017

  31. [31]

    St ochastic on-line knapsack problems

    Alberto Marchetti-Spaccamela and Carlo V ercellis. St ochastic on-line knapsack problems. Mathematical Programming, 68(1-3):73–104, 1995

    work page 1995

  32. [32]

    Sub- modular secretary problem and extensions

    MohammadHossein Bateni, Mohammadtaghi Hajiaghayi, a nd Morteza Zadimoghaddam. Sub- modular secretary problem and extensions. ACM Transactions on Algorithms (TALG), 9(4):32, 2013

    work page 2013

  33. [33]

    Constrained non- monotone submodular maximization: Offline and secretary al gorithms

    Anupam Gupta, Aaron Roth, Grant Schoenebeck, and Kunal Talwar. Constrained non- monotone submodular maximization: Offline and secretary al gorithms. In International W ork- shop on Internet and Network Economics , pages 246–257. Springer, 2010

    work page 2010

  34. [34]

    Submodular Secretary Problems: Cardinality, Matching, and Linear Constraints

    Thomas Kesselheim and Andreas Tönnis. Submodular secr etary problems: Cardinality, match- ing, and linear constraints. arXiv preprint arXiv:1607.08805, 2016. 15

    work page internal anchor Pith review Pith/arXiv arXiv 2016