Pith. sign in

REVIEW 2 major objections 4 minor 12 references

Submodular Cost Submodular Cover with an Approximate Oracle

T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that the greedy algorithm for submodular cover keeps bounded approximation ratios when the benefit function is known only through an approximate, possibly non-submodular oracle.

desk verdict Sound theory for SCSC with approximate oracles; the case-study bridge from relative-error sketch to absolute-error theorem needs fixing before the empirical claims are credible. read the letter →

arxiv 1908.00653 v1 pith:TNQNQKQL submitted 2019-08-01 cs.DS

Victoria G. Crawford , Alan Kuhnle , My T. Thai This is my paper · ORCID
classification cs.DS MSC 68W2590C27
keywords submodularcoverapproximateoraclegreedyalgorithmapproximationratiocostinfluencethresholdreachabilitysketchcurvature
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper asks whether the greedy algorithm for Submodular Cost Submodular Cover (SCSC) still has provable guarantees when the benefit function cannot be evaluated exactly and is replaced by an $\epsilon$-approximate surrogate $F$. It establishes that, provided every element added by the greedy run has marginal benefit $\mu$ large enough relative to $\epsilon$, the greedy output covers the threshold up to a small loss, $f(A) \ge \tau - \epsilon$, and its cost is bounded by a ratio that degrades gracefully with $\epsilon$. This matters because in applications such as influence maximization the exact benefit is hard to compute, so optimization must run against sketches, simulations, or noisy learned surrogates that need not even be submodular. The two ratios established are incomparable: one is closer to the classical bounds but needs an exact-oracle quantity to evaluate; the other replaces that quantity with a tunable parameter and is computable from the surrogate alone.

What carries the argument

The load-bearing device is a charging argument that assigns the cost of the greedy solution to elements of the optimal solution, adapted from the integral-valued SCSC analysis of Wan et al. (2010). Because the surrogate $F$ may be non-submodular, the greedy elements $x_i$ need not exhibit diminishing cost-effectiveness, so the proof charges instead with $\tilde{x}_i$, the element that would be most cost-effective according to the true function $f$ at the same step. These $\tilde{x}_i$ have non-increasing marginal cost-effectiveness, which is exactly what the charge bound needs; the oracle error $\epsilon$ enters as an additive distortion that is absorbed using the condition $\mu > 4\epsilon c_{\max}\rho / c_{\min}$. In Theorem 2 the charge is truncated once marginal contributions fall below a level $\lambda = \gamma\mu/(n\rho)$, which trades the instance-dependent $\beta$ for the tunable $\gamma$ and makes the ratio computable from $F$ alone.

What would settle it

Construct a small SCSC instance that satisfies $\mu > 4\epsilon c_{\max}\rho / c_{\min}$ and run Algorithm 1 with an $\epsilon$-approximate but non-submodular surrogate $F$; because every constant in the theorems is explicit, checking whether the output violates $f(A) \ge \tau - \epsilon$ or exceeds the stated cost ratio would settle whether the guarantees are tight, and a search over adversarial $\pm\epsilon$ perturbations of a submodular $f$ could reveal whether the uniform-error condition is genuinely necessary.

Watch

Extended reading notes

Core claim

The central claim is that Algorithm 1, the greedy rule that repeatedly adds the element maximizing $F_\tau$-marginal gain per unit cost, is a bicriteria approximation algorithm for SCSC under an $\epsilon$-approximate oracle. In Theorem 1, whenever the smallest marginal gain $\mu$ of an added element satisfies $\mu > 4\epsilon c_{\max}\rho / c_{\min}$, the returned set satisfies $f(A) \ge \tau - \epsilon$ and $c(A) \le \frac{\rho}{1 - 4\epsilon c_{\max}\rho/(c_{\min}\mu)} (\ln(\alpha/\beta) + 2) c(A^*)$, where $A^*$ is an optimal solution. Theorem 2 replaces $\beta$ by a tunable $\gamma \in (0, 1 - 4\epsilon c_{\max}\rho/(c_{\min}\mu))$ and gives $c(A) \le \frac{\rho}{1 - 4\epsilon c_{\max}\rho/(c_{\min}\mu) - \gamma} (\ln(n\alpha\rho/(\gamma\mu)) + 2) c(A^*)$, again with $f(A) \ge \tau - \epsilon$. When $\epsilon = 0$ the guarantees reduce, up to a small additive constant, to existing SCSC ratios, and the same charging framework yields a new exact-oracle ratio in the second case. The authors also show that the two ratios are incomparable, and that the Cohen et al. average-reachability sketch used in the case study is not submodular, so the general approximate-oracle analysis is not vacuous for that oracle.

