pith. sign in

arxiv: 2409.05020 · v2 · submitted 2024-09-08 · 📡 eess.SY · cs.DS· cs.SY

A Performance Bound for the Greedy Algorithm in a Generalized Class of String Optimization Problems

Brandon Van Over , Bowen Li , Edwin K. P. Chong , Ali Pezeshki This is my paper

Pith reviewed 2026-05-23 20:40 UTC · model grok-4.3

classification 📡 eess.SY cs.DScs.SY
keywords greedy algorithmperformance boundstring optimizationcurvature boundssubmodular functionssensor coveragesocial welfare maximization
0
0 comments X

The pith

A new simpler bound for the greedy algorithm in string optimization problems outperforms the generalized versions of two prior curvature bounds and reveals an error in the third.

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

The paper establishes a performance bound for the greedy algorithm on optimization problems whose decision variables are strings rather than sets. It generalizes two curvature constants from the 1984 Conforti-Cornuéjols analysis of submodular set functions over matroids, then derives a still simpler computable bound that covers a wider class of string-domain functions. The authors prove the new bound is strictly tighter than the two generalizations and supply a counterexample showing the third prior constant does not hold under the original assumptions. If the claims are correct, the result supplies stronger, easier-to-check guarantees for greedy solutions in sensor-coverage and social-welfare problems.

Core claim

By extending the constants α_G and α_G'' to string domains while preserving the structural assumptions that recover the matroid case as a special instance, the authors obtain a new performance bound for the greedy algorithm that is both simpler and strictly superior to those two earlier bounds; a counterexample simultaneously demonstrates that the third constant α_G' fails to give a valid guarantee under the same assumptions.

What carries the argument

The new, simpler computable performance bound obtained by generalizing the curvature constants α_G and α_G'' from set functions to string-domain functions.

If this is right

  • The bound supplies explicit approximation guarantees for greedy sensor-coverage solutions when the coverage function is either set-submodular or string-submodular.
  • The same bound applies directly to social-welfare maximization when each agent's utility is an arbitrary black-box function on strings.
  • Because the new bound is computable from the problem data without solving the original optimization problem, it can be used to certify performance in advance.
  • The result recovers the classical matroid setting as a special case, so all prior guarantees for submodular maximization over matroids remain valid.

Where Pith is reading between the lines

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

  • The same generalization technique could be applied to other discrete structures whose elements form ordered sequences, such as scheduling or routing problems.
  • Algorithm designers might now prefer the new bound over older curvature expressions when implementing performance certificates for greedy heuristics.
  • The existence of the counterexample suggests that any future transfer of set-based bounds to string or sequence domains should be accompanied by explicit verification rather than assumed automatic.

Load-bearing premise

String-domain functions must satisfy the same monotonicity and diminishing-returns properties that were used to define the curvature constants for set functions over matroids.

What would settle it

A concrete string optimization instance, constructed exactly as in the paper's counterexample for α_G', in which the ratio achieved by the greedy solution falls below the value predicted by the new bound.

Figures

Figures reproduced from arXiv: 2409.05020 by Ali Pezeshki, Bowen Li, Brandon Van Over, Edwin K. P. Chong.

