Pith. sign in

REVIEW 2 major objections 4 minor 8 references

Improving Online Bin Covering with Little Advice

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

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

Pith's one-line read An online bin-covering strategy using O(log log n) bits of advice is shown to asymptotically cover at least 135/242 ≈ 0.5578 of the optimal number of bins.

desk verdict A real improvement in the competitive ratio, but a concrete gap in the Lemma 3 partition argument means the main theorem is not yet proven. read the letter →

arxiv 2506.09004 v1 pith:5GHMB47V submitted 2025-06-10 cs.DS

Andrej Brodnik , Bengt J. Nilsson , Gordana Vujović This is my paper
classification cs.DS MSC 68W2768Q17
keywords bincoveringonlinealgorithmsadvicecomplexitycompetitiveanalysisdualharmonicstrategyworstfitreservedbinsO(loglogn)
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 online bin covering problem asks an algorithm to place items of size between 0 and 1 into unit bins as they arrive, maximizing the number of bins whose contents sum to at least 1. The paper establishes that a strategy which may read a very short advice string, O(log log n) bits where n is the input length, asymptotically covers at least 135/242 ≈ 0.5578 of the bins covered by an optimal offline solution, improving the previous certified ratio of 8/15 ≈ 0.5333 for the same advice budget. The improvement is obtained by rebalancing how many bins are reserved for 2-items (items of size at least 1/2), splitting the remaining 2-items into carefully chosen chunks, and tracking the resulting loss with a parameterized inequality. A sympathetic reader should care because this narrows the gap between the 1/2 barrier for algorithms with no advice and the near-1 ratios achievable with a linear number of advice bits, while using advice so small it costs almost nothing to transmit.

What carries the argument