Load-bearing premise

The proof assumes the surrogate function is within $\epsilon$ of the true benefit function for every possible set, not just for the sets the greedy algorithm actually evaluates; many practical oracles, including the influence sketch used in the case study, only offer high-probability relative error on the queries made, so the uniform bound is a stronger property than the oracle delivers.

Editorial extensions

If this is right

  • If the theorems hold, SCSC admits bicriteria guarantees under sketches, simulations, and noisy learned surrogates, not just exact value oracles: the feasibility loss is only $\epsilon$, not a constant fraction of the threshold.
  • With an exact oracle ($\epsilon = 0$), the first bound becomes $\rho(\ln(\alpha/\beta) + 2)$, reproducing known SCSC ratios up to a small constant, while the second is a new incomparable exact-oracle ratio.
  • The condition $\mu > 4\epsilon c_{\max}\rho / c_{\min}$ gives a quantitative prescription: an instance is amenable to greedy whenever the smallest marginal gain of chosen elements stays large relative to the oracle error and the cost curvature.
  • For influence threshold problems, the average-reachability sketch of Cohen et al. can serve as the oracle; the empirical case study shows the two ratios take moderate values on real networks even though the sketch is non-submodular.
  • Because Theorem 2's ratio is computable from $F$ alone, it can be evaluated online during a greedy run, making the guarantee usable even when the true benefit function cannot be queried.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The requirement that $F$ be uniformly $\epsilon$-approximate on all subsets is stricter than the high-probability, query-dependent guarantee of many sketches; a natural extension is to prove versions of Theorems 1 and 2 that hold with high probability over the oracle's randomness using only the queries actually made.
  • The explicit dependence on $\epsilon/\mu$ suggests an adaptive scheme: increase sketch quality, or switch to exact evaluation, whenever marginal gains drop toward $4\epsilon c_{\max}\rho / c_{\min}$, preserving the ratio while saving computation early in the run.
  • The threshold $\mu > 4\epsilon c_{\max}\rho / c_{\min}$ hints at an inherent limitation: for instances where every feasible set contains only elements with small marginal gains, no amount of greedy tuning can satisfy the condition, and a different algorithmic approach would be needed.
  • The incomparability of the two bounds mirrors a trade-off between tightness and evaluability; one could interpolate between $\alpha/\beta$ and $n\alpha\rho/(\gamma\mu)$ to design a family of ratios with adjustable computational cost.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper studies the Submodular Cost Submodular Cover (SCSC) problem, in which a monotone submodular benefit function f must be driven above a threshold τ while minimizing a monotone submodular cost c, under the assumption that the algorithm has access only to an ε-approximate surrogate F rather than to f. The authors analyze the natural greedy algorithm (Algorithm 1), which uses the truncated surrogate Fτ = min(F, τ). Theorem 1 gives a bicriteria guarantee: if the minimum greedy marginal gain µ satisfies µ > 4εc_maxρ/c_min, then the returned set A has f(A) ≥ τ−ε and c(A) ≤ ρ/(1−4εc_maxρ/(c_minµ)) · (ln(α/β)+2) · c(A*), where A* is optimal, α is the largest singleton value of f, β is the smallest nonzero marginal gain, and ρ is the curvature of c. Theorem 2 gives an incomparable bound that replaces β by a tunable parameter γ. The proofs adapt the charging argument of Wan et al. to the sequence of f-optimal augmentations x̃_i, and the paper includes a proof that the two bounds are incomparable. Section 3 presents a case study for the Influence Threshold problem using the Cohen et al. average-reachability sketch as the surrogate, proves that this sketch is non-submodular, and reports computed values of the two ratios on Facebook and GrQc networks.