Figure 1
Figure 1. Figure 1: Sensor coverage for event detection in a mission space. The location of a sensor placed during epoch i is denoted by si , and it can detect any occurring event at location x ∈ Ω [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The top right and bottom left regions have high [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 2
Figure 2. Figure 2: Mission space partition. We denote the (1−e −1 ) performance bound in [4] and [6] by β0, the greedy curvature bound in [2] and its generalized ver￾sion by β1, and our performance bound by β2 = f(GK)/Bs. A comparison of these performance bounds under different (initial) decay rates with K = 5 is shown in [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 4
Figure 4. Figure 4: Performance bound comparison under different number of placed sensors. Upper Figure: Homogeneous sensors with decay rate λ = 1; Lower Figure: Nonhomogeneous sensors with initial decay rate λ1 = 1. set AN = {a1, . . . , aN } of N agents to maximize the social welfare function X N j=1 uj (Sj ). Let Sj ⊆ IM be the subset of items we assign to agent aj , and uj is the utility function of agent aj defined on th… view at source ↗
Figure 3
Figure 3. Figure 3: Performance bound comparison under different (initial) decay rates with number of placed sensors K = 5. Upper Figure: Homoge￾neous Sensors; Lower Figure: Nonhomogeneous Sensors. B. Social Welfare Maximization with Black-Box Utility Functions In the welfare maximization problem, we are tasked with partitioning a set of M items IM = {i1, . . . , iM} among a 3 4 5 6 7 8 Number of Homogeneous Sensors (K) 0.7 0… view at source ↗
Figure 5
Figure 5. Figure 5: Performance bound comparison for set utility functions (upper figure) and string utility functions (lower figure). Experiment: In our experiments, we have 60 items to dis￾tribute. Each utility function is a black-box function whose incremental gains for all 60 items are randomly generated from Unif(0, 100). In [PITH_FULL_IMAGE:figures/full_fig_p009_5.png] view at source ↗
read the original abstract

We present a simple performance bound for the greedy scheme in string optimization problems that obtains strong results. Our approach vastly generalizes the group of previously established greedy curvature bounds by Conforti and Cornu\'{e}jols (1984). We consider three constants, $\alpha_G$, $\alpha_G'$, and $\alpha_G''$ introduced by Conforti and Cornu\'{e}jols (1984), that are used in performance bounds of greedy schemes in submodular set optimization. We first generalize both of the $\alpha_G$ and $\alpha_G''$ bounds to string optimization problems in a manner that includes maximizing submodular set functions over matroids as a special case. We then derive a much simpler and computable bound that allows for applications to a far more general class of functions with string domains. We prove that our bound is superior to both the $\alpha_G$ and $\alpha_G''$ bounds and provide a counterexample to show that the $\alpha_G'$ bound is incorrect under the assumptions in Conforti and Cornu\'{e}jols (1984). We conclude with two applications. The first is an application of our result to sensor coverage problems. We demonstrate our performance bound in cases where the objective function is set submodular and string submodular. The second is an application to a social welfare maximization problem with black-box utility functions.

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 / 2 minor

Summary. The paper claims to derive a new, simpler, and computable performance bound for the greedy algorithm on string optimization problems. It generalizes the α_G and α_G'' constants from Conforti and Cornuéjols (1984) to string domains (reducing to the matroid case as a special instance), proves the new bound is superior to both, supplies a counterexample showing the α_G' bound is incorrect under the 1984 assumptions, and demonstrates the result on sensor coverage (set- and string-submodular cases) and social-welfare maximization with black-box utilities.

Significance. If the generalization and proofs hold, the work supplies a stronger, more widely applicable curvature-style bound for greedy algorithms beyond set functions, directly useful for sensor placement and welfare problems. The explicit reduction to the matroid case, the superiority proof, and the counterexample to α_G' are concrete strengths that would make the bound a useful reference for string-domain submodular optimization.

minor comments (2)
  1. Abstract: the claim that the new bound 'vastly generalizes' the group of previously established bounds would be clearer if the precise function class (beyond 'string domains') were stated explicitly in the abstract rather than only in the body.
  2. The manuscript should include a short table or paragraph comparing the new bound numerically with α_G and α_G'' on at least one concrete instance from the sensor-coverage application to illustrate the claimed superiority.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of our manuscript and for recommending minor revision. The referee's summary correctly identifies the main contributions, including the generalization of the α_G and α_G'' bounds, the superiority proof, the counterexample to α_G', and the applications to sensor coverage and social welfare maximization.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The derivation generalizes the external constants α_G and α_G'' from Conforti and Cornuéjols (1984) to string domains while treating the matroid case as a special instance, then directly proves superiority of the new bound and supplies an explicit counterexample for α_G' under the 1984 assumptions. No step reduces by construction to a fitted parameter, self-definition, or load-bearing self-citation; the central claims rest on independent mathematical generalization and counterexample construction rather than renaming or circular invocation of prior results by the same authors.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review prevents identification of specific free parameters or invented entities; the work relies on standard mathematical assumptions about submodularity and curvature constants from prior literature.

pith-pipeline@v0.9.0 · 5805 in / 1048 out tokens · 37589 ms · 2026-05-23T20:40:13.004615+00:00 · methodology

discussion (0)

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

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. A Greedy PDE Router for Blending Neural Operators and Classical Methods

    stat.ME 2025-09 unverdicted novelty 6.0

    An approximate greedy router for hybrid PDE solvers that mimics optimal selection without true error access and shows faster, more stable error reduction on test equations.

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages · cited by 1 Pith paper

  1. [1]

    Adaptive submodularity: Theory and applications in active learning and stochastic optimization,

    D. Golovin and A. Krause, “Adaptive submodularity: Theory and applications in active learning and stochastic optimization,” J. Artif. Intell. Res., vol. 42, pp. 427–486, 2011

    work page 2011

  2. [2]

    Submodular set functions, matroids and the greedy algorithm: Tight worst-case bounds and some generalizations of the Rado-Edmonds theorem,

    M. Conforti and G. Cornu ´ejols, “Submodular set functions, matroids and the greedy algorithm: Tight worst-case bounds and some generalizations of the Rado-Edmonds theorem,” Discrete. Appl. Math. , vol. 7, no. 3, pp. 251–274, 1984

    work page 1984

  3. [3]

    M. L. Fisher, G. L. Nemhauser, and L. A. Wolsey, An analysis of approximations for maximizing submodular set functions—II . Springer Berlin Heidelberg, 1978

    work page 1978

  4. [4]

    An analysis of approximations for maximizing submodular set functions—I,

    G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher, “An analysis of approximations for maximizing submodular set functions—I,” Math. Program., vol. 14, pp. 265–294, 1978

    work page 1978

  5. [5]

    Maximizing a monotone submodular function subject to a matroid constraint,

    G. Calinescu, C. Chekuri, M. Pal, and J. V ondr ´ak, “Maximizing a monotone submodular function subject to a matroid constraint,” SIAM J. Comput., vol. 40, no. 6, pp. 1740–1766, 2011

    work page 2011

  6. [6]

    An online algorithm for maximizing submodular functions,

    M. Streeter and D. Golovin, “An online algorithm for maximizing submodular functions,” in Proc. Adv. in Neural Inf. Process. Syst. 21 (NIPS 2008) , vol. 21, (Vancouver, BC, Canada), pp. 1577–1584, Dec. 2008

    work page 2008

  7. [7]

    Maximizing sequence- submodular functions and its application to online advertising,

    S. Alaei, A. Makhdoumi, and A. Malekian, “Maximizing sequence- submodular functions and its application to online advertising,” Manage. Sci., vol. 67, no. 10, pp. 6030–6054, 2021

    work page 2021

  8. [8]

    Improved bounds for the greedy strategy in optimization problems with curvature,

    Y . Liu, E. K. P. Chong, and A. Pezeshki, “Improved bounds for the greedy strategy in optimization problems with curvature,” J. Comb. Optim., vol. 37, no. 4, pp. 1126–1149, 2019

    work page 2019

  9. [9]

    String submodular functions with curvature constraints,

    Z. Zhang, E. K. P. Chong, A. Pezeshki, and W. Moran, “String submodular functions with curvature constraints,” IEEE Trans. Autom. Control, vol. 61, no. 3, pp. 601–616, 2015. 10 IEEE TRANSACTIONS ON AUTOMATIC CONTROL

    work page 2015

  10. [10]

    Approximation for maxi- mizing monotone non-decreasing set functions with a greedy method,

    Z. Wang, B. Moran, X. Wang, and Q. Pan, “Approximation for maxi- mizing monotone non-decreasing set functions with a greedy method,” J. Comb. Optim. , vol. 31, pp. 29–43, 2016

    work page 2016

  11. [11]

    A new performance bound for submodular maximization problems and its application to multi-agent optimal coverage problems,

    S. Welikala, C. G. Cassandras, H. Lin, and P. J. Antsaklis, “A new performance bound for submodular maximization problems and its application to multi-agent optimal coverage problems,” Automatica, vol. 144, p. 110493, 2022

    work page 2022

  12. [12]

    An improved greedy curvature bound in finite-horizon string optimization with an application to a sensor coverage problem,

    B. Van Over, B. Li, E. K. P. Chong, and A. Pezeshki, “An improved greedy curvature bound in finite-horizon string optimization with an application to a sensor coverage problem,” in Proc. 62nd IEEE Conf. Decision Control (CDC) , (Singapore), pp. 1257–1262, Dec. 2023

    work page 2023

  13. [13]

    On bounds for greedy schemes in string optimization based on greedy curvatures,

    B. Li, B. Van Over, E. K. P. Chong, and A. Pezeshki, “On bounds for greedy schemes in string optimization based on greedy curvatures,” in Proc. 63nd IEEE Conf. Decision Control (CDC) , (Milan, Italy), p. to appear, Dec. 2024

    work page 2024

  14. [14]

    Distributed coverage control and data collection with mobile sensor networks,

    M. Zhong and C. G. Cassandras, “Distributed coverage control and data collection with mobile sensor networks,” IEEE Trans. Autom. Control , vol. 56, no. 10, pp. 2445–2455, 2011

    work page 2011

  15. [15]

    Exploiting submodularity to quantify near-optimality in multi-agent coverage problems,

    X. Sun, C. G. Cassandras, and X. Meng, “Exploiting submodularity to quantify near-optimality in multi-agent coverage problems,” Automatica, vol. 100, pp. 349–359, 2019

    work page 2019

  16. [16]

    Combinatorial auctions with decreasing marginal utilities,

    B. Lehmann, D. Lehmann, and N. Nisan, “Combinatorial auctions with decreasing marginal utilities,” Games and Econ. Behav. , vol. 55, no. 4, pp. 270–296, 2006

    work page 2006