{"id":"a0796baa-1039-4f9f-838f-831f43154c27","arxiv_id":"2506.09004","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"A modified online bin-covering strategy with O(log log n) advice bits is proven to cover at least 135/242 - O(1/log n) of the optimal number of bins, improving the previous 8/15.","lead":"This paper improves the best known competitive ratio for online bin covering with a small advice tape, from 8/15 to 135/242. The improvement comes from a sharper worst-case analysis of an existing strategy plus a few changes, still using O(log log n) advice bits.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3, Case 2 assumes a partition of the last 2-item subsequence that can be impossible: for β=1 and |G2|=100, the constraints require 2Z≤66 but Z=34, so Theorem 1's proof has a concrete gap.","rationale":"Lemma 3 is the only place that connects the advice strategy's 2-item handling to the constants 135/242. My check of the algebra in Section 4.1 shows the proof of Case 2 postulates a partition whose necessary condition 2Z≤3m_R^{-b} can fail under the paper's own rounding convention. This is a sharper form of the reader's weakest assumption: the partition is not merely unproved; for β=1, N=100 it cannot exist. The asymptotic statement might survive after choosing m_R with ceil or after adding a residue-class argument, but as written the central claim is unsupported. I do not see another equally consequential flaw: the reductions to Lemma 1 and Lemma 2 are standard, the small-item argument (Lemma 4/5) follows the cited framework, and the advice-bit count O(log log n) is appropriate. The result may well be true, but the proof requires a nontrivial repair. Therefore I would keep the reader's conditional verdict, with the required revision clearly identified: prove or replace the Case 2 partition.","tokens_in":11666,"tokens_out":27775,"duration_ms":308011,"concrete_test":"Write a short script that, for β∈[1,121/107) and N up to 10^6 with ε=2/2^{b/2} as in Theorem 1, checks whether the system X_L+X_R+Y=Z, X_L+X_R≤m, X_L+Y≤m, X_R+Y≤m has a nonnegative integer solution, where m=m_R^{-b} and Z=(2β−1)N−3m. The necessary and sufficient condition is 2Z≤3m; report every (N,β) where it fails. For β=1, N=100 it fails, confirming the counterexample; if the set of failures is infinite as n varies, the proof of Lemma 3 must be revised before Theorem 1 can be accepted.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 4.1, Lemma 3, Case 2 is the pivotal step feeding Theorem 1. It asserts that the final subsequence of Z=T2−3m_R^{-b} 2-items can be split into consecutive chunks X_L, X_R, Y with X_L+X_R+Y=Z and X_L+X_R≤m_R^{-b}, X_L+Y≤m_R^{-b}, X_R+Y≤m_R^{-b}. Adding these three inequalities forces 2Z≤3m_R^{-b}. This necessary condition is not guaranteed by the paper's definitions. Take β=1, so T2=|G2|=N, and N=100. For any sufficiently small ε (e.g., ε=0.001), m_R=⌊(1−ε)^2·27·100/121⌋=22, so m_R^{-b}=22 and Z=100−66=34. Then 2Z=68>66=3m_R^{-b}; no nonnegative integers X_L, X_R, Y can satisfy the three pairwise inequalities, regardless of α or δ. The proof simply postulates the partition; neither an existence argument nor an accounting of rounding loss is given. Since Cases 2a–2c and Lemma 2 all depend on this partition, the claimed 135/242−O(1/log n) bound is not established. The gap is not merely cosmetic: for inputs with β=1 and ε not extremely small, the same failure occurs for all N, not just N=100.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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 α.","tokens_in":12041,"tokens_out":5966,"duration_ms":62330,"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":[{"comment":"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}).","section":"4.1, Lemma 3, Case 2"},{"comment":"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.","section":"4.1, Lemma 3, Case 2"}],"minor_comments":[{"comment":"Typo: 'subsquence' should be 'subsequence'.","section":"4, Property I"},{"comment":"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.","section":"2 and 4.1"},{"comment":"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.","section":"Theorem 1"},{"comment":"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.","section":"4.2, Lemma 4"}],"recommendation":"major_revision","confidential_remarks":"The main gap in Lemma 3 is concrete and reproducible, so the current version cannot be accepted. However, the asymptotic parameter regime (large |G2|, small ε) appears close to satisfying the necessary condition 2Z ≤ 3m_R^{-b}, so there is a plausible fix by adding an explicit feasibility argument and absorbing small-n cases in the additive constant. The authors should also double-check the good-count constraints in the same lemma. I recommend a major revision focused on Lemma 3 rather than rejection, because the strategy and high-level approach remain promising."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"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.\n\nWhat is actually new: the paper raises the best known competitive ratio for online bin covering with O(log log n) advice from 8/15 to 135/242, using a modified analysis of the Boyar et al. strategy. The (α, α′, ρ, ε)-viable covering framework is a natural generalization of the earlier (α, ε)-desirable covering, and the four-way split of the 2-item subsequence is a genuine extension. The constant tuning is done analytically, not fitted, and the algebra in the three cases of Theorem 1 checks out internally. For that reason the paper deserves a serious referee even though I do not think it is publishable as is.\n\nThe soft spot is in Lemma 3, Case 2. The proof asserts, without argument, that the final chunk of Z = T2 − 3m_R^{-b} 2-items can be partitioned into consecutive subchunks X_L, X_R, Y satisfying three pairwise inequalities. Adding those inequalities gives 2Z ≤ 3m_R^{-b}. This necessary condition is not guaranteed. The stress-test example is correct: with β = 1, so |G22| = 0 and T2 = |G2|, take |G2| = 100 and ε = 0.001. Then m_R = floor(0.998·(27/121)·100) = 22, so 3m_R^{-b} = 66 and Z = 34; 2Z = 68 > 66, so no nonnegative integers X_L, X_R, Y can satisfy the three constraints. This is not a floating-point artifact: the continuous margin between 2Z and 3m_R is only about 0.004N for small ε, and the floor in m_R can easily exceed that, so the failure occurs for infinitely many inputs. Since Cases 2a, 2b, and 2c all rely on this partition, the proof of Theorem 1 is incomplete.\n\nOther concerns are minor by comparison. Lemmas 4 and 5 follow the Boyar et al. template closely, and the small-items argument is rather compressed, but the reasoning is recognizable and probably sound. The reliance on the authors' own Inequality (2) from [4] is acceptable because that result is formally stated and proven elsewhere.\n\nBottom line: the result is likely fixable, but the authors need to supply either an existence proof for the chunk partition or a modification of m_R that absorbs the rounding loss. Who is this for? Researchers in online algorithms with advice. I would send this to peer review, but I would not accept it until the Lemma 3 gap is closed.","headline":"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.","tokens_in":12564,"tokens_out":6880,"would_cite":false,"duration_ms":71963,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W27","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["bin covering","online algorithms","advice complexity","competitive analysis","dual harmonic strategy","dual worst fit","reserved bins","O(log log n) advice"],"falsifier":"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$.","tokens_in":11500,"feed_emoji":"📦","tokens_out":7559,"duration_ms":79673,"temperature":0.7,"pith_summary":"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.","feed_headline":"Tiny advice lifts bin covering to 0.5578 of optimum","feed_subtitle":"The same online strategy, rebalanced and re-analyzed, outdoes the previous 8/15 bound with O(log log n) advice bits.","key_machinery":"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.","core_discovery":"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$.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies Dual Next Fit and the DNF bound for $\\alpha$-bounded items used to count small-item bins.","marker":"[1]"},{"why":"The previous $O(\\log\\log n)$-advice strategy and 8/15 analysis that this paper rebalances and sharpens.","marker":"[3]"},{"why":"Provides the exact-advice $DH_4$ strategy and the DNF inequality for items bounded by $\\alpha$.","marker":"[4]"},{"why":"Defines the advice-on-tape model of an oracle writing a bit string the strategy can read.","marker":"[5]"},{"why":"Shows no pure online strategy can beat 1/2, setting the baseline the new ratio improves.","marker":"[6]"},{"why":"Gives the self-delimiting encoding that lets the strategy handle variable-length advice without an explicit length field.","marker":"[7]"}],"fun_headline_variants":["Better bin covering ratio with O(log log n) advice","Old strategy, new analysis: bin covering hits 0.5578","Same small advice, better competitive ratio for bin covering","Bin covering improved: 0.5578 with little advice","Little advice, bigger payoff in online bin covering"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Better bin covering ratio with O(log log n) advice","Old strategy, new analysis: bin covering hits 0.5578","Same small advice, better competitive ratio for bin covering","Bin covering improved: 0.5578 with little advice","Little advice, bigger payoff in online bin covering"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000937,"raw_usage":{"total_tokens":4005,"prompt_tokens":942,"completion_tokens":3063,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":558,"completion_tokens_details":{"reasoning_tokens":2991}},"tokens_in":558,"tokens_out":3063,"duration_ms":23038,"temperature":1.0,"reasoning_tokens":2991,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T04:59:31.427453+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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$.","supporting_citations":[{"cited_title":"Johnson, Daniel J","cited_arxiv_id":null,"evidence_quote":"Supplies Dual Next Fit and the DNF bound for $\\alpha$-bounded items used to count small-item bins."},{"cited_title":"Favrholdt, Shahin Kamali, and Kim S","cited_arxiv_id":null,"evidence_quote":"The previous $O(\\log\\log n)$-advice strategy and 8/15 analysis that this paper rebalances and sharpens."},{"cited_title":"Larsen, and Alejandro L\\' o pez-Ortiz","cited_arxiv_id":null,"evidence_quote":"Provides the exact-advice $DH_4$ strategy and the DNF inequality for items bounded by $\\alpha$."},{"cited_title":"Nilsson, and Gordana Vujovic","cited_arxiv_id":null,"evidence_quote":"Defines the advice-on-tape model of an oracle writing a bit string the strategy can read."},{"cited_title":"o ckenhauer, Dennis Komm, Rastislav Kr\\' a lovi c , Richard Kr\\' a lovi c , and Tobias M\\","cited_arxiv_id":null,"evidence_quote":"Shows no pure online strategy can beat 1/2, setting the baseline the new ratio improves."},{"cited_title":"Online algorithms for a dual version of bin packing","cited_arxiv_id":null,"evidence_quote":"Gives the self-delimiting encoding that lets the strategy handle variable-length advice without an explicit length field."}],"review_version":1}