Significance. If the oracle hypothesis of Theorems 1 and 2 is satisfied, the paper provides the first approximation guarantees for SCSC under a general approximate oracle, and the zero-error limit nearly recovers existing SCSC ratios. The charging argument is a genuine extension of Wan et al.: the lower bound on Δf(A_{i-1}, x̃_i), the monotonicity of the charges ω_i, and the telescoping bound in the proofs of Theorems 1 and 2 all check out. I found no internal inconsistency in the main derivation. The paper also gives an explicit feasibility loss of τ−ε and a clean demonstration that its two bounds are incomparable. However, the practical significance claimed through the Section 3 case study is not yet established, because the oracle used there does not satisfy the deterministic all-subsets absolute-error condition assumed by the theorems. Since the main theoretical results are sound and the gap is localized to the bridge between the oracle model and the case study, the manuscript is promising but needs revision.

major comments (2)
  1. [Section 3 and §1.3] The case study does not instantiate the hypothesis of Theorems 1 and 2. The theorems require |f(X) − F(X)| ≤ ε for every X ⊆ S, deterministically. The Cohen et al. oracle is described in Section 3 as having "relative error of all queries over the duration of the greedy algorithm ... within ε with probability at least 1 − 1/n^{c−2}", which is a high-probability, query-dependent, relative-error guarantee. The conversion in Section 1.3 from relative to absolute error uses B = τ as an upper bound on f "over the duration of Algorithm 1", but this is not justified: sets such as an optimal solution A* can have f(A*) ≥ τ, and the sketch estimates f, not the truncated function fτ. Truncating f and F after the fact does not preserve a relative-error guarantee for the sketch. Consequently, the ratios r1 and r2 plotted in Figures 3 and 4 are not proven approximation ratios for those runs. The authors should either prove a version of Theorems 1 and 2 under a high-probability per-query relative-error oracle (noting that the proof only queries sets of the form A_{i-1}, A_{i-1} ∪ {x}, A_{i-1} ∪ {x̃_i}, and the final A, so a union bound over polynomially many queries is feasible), or explicitly present the experiments as a heuristic illustration rather than an instantiation of the theorems.
  2. [Appendix A.2] The proof of Theorem 1 (Alternative) contains an unjustified inequality. The proof states that for all x, ΔF(A, x) ≤ c(x)/c(x_k) · ΔF(A, x_k) ≤ (c_max/c_min)µ*, but Algorithm 1 selects x_k by maximizing ΔFτ(A, x)/c(x), not ΔF(A, x)/c(x). When F(A ∪ {x}) crosses the threshold τ, ΔFτ is at most τ − F(A), while ΔF(A, x) can be much larger. The subsequent conclusion that Δf(A, x) ≤ (c_max/c_min)µ* + 2ε for all x therefore does not follow as written. The theorem may be salvageable by splitting into the case where some remaining element crosses τ and the case where none does, but the proof is incomplete in its current form.
minor comments (4)
  1. [Section 3 and Appendix D] The procedure for computing the upper bound on the Theorem 2 ratio from F alone is under-specified. The text says α and µ are bounded using F, but it does not give the exact formulas; for reproducibility the authors should state, for example, that α ≤ max_x(F({x}) + ε) and that µ can be lower bounded from the F-marginals of the chosen elements, together with the γ-selection rule used in the experiments.
  2. [Section 2.1] The discussion states that the curvature ρ of c is assumed to be computable, but for a general monotone submodular cost function curvature is defined as a maximum over exponentially many subsets. The experiments use modular costs (ρ = 1) or manually chosen curvature values; the paper should at least note that computing ρ exactly is nontrivial in general.
  3. [Section 1.3] The definition of µ as min{fτ(A_i) − fτ(A_{i−1}) : i ∈ {1,...,k}} is not meaningful when k = 0; the proof handles k = 0 separately, but the definition and theorem statements should be adjusted to avoid an undefined quantity in the empty case.
  4. [Section 3] The experimental plots omit runs where the minimum marginal gain is too small relative to ε, and the text notes this. It would be helpful to state how many runs were omitted for each threshold, since the plotted values are conditional on the theorem condition and do not by themselves establish that the ratios are achievable at those thresholds.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: The central theorems are derived from explicit approximation and submodularity assumptions; the case-study oracle mismatch is an applicability gap, not a circular reduction.

full rationale