The central object is an $(\alpha, \alpha', \rho, \epsilon)$-viable covering. It splits the subsequence of 2-items into an early part and a late part of lengths $(1-\rho)T_2$ and $\rho T_2$; in the early part at least $\lfloor\alpha |G_2|\rfloor$ bins contain exactly one 2-item plus small items, in the late part at least $\lfloor\alpha' |G_2|\rfloor$ such bins appear, the remaining early 2-items are paired two-by-two, and leftover small items cover $2|G_S|/3 - O(\epsilon|G_2|)$ more bins. Lemma 2 converts this structure into the counting bound $\min\{( (1-\rho)(2\beta-1)+\alpha+2\alpha' )/(2\beta),\ 2/3\} \cdot |OPT| - O(\epsilon|G_2|)$. The strategy $DH_2^b$ realizes the structure by reserving $m_R^{-b}$ bins, declaring the $|G_2| - 2m$ largest 2-items to be good, filling black reserved bins with black small items via a threshold rule, and filling white reserved bins with white items by dual worst fit; Lemma 4 then guarantees every good item ends up in a covered bin.

What would settle it

Find one input sequence for which, in Case 2 of Lemma 3, no split of the final 2-item subsequence into consecutive chunks $X_L$, $X_R$, $Y$ satisfies $X_L^{-b}+X_R^{-b}+Y=Z$ together with the three upper-bound inequalities and the prescribed good-item counts; alternatively, simulate $DH_2^b$ on the worst-case family implied by failing one of the five constraints and check whether the covered bins fall below $(135/242)|OPT| - C$.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 1: the Dual Harmonic strategy $DH_2^b$ with $b = 2\log\log n$, using $O(\log\log n)$ bits of advice, achieves asymptotic competitive ratio at least $135/242 - O(1/\log n) \approx 0.5578 - O(1/\log n)$. The proof splits the analysis according to the parameter $\beta = (|G_{22}| + |G_2|)/|G_2|$. If $\beta \ge 121/107$, the plain $DH_2$ strategy already certifies the bound; otherwise the oracle sends a constant number of $b$-bit approximations and selection bits, and the strategy produces either an $(\alpha, \epsilon)$-desirable covering or one of two $(\alpha, \alpha', \rho, \epsilon)$-viable coverings. Choosing $\delta_T = 1/11$, $\alpha_T^L = 5\alpha/14$, $\rho = 13/121$, and $\rho' = 26/121$ balances the three cases so that each yields at least $135/242 - O(1/\log n)$, with the additive loss controlled by $\epsilon = 2/\log n$.

Load-bearing premise

The proof assumes that for every input the last block of 2-items splits into three consecutive parts whose lengths and good-item counts satisfy five specific constraints, and it does not prove that such a split always exists.

Editorial extensions

If this is right

  • With only $O(\log\log n)$ bits of advice, an online bin-covering strategy now has a certified ratio of about 0.5578, strictly above the 1/2 limit for pure online strategies.
  • The same advice budget as in the previous 8/15 bound now yields a larger constant; the gain comes from rebalancing parameters, not from reading more advice.
  • The lower bound that $o(\log\log n)$ advice cannot beat 1/2 remains intact, so 0.5578 is currently the best known point on this segment of the advice-versus-ratio curve.
  • The explicit parameter choices ($\delta_T = 1/11$, $\alpha_T^L = 5\alpha/14$, $\rho = 13/121$, $\rho' = 26/121$) give future improvements a concrete benchmark to beat within the same proof framework.

Reading between the lines

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

  • The authors do not optimize the four balancing parameters; a numerical search over the feasible region of Lemma 3's inequalities might push the ratio modestly higher without any new algorithmic idea.
  • The proof's weakest spot is the unstated existence of the chunk partition in Case 2; if that partition can fail for some input, the theorem's proof would need a different split rule even if the ratio itself survives.
  • The same two-class template could likely be extended to three item classes (items of size at least 1/3 join the picture), which in the exact-advice setting gives 2/3; such an extension would trade a slightly larger advice string for a ratio closer to 2/3.
  • The black/white item accounting shows the strategy tolerates an $O(\epsilon|G_2|)$ error in small-item supply; a randomized variant without advice would still face the 1/2 pure-strategy barrier, so the advice is genuinely buying the chunk-selection coordination.
Share X Bluesky LinkedIn Reddit HN

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 online bin covering problem with advice. It claims that the DH_2^b strategy of Boyar et al., using O(log log n) bits of advice, can be analyzed and slightly modified to achieve an asymptotic competitive ratio of 135/242 - O(1/log n), improving the previous 8/15. The proof proceeds by defining (α, α', ρ, ε)-viable coverings and a case analysis (Lemma 3) on how 2-items are placed, together with a small-item packing analysis (Lemmas 4 and 5). The main theorem then chooses constants δ_T = 1/11, α_T^L = 5α/14, ρ = 13/121, and ρ' = 26/121 and optimizes over β and α.

Significance. If the claimed ratio were established, it would be a meaningful improvement over the previous best O(log log n)-advice result and would further demonstrate the power of even logarithmic advice in online bin covering. The paper gives explicit parameter choices and cleanly reduces the problem to checking a small number of algebraic inequalities, which is a useful framework. However, the core lemma (Lemma 3) contains an unproved and in fact false assertion about the existence of a chunk partition of the final subsequence of 2-items; since the subsequent cases and the main theorem depend on this partition, the main result is not supported by the submitted proof. The paper also relies on known inequality (2) from [4] and the framework of [3], which are appropriate prior results.

major comments (2)
  1. [4.1, Lemma 3, Case 2] The existence of the partition of the last subsequence into chunks X_L, X_R, Y with the stated size constraints is asserted without proof, and it is not always possible. For β = 1, |G2| = 100, and ε = 0.001, the definition gives m_R = floor((1-ε)^2 · 27·100/121) = 22, so m_R^{-b} ≤ 22 and Z = T_2 - 3m_R^{-b} = 100 - 3·22 = 34. The three constraints X_L+X_R ≤ m_R^{-b}, X_L+Y ≤ m_R^{-b}, and X_R+Y ≤ m_R^{-b} imply 2Z = 2(X_L+X_R+Y) ≤ 3m_R^{-b}, i.e., 68 ≤ 66, which is impossible. Hence no nonnegative integers X_L, X_R, Y satisfy the case-2 hypotheses. Because Cases 2a–2c and Lemma 2 all rely on this partition, the proof of Theorem 1 is not valid as written. The paper gives neither an existence argument nor a handling of rounding/approximation errors (e.g., the difference between m_R and m_R^{-b}).
  2. [4.1, Lemma 3, Case 2] Even setting aside the numerical impossibility above, the lemma asserts not only size constraints but also that the initial two chunks contain prescribed numbers of good items (⌊α_L|G2|⌋^{-b} in the first chunk and the remainder in the second). These good-item count conditions are coupled with the size equations, and the proof does not justify that a consecutive partition of the input subsequence can simultaneously satisfy both. A separate feasibility argument is needed; the current text simply states 'The initial two chunks contain ...' as if it follows from the size constraints.
minor comments (4)
  1. [4, Property I] Typo: 'subsquence' should be 'subsequence'.
  2. [2 and 4.1] The notation m_R^{-b} is used both for the b-bit lower approximation of an integer (a rational number) and for an exact integer count of items (e.g., 'exactly m_R^{-b} 2-items each'). These uses should be disambiguated; otherwise the reader cannot verify the arithmetic in Lemma 3.
  3. [Theorem 1] The choices ρ = 13/121 and ρ' = 26/121 are introduced without derivation. Since the competitive ratio expression in Lemma 2 depends linearly on ρ and ρ', the proof would be clearer if it showed how these values are obtained from the balance conditions in Cases 2b and 2c.
  4. [4.2, Lemma 4] The inequality chain in the d ≥ ε case is compressed; in particular, the step from 2d^{+b} m_W to 2(d+1/2^b)(m_R - (1-ε)^2 m_{RB}) uses m_R^{-b} ≤ m_R and m_B^{-b} ≥ (1-ε)m_B without a note. Expanding these steps would help the reader verify the 'which holds for 1/2^{b/2} < ε sufficiently small' claim.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the improved ratio is an analytical consequence of the prior Boyar et al. framework, and the asserted Case 2 partition is a correctness gap rather than a self-referential derivation.

full rationale

The derivation chain is not circular in the sense of fitting a parameter and then renaming it as a prediction. Lemma 2 is obtained by a purely algebraic lower-bound calculation from the three properties of an (alpha, alpha-prime, rho, epsilon)-viable covering, and Theorem 1 substitutes chosen constants delta_T = 1/11, alpha_T^L = 5*alpha/14, rho = 13/121, and rho-prime = 26/121 to balance the three cases; this is parameter optimization, not fitting the target ratio. The only input from the present authors' earlier work is Inequality (2) from Brodnik et al. [4], used in Lemma 5 to bound DNF small-item bins; that inequality is a standard, parameter-free competitive-ratio statement about DNF with items bounded by alpha < 1, and it does not assume the 135/242 bound, so it is independent support rather than a self-citation that carries the target result. The Boyar et al. [3] results used as lemmas are external to the present author set and are invoked as prior theorems, which is normal derivation rather than circularity. I do flag a substantial non-circular proof gap: in Section 4.1, Lemma 3, Case 2, the paper asserts, without existence proof, that the final Z = T_2 - 3*m_R^{-b} 2-items can be partitioned into chunks X_L, X_R, and Y satisfying X_L + X_R + Y = Z, X_L + X_R <= m_R^{-b}, X_L + Y <= m_R^{-b}, and X_R + Y <= m_R^{-b}; for beta = 1 and N = 100, these constraints give 2Z = 68 > 66 = 3*m_R^{-b}, so no such partition exists for that parameter choice. This is a serious correctness risk for Theorem 1, but it is not circularity, because the claimed bound is not defined in terms of itself and the proof does not reuse the target competitive ratio as an input.

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

The proof introduces several constants (delta_T, alpha_L^T, rho, rho', the weights in m_R) chosen to balance case inequalities; these are analytically optimized, not fitted to data. The central derivation inherits two prior results from the same research line ([3] and the authors' own [4]) and one asserted chunk-partition existence statement, which is the most fragile premise.

free parameters (6)
  • epsilon = 2/log n in Theorem 1
    Error parameter controlling b-bit approximation; chosen as 2/2^{b/2} with b = 2 log log n. It enters all case bounds as -epsilon terms.
  • delta_T = 1/11
    Threshold separating Case 2a from Cases 2b/2c in Lemma 3; chosen to balance the three competitive-ratio inequalities.
  • alpha_L^T = 5 alpha / 14
    Threshold on the fraction of good items in the first chunk; chosen to balance Case 2b and Case 2c.
  • rho = 13/121
    Fraction of 2-items in the third chunk in Case 2b; chosen to make the lower bound equal 135/242 at beta = 1.
  • rho_prime = 26/121
    Fraction of 2-items in the last two chunks in Case 2c; chosen to balance the third inequality.
  • coefficients in m_R = 27/121 and 2/3
    Weights of |G2| and |G22| in the definition of the number of reserved bins m_R; these constants are selected so the derived lower bound reaches 135/242.
assumptions (5)
  • domain assumption Inequality (2) from Brodnik et al. [4]: |DNF(sigma_alpha)| > 1/(1+alpha)|OPT| - 1/(1+alpha).
    Used in Lemma 5 to bound the number of small-item-only bins; from the authors' own prior work, not re-proved here.
  • domain assumption Boyar et al. [3] results, including the (alpha,epsilon)-desirable covering framework, Expression (4), and their Lemma 1, are correct.
    Lemma 1 and the base covering bound in the proof of Theorem 1 inherit these results.
  • domain assumption The optimal solution can be partitioned into G22, G2, GS with the bins in G2 containing the |G2| largest 2-items and with the small-item exchange properties used in Section 4.2.
    Justified only by 'simple exchange argument' in Section 4.2; essential for the small-item supply bounds in Lemma 4.
  • ad hoc to paper The chunk partition in Case 2 of Lemma 3 exists with the stated size and good-count constraints.
    Asserted without proof; the whole case analysis depends on it.
  • standard math The b-bit fixed-point approximation satisfies v^{-b} >= (1-tau)v and v^{+b} <= (1+tau)v with tau = 2^{-b+1}, and integers up to n can be approximated with O(log log n) bits.
    Used throughout to justify the approximation error terms and the O(log log n) advice bound.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Improving Online Bin Covering with Little Advice." pith.science (2026). https://pith.science/paper/5GHMB47V

@misc{pith2026250609004,
  author       = {Pith},
  title        = {Pith review of: Improving Online Bin Covering with Little Advice},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5GHMB47V}},
  note         = {Machine review of arXiv:2506.09004}
}
abstract

The online bin covering problem is: given an input sequence of items find a placement of the items in the maximum number of bins such that the sum of the items' sizes in each bin is at least~1. Boyar~{\em et~al}.\@~\cite{boyar2021} present a strategy that with $O(\log \log n)$ bits of advice, where $n$ is the length of the input sequence, achieves a competitive ratio of $8/15\approx0.5333\ldots$. We show that with a strengthened analysis and some minor improvements, the same strategy achieves the significantly improved competitive ratio of~$135/242\approx0.5578\ldots$, still using $O(\log \log n)$ bits of advice.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

8 extracted references · 8 canonical work pages

  1. [4]

    Larsen, and Alejandro L\' o pez-Ortiz

    Joan Boyar, Shahin Kamali, Kim S. Larsen, and Alejandro L\' o pez-Ortiz. Online bin packing with advice. Algorithmica , 74(1):507--527, 2016

    work page 2016

  2. [3]

    Favrholdt, Shahin Kamali, and Kim S

    Joan Boyar, Lene M. Favrholdt, Shahin Kamali, and Kim S. Larsen. Online bin covering with advice. Algorithmica , 83(3):795--821, 2021

    work page 2021

  3. [1]

    Johnson, Daniel J

    Susan Fera Assmann, David S. Johnson, Daniel J. Kleitman, and Joseph Y-T. Leung. On a dual version of the one-dimensional bin packing problem. Journal of Algorithms , 5(4):502--525, 1984

    work page 1984

  4. [2]

    Problems in discrete applied mathematics

    Susan Fera Assmann. Problems in discrete applied mathematics . PhD thesis, Massachusetts Institute of Technology, 1983

    work page 1983

  5. [5]

    Nilsson, and Gordana Vujovic

    Andrej Brodnik, Bengt J. Nilsson, and Gordana Vujovic. Online bin covering with exact advice. Proc. Middle-European Conference on Applied Theoretical Computer Science , MATCOS-22, 2022. Accepted to Informatica, International Journal of Computing and Informatics , 2024

    work page 2022

  6. [6]

    o ckenhauer, Dennis Komm, Rastislav Kr\' a lovi c , Richard Kr\' a lovi c , and Tobias M\

    Hans-Joachim B\" o ckenhauer, Dennis Komm, Rastislav Kr\' a lovi c , Richard Kr\' a lovi c , and Tobias M\" o mke. Online algorithms with advice: the tape model. Information and Computation , 254:59--83, 2017

    work page 2017

  7. [7]

    Online algorithms for a dual version of bin packing

    J\' a nos Csirik and Vilmos Totik. Online algorithms for a dual version of bin packing. Discrete Applied Mathematics , 21(2):163--167, 1988

    work page 1988

  8. [8]

    An Introduction to Online Computation --- Determinism, Randomization, Advice

    Dennis Komm. An Introduction to Online Computation --- Determinism, Randomization, Advice . Springer, Texts in Theoretical Computer Science. ISBN 978-3-319-42747-8, 2016

    work page 2016

Pith tools

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