The central derivation is self-contained. Theorems 1 and 2 start from the stated definition that F is an absolute epsilon-approximation to f, the submodularity of f and c, and the condition mu > 4*epsilon*cmax*rho/cmin; the proof adapts the external Wan et al. charging argument to the sequence x-tilde_i and carries explicit error terms (e.g., equations (2)-(6) in Appendix B) rather than assuming the desired cost bound. The quantities alpha, beta, mu, rho, cmin, and cmax are instance parameters that are not fitted to force a ratio, and no fitted quantity is renamed as a prediction. The Cohen et al. sketch is cited as an external oracle construction, not as a prior result of the present authors, and the gap between its high-probability, query-based relative-error guarantee and the theorem's deterministic all-subsets absolute-error hypothesis is a correctness/bridge concern for Section 3, not a circular step. Self-citations (Kuhnle et al. 2017, 2018; Zhang et al. 2016) appear in related work and experimental context and do not carry any load-bearing step of the proof. No uniqueness theorem or ansatz is imported from the authors' prior work, and the empirical ratios are computed by querying f or F rather than produced by construction from the claimed ratios. Therefore no circularity is present.

Assumptions & free parameters 1 free parameters · 5 assumptions · 0 invented entities

The central theorems rest on the standard SCSC model assumptions (monotone submodular f and c), the absolute-error approximate oracle model, and standard properties of submodular functions such as truncation and curvature. The only tunable quantity in the bounds is γ in Theorem 2, which does not affect validity; no data-dependent constants are fitted to make the results hold.

free parameters (1)
  • γ (Theorem 2 tuning parameter) = variable; optimized by discretized search during experiments
    Theorem 2 holds for any γ in (0, 1−4ϵcmaxρ/(cminµ)); the experimental section selects γ that minimizes the upper bound. This is a degree of freedom in the guarantee, not a data-fitted constant.
assumptions (5)
  • domain assumption f and c are monotone submodular with f(∅)=0 and c(X)=0 iff X=∅.
    This is the definition of SCSC, stated in Section 1.
  • domain assumption F satisfies |f(X)−F(X)| ≤ ϵ for all X ⊆ S.
    This is the approximate oracle model defined in Section 1.3.
  • standard math Truncation at τ preserves monotone submodularity and the absolute error bound.
    Used at the start of the proofs: 'Without loss of generality we redefine f = min{f,τ} and F = min{F,τ}'. This is a known property of monotone submodular functions.
  • standard math The curvature ρ satisfies c(A) ≤ ∑_{x∈A} c({x}) ≤ ρ c(A) for all A.
    Follows directly from the definition of ρ in Section 1.3.
  • domain assumption The Cohen et al. bottom-k sketch provides relative error within ϵ for all greedy queries with probability at least 1−1/n^{c−2}.
    Cited from Cohen et al. (2014) and used in Section 3 to claim F is an ϵ-approximation in the case study.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Submodular Cost Submodular Cover with an Approximate Oracle." pith.science (2026). https://pith.science/paper/TNQNQKQL

@misc{pith2026190800653,
  author       = {Pith},
  title        = {Pith review of: Submodular Cost Submodular Cover with an Approximate Oracle},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TNQNQKQL}},
  note         = {Machine review of arXiv:1908.00653}
}
read the original abstract

In this work, we study the Submodular Cost Submodular Cover problem, which is to minimize the submodular cost required to ensure that the submodular benefit function exceeds a given threshold. Existing approximation ratios for the greedy algorithm assume a value oracle to the benefit function. However, access to a value oracle is not a realistic assumption for many applications of this problem, where the benefit function is difficult to compute. We present two incomparable approximation ratios for this problem with an approximate value oracle and demonstrate that the ratios take on empirically relevant values through a case study with the Influence Threshold problem in online social networks.

Figures

Figures reproduced from arXiv: 1908.00653 by the authors.

Figure 1
Figure 1. Instance G1, G2 and G3 (in that order from left to right) from the proof of Proposition 1. 0 r 2 z r 2 x r 1 z r 3 z r 3 y r 2 y r 1 y r 1 x r 3 x 1 [PITH_FULL_IMAGE:figures/full_fig_p010_1.png] view at source ↗
Figure 3
Figure 3. The approximation ratios of Theorem 1 (r1) and an upper bound on that of Theorem 2 (r2) at [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figure 1
Figure 1. Suppose that we construct the approximate reachability oracle of Cohen et al. with k = 5, and the randomly generated mapping from vertex, instance pairs to the interval [0, 1] is as depicted in [PITH_FULL_IMAGE:figures/full_fig_p011_1.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: The approximation ratios of Theorem 1 (r1) and an upper bound on that of Theorem 2 (r2) at [PITH_FULL_IMAGE:figures/full_fig_p023_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

  1. [5]

    URL http://arxiv.org/abs/1805.06990. J. Leskovec and J. J. Mcauley. Learning to discover social circles in ego networks. In Advances in neural information processing systems, pages 539–547,

    work page Pith review arXiv

  2. [7]

    Singla, S

    14 A. Singla, S. Tschiatschek, and A. Krause. Noisy submodular maximization via adaptive sampling with applications to crowdsourced image collection summarization. In AAAI, pages 2037–2043,

    work page

  3. [12]

    For eachy∈A∗, ifπ1(y)≤λ we setmy = 0, otherwisemy is the value in{1,...,k} such that ifi∈{ 1,...,m y} thenπi(y)>λ , and ifi∈{my + 1,...,k} thenπi(y)≤λ

    We first define a valuemy for everyy∈A∗. For eachy∈A∗, ifπ1(y)≤λ we setmy = 0, otherwisemy is the value in{1,...,k} such that ifi∈{ 1,...,m y} thenπi(y)>λ , and ifi∈{my + 1,...,k} thenπi(y)≤λ. Such anmy can be set sincef is submodular and monotonic. Then w(y) = my∑ i=1 (πi(y)−πi+1(y))ωi + k∑ i=my+1 (πi(y)−πi+1(y))ωi. (2) A similar analysis as in the proof o...

    work page 2003

  4. [1982]

    Zhang, A

    H. Zhang, A. Kuhnle, H. Zhang, and M. T. Thai. Detecting misinformation in online social networks before it is too late. In Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, pages 541–548. IEEE Press,

    work page 2016

  5. [2003]

    Kuhnle, T

    A. Kuhnle, T. Pan, M. A. Alim, and M. T. Thai. Scalable bicriteria algorithms for the threshold activation problem in online social networks. In INFOCOM 2017-IEEE Conference on Computer Communications, IEEE, pages 1–9. IEEE,

    work page 2017

  6. [2007]

    X. Li, J. D. Smith, T. N. Dinh, and M. T. Thai. Why approximate when you can get the exact? optimal targeted viral marketing at scale. In IEEE INFOCOM 2017-IEEE Conference on Computer Communications, pages 1–9. IEEE,

    work page 2017

  7. [2010]

    K. Wei, Y . Liu, K. Kirchhoff, and J. Bilmes. Using document summarization techniques for speech data subset selection. In Proceedings of the 2013 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 721–726,

    work page 2013

  8. [2011]

    K. Han, Y . He, S. Tang, H. Huang, and C. Xu. Cost-effective seed selection in online social networks.arXiv preprint arXiv:1711.10665,

    work page Pith review arXiv

Show all 12 references
  1. [2014]

    T. N. Dinh, H. Zhang, D. T. Nguyen, and M. T. Thai. Cost-effective viral marketing for time-critical campaigns in large-scale social networks. IEEE/ACM Transactions on Networking (ToN), 22(6):2001–2011,

    2001

  2. [2015]

    Y . Tang, X. Xiao, and Y . Shi. Influence maximization: Near-optimal time complexity meets practical efficiency. In Proceedings of the 2014 ACM SIGMOD international conference on Management of data, pages 75–86. ACM,

    2014

  3. [2016]

    15 A Additional Approximation Results A.1 The case of monotone submodular F The main difficulty in proving Theorems 1 and 2 in Section 2.1 is that the ϵ-approximate oracle F is not monotone submodular. In the event thatF is monotone submodular, existing results for SCSC [Wolsey...

    1982

  4. [2018]

    URL http://arxiv.org/abs/1707.04347. W. Chen, C. Wang, and Y . Wang. Scalable influence maximization for prevalent viral marketing in large-scale social networks. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1029–1...

    arXiv

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.