{"id":"da9a9a13-3c74-47f1-989c-218d180a20ee","arxiv_id":"2506.06893","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"For online job assignment with heterogeneous rewards and durations, Forward-Looking BALANCE achieves an asymptotically optimal competitive ratio of ln(RD)+3lnln(R∨D)+O(1), and no online algorithm can beat ln(RD)+Ω(1).","lead":"This paper designs an online scheduler, Forward-Looking BALANCE, that assigns arriving jobs to cloud servers while accounting for how busy each server will be in the future. The result is a worst-case performance guarantee that the authors prove is the best possible up to lower-order terms in the large-capacity regime.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Real-duration capacity-feasibility condition (Prop. 4.10 / Lemma EC.2.1) contains a sign error that makes its key logarithmic expression undefined for the paper's own parameter choices, so Theorem 3.1's general upper bound is not supported as written.","rationale":"The reader's verdict already identifies the real-duration proof in the e-companion as the weakest point, and I agree that this is where the central claim is least secure. My pass narrows that concern to a concrete, checkable defect: the capacity-feasibility constraint that determines the penalty parameter β in Theorem 3.1 contains a logarithmic term whose argument is negative for the exact parameter values the proof selects. This is not an aesthetic typo; it means the optimization program P_FLB-REAL is not well-defined at the claimed solution, and the subsequent asymptotic expansion of ln(β) is not justified by the stated constraint. The integer-duration proof in Section 4 follows a similar but separate induction and appears to avoid this particular sign issue, so I do not claim the main idea is false. The lower-bound construction in Proposition 5.1 also relies on an unexpanded 'by duplicating jobs' extension from capacity 1 to large capacities, but the dominant concern for the stated upper bound is the real-duration capacity-feasibility condition. Because the issue may be fixable with a corrected algebraic derivation, a conditional verdict is appropriate: the paper should not be accepted as providing Theorem 3.1 until the displayed constraint is re-derived and verified, ideally with a machine-checked or at least fully rewritten induction.","tokens_in":43288,"tokens_out":18134,"duration_ms":185657,"concrete_test":"Re-derive Lemma EC.2.1 case (ii) and Proposition 4.10 symbolically, and evaluate the argument of the outer logarithm with the paper's parameter choice, e.g., R=D=10, γ=3, η=(1/ln10)^2. If the argument is negative (numerically about -57.8), determine whether a correction such as replacing (1+η/(R+γη))^γ by its reciprocal, or a different parameter regime, makes the argument positive and still yields ln(RD)+3lnln(R∨D)+O(1) after optimizing γ,η. A machine-checked rewrite of the induction would settle whether the invariant itself, rather than only the displayed formula, is valid.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The main general result (Theorem 3.1, real durations) rests on the capacity-feasibility condition in Proposition 4.10, which is derived from the invariant in Lemma EC.2.1. The constraint in P_FLB-REAL contains the term -ln(1 + (γ+R/η)(1 - (1+η/(R+γη))^γ) - (R/η)(1+η/(R+γη))^γ). With the paper's own choices in the proof of Theorem 3.1, γ=⌈ln(R∨D)⌉∨2 and η=(1/ln(R∨D))^2, the quantity q=1+η/(R+γη) satisfies q^γ≈e^{1/R}>1, so whereas (γ+R/η)(1-q^γ) is negative and large in magnitude, the subtracted term (R/η)q^γ is even larger; the argument of the logarithm is negative for essentially all R,D in the regime R∨D=ω(1). For instance, R=D=10 gives γ=3, η≈0.189, and the argument is about -57.8. A logarithm of a negative number is not defined, so the first constraint in P_FLB-REAL cannot be used to select β in the way the proof describes. Moreover, the proof of Theorem 3.1 replaces this term with the different expression -ln(1+γ+(R/η)(1-(1+η/(R+γη))^γ)), omitting the final '-R/η(1+η/(R+γη))^γ' term. Because the claimed bound lnβ=ln(RD)+3lnln(R∨D)+O(1) is obtained by making this constraint bind, the real-duration upper bound is not actually derived from the stated propositions. The integer-duration theorem (Theorem 4.1) may still be sound, but the headline general theorem lacks a valid written proof unless the displayed formula in Proposition 4.10 is corrected and re-derived.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies an adversarial online resource-allocation problem in which jobs with heterogeneous rewards and durations arrive over continuous time and must be assigned immediately and irrevocably to servers with reusable capacity. The authors propose Forward-Looking BALANCE (FLB), a parametric family of greedy algorithms that use an exponential penalty function of projected future utilizations, evaluated at a chosen set of inspection times. The main claims are an asymptotic competitive ratio of ln(RD)+3lnln(R∨D)+O(1) for general real-valued durations, a stronger ln(RD)+lnln(R∨D)+O(1) bound for integer durations, matching lower bounds up to lower-order terms, and hence C*_LOG-LIMIT = 1. The analysis is based on a configuration-LP dual fitting argument and an invariant-based capacity-feasibility proof; the paper also includes special-case results for homogeneous rewards and numerical experiments.","tokens_in":43726,"tokens_out":9593,"duration_ms":91895,"significance":"If correct, the paper would settle the asymptotic logarithmic constant for this heterogeneous reusable-resource model, generalize BALANCE to heterogeneous rewards and durations, and introduce a configuration-LP + invariant framework that is likely to be useful beyond this specific problem. The integer-duration analysis (Section 4) is detailed and appears internally consistent on inspection; the lower-bound construction via Yao's lemma is a clear strength, and the numerical experiments add useful evidence. However, the proof of the headline real-duration upper bound (Theorem 3.1) is not supported as written: the displayed capacity-feasibility condition in Proposition 4.10 contains an undefined logarithm for the paper's own parameter choices, and the proof of Theorem 3.1 uses a different expression. Because this issue is load-bearing for the main theorem, the general result currently lacks a valid written proof.","major_comments":[{"comment":"The capacity-feasibility constraint in Proposition 4.10 contains the term -ln(1 + (γ+R/η)(1 - ((ηγ+R)lnβ)/(R cmin)) - (R/η)(1+η/(R+γη))^γ). With the parameter choices made in the proof of Theorem 3.1 in EC.2.3, namely γ=⌈ln(R∨D)⌉∨2 and η=(1/ln(R∨D))^2, the quantity q=1+η/(R+γη) satisfies q^γ>1 for R∨D sufficiently large; for instance R=D=10 gives γ=3, η≈0.189 and the logarithm's argument is approximately -57.8. A logarithm of a negative number is undefined, so this constraint cannot be used to select β. Furthermore, the proof of Theorem 3.1 in EC.2.3 silently bounds the same term by -ln(1+γ+(R/η)(1-(1+η/(R+γη))^γ)), a different expression that drops the negative contributions involving q^γ. Because the claimed bound lnβ=ln(RD)+3lnln(R∨D)+O(1) is obtained by making this constraint bind, Theorem 3.1's upper bound is not derived from the stated propositions as written. The formula must be corrected and the proof re-derived before the general real-duration result can be accepted.","section":"Proposition 4.10 / EC.2.3 (proof of Theorem 3.1)"},{"comment":"The proof of Proposition 4.11 opens by saying it upper bounds FLB with inspection-frequency scalar γ∈(0,1], whereas the proposition statement and the program P_FLB-REAL require γ≥2. The factor γ/(γ-1) and the bound |T_ij\\{τ}|≥γ-1 used in Step (ii) are false or undefined for γ∈(0,1], so this is not a cosmetic typo. In the same proof, the partition of T_iS is defined circularly: T^(a)_iS ≜ T_iS \\ T^(a)_iS. These two issues make the approximate dual-feasibility argument uncheckable as written and need to be fixed.","section":"EC.2.2, proof of Proposition 4.11"},{"comment":"The lower bound is essential for the corollary C*_LOG-LIMIT=1, but as written the proof works with capacity c=1 and then asserts, without proof, that duplicating jobs extends the result to large capacities. Since Definition 2.3 defines the asymptotic competitive ratio as a limsup over cmin→∞, the c=1 construction alone does not establish the stated asymptotic lower bound. The scaling argument should be spelled out, or the statement should be restricted to the unit-capacity regime.","section":"Proposition 5.1"}],"minor_comments":[{"comment":"In the explicit construction of σ, the definition σ(j,τ)≜{(jℓ,τℓ)}ℓ∈[m] should range over ℓ∈[s], where s=c_i-c_iα_i,t_j→τ; as printed the image set has cardinality m rather than s.","section":"EC.2.2, proof of Proposition 4.11"},{"comment":"In Case (ii), the notation switches between t, τ, and t_j, and the derivation of the displayed lower bound is very hard to follow. The proof should be rewritten with consistent time variables, especially since it is a load-bearing part of the real-duration argument.","section":"EC.2.1, proof of Lemma EC.2.1"},{"comment":"The program P_FLB-REAL states η>0, but Proposition 4.10 says (η,β)∈R_+^2 even though the expression R/η appears. The case η=0 should be excluded explicitly.","section":"Proposition 4.10 / P_FLB-REAL"},{"comment":"The description of the truncated normal distribution says rewards and durations are 'bounded within [0,10]', but the model normalizes rewards and durations to be at least 1. It should be clarified whether normalization is applied after truncation and how the reported R=D=10 is enforced.","section":"Section 6.2"},{"comment":"The footnote after the lemma statement imposes a condition on β, η, cmin that is later used in the proof; placing this condition before the lemma statement and integrating it into the lemma's hypotheses would improve readability.","section":"Section 4.1, Lemma 4.4"}],"recommendation":"major_revision","confidential_remarks":"The integer-duration analysis (Section 4) is a solid contribution and the overall approach is interesting. However, the proof of the headline Theorem 3.1 for real durations is not valid as written: the capacity-feasibility condition in Proposition 4.10 is undefined for the paper's own parameter choices, and the proof of Theorem 3.1 uses a different expression. The errors in Proposition 4.10 and the proof of Proposition 4.11 look local and fixable, so I recommend major revision rather than rejection. The authors should also supply the promised large-capacity extension of the lower bound in Proposition 5.1, which is needed for the asymptotic statement."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThis paper deserves a serious look. It introduces Forward-Looking BALANCE, a natural extension of BALANCE that uses projected future capacities at periodic inspection times, and proves an asymptotically optimal competitive ratio of ln(RD)+3lnln(R∨D)+O(1) for online job assignment with heterogeneous rewards and durations. The configuration-LP dual-fitting analysis is genuinely new for this family: prior BALANCE/AdWords/reusable-resource work does not get the logarithmic constant right, and the lower bound via Yao shows no algorithm can beat the ln(RD) constant. So the paper settles C*_LOG-LIMIT = 1. That is a real result.\n\nThe integer-duration proof (Theorem 4.1) is careful and, as far as I checked, correct. The invariant-based feasibility argument and the charging scheme are non-trivial and hang together. The real-duration proof is relegated to the e-companion, and that is where the warts are: the proof of Prop 4.11 says γ∈(0,1] when the proposition requires γ≥2, and the definition of T_iS^(a) is circular. Both are fixable typos, not conceptual gaps.\n\nI also checked the stress-test claim of a sign error in Prop 4.10. It does not hold up. The note misreads the constraint: the logarithm's argument in the c_min→∞ limit is 1+γ+R/η − (R/η)(1+η/(R+γη))^γ, which is exactly what the proof of Theorem 3.1 uses. The stress-test's version incorrectly treats the (1−q^γ) factor as multiplying the entire (γ+R/η) term and then subtracts (R/η)q^γ again. With the actual expression, the argument is positive for the paper's parameter choices, not negative. So the main theorem does not have the load-bearing flaw the note claims.\n\nRemaining soft spots are minor: the e-companion typos, the lack of code/data for the numerical experiments, and the fact that the algorithm requires prior knowledge of R and D (which Remark 2.2 and EC.5 show is necessary). The finite-capacity regime gets messier, but the paper is explicit that the headline is asymptotic.\n\nThis is for anyone working on online matching, reusable resources, or primal-dual methods. I would send it to a serious referee, conditionally accepting after the e-companion is cleaned up and the experiments are made reproducible.","headline":"A genuinely new online allocation algorithm with a solid integer-duration proof; the real-duration theorem needs e-companion cleanup but the stress-test's sign-error claim misreads the formula.","tokens_in":44293,"tokens_out":6839,"would_cite":true,"duration_ms":56087,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W27","90B35","90C05","90C27"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper establishes that online job assignment has asymptotic competitive ratio $\\ln(RD)$, with Forward-Looking BALANCE matching it and a lower bound showing no online algorithm can do better.","keywords":["online job assignment","reusable resources","competitive analysis","primal-dual method","configuration LP","forward-looking BALANCE","cloud computing","large-capacity regime"],"falsifier":"Take the paper's adversarial family from Section 5: a single server, jobs numbered by $j\\in[M]$ arriving at $j/M$ with reward $R^{j/M}$ and duration $\\lfloor D^{j/M}\\rfloor$, with the adversary choosing the stopping time $k$ after seeing the online policy. Compute the worst-case ratio of FLB with the Section EC.2.3 parameters as $M$ and $c_{\\min}$ grow; if it exceeds $\\ln(RD)+3\\ln\\ln(R\\vee D)+O(1)$, the upper bound is false. Similarly, if any online policy achieves a ratio below $\\ln(RD)+\\Omega(1)$ on this family, the lower bound is false.","tokens_in":43063,"feed_emoji":"☁️","tokens_out":10157,"duration_ms":96295,"temperature":0.7,"pith_summary":"Online job assignment asks a platform to place jobs on servers as they arrive, with each job occupying a server for its duration and earning reward at completion. The paper claims that in the large-capacity regime the best possible competitive ratio against an omniscient offline benchmark has leading term $\\ln(RD)$, where $R$ and $D$ are the ratios of maximum to minimum rewards and durations. It proves the upper bound by exhibiting a family of algorithms, Forward-Looking BALANCE (FLB), that assigns each job to the server maximizing an adjusted reward: the job's reward minus penalties for projected capacity use at a chosen set of current and future inspection times. It proves the lower bound by constructing single-server instances on which every online algorithm loses a $\\ln(RD)+\\Omega(1)$ factor. Together these give $C^*_{\\mathrm{LOG\\text{-}LIMIT}}=1$: no algorithm can asymptotically improve the constant in front of $\\ln(RD)$.","feed_headline":"Forward-looking BALANCE hits the optimal ln(RD) ratio","feed_subtitle":"With large server capacity, the algorithm achieves the best possible logarithmic dependence on reward/duration ranges.","key_machinery":"The load-bearing object is the Forward-Looking BALANCE score: for a job-server pair, $r_{ij}d_{ij} - \\sum_{\\tau \\in \\mathcal{T}_{ij}(\\gamma)} \\Psi(\\alpha_{i,t_j\\to\\tau})$, where $\\alpha_{i,t_j\\to\\tau}$ is the projected fraction of server $i$'s capacity that remains free at future time $\\tau$, $\\mathcal{T}_{ij}(\\gamma)$ samples current and future inspection times at frequency $\\gamma$, and $\\Psi(x)=\\eta(\\beta^{1-x}-1)$ is an exponential penalty. The algorithm assigns the arriving job to the compatible server with the largest positive adjusted reward. The analysis couples this score with a configuration LP whose primal variables assign whole feasible schedules of non-overlapping jobs to units of capacity; the dual solution is built from FLB's decisions, and a charging argument verifies dual feasibility. A separate inductive invariant bounds how much the projected available capacity can drop over any duration window, which is what guarantees capacity feasibility without forcing an overly pessimistic penalty at zero capacity.","core_discovery":"The paper's central discovery is that the online job assignment problem has a sharp asymptotic logarithmic constant: the best competitive ratio any online algorithm can guarantee is $\\ln(RD)+o(\\ln(RD))$, and FLB attains $\\ln(RD)+3\\ln\\ln(R\\vee D)+O(1)$. The algorithm is a forward-looking generalization of BALANCE: instead of using only the current free capacity of each server, it subtracts from the reward the sum of an exponential penalty evaluated on the projected free capacity at inspection times inside the job's holding interval, so a server that will be busy soon looks less attractive. Feasibility is not forced by a conservative penalty at zero capacity; it follows from an invariant maintained by the algorithm. The matching lower bound holds even for fractional or randomized algorithms, via a single-server construction with exponentially increasing rewards and durations and an adversarial stopping time.","pith_inferences":["If the same score were used with a soft-capacity cost rather than a hard rejection rule, the proof's invariant suggests the $\\ln(RD)$ leading constant would survive as long as the penalty reflects projected occupancy; a platform that can momentarily overload a server could trade a bounded violation for higher reward.","The paper's $(R,D)$-agnostic lower bounds imply that even a crude estimate of reward and duration ranges, updated online, could remove the exponential gap; designing such an estimator and proving a regret-style competitive ratio is a natural next step.","Because the integer-duration analysis beats the real-duration bound by a $\\ln\\ln(R\\vee D)$ factor, forcing durations onto a discrete grid may be a cheap practical lever: systems that charge in fixed time increments inherit the stronger guarantee.","A finite-capacity version of the parameter optimization is sketched in the paper; automating that choice per capacity level could turn FLB into a deployable policy for small clouds where $c_{\\min}$ is not large."],"forward_implications":["For a cloud platform that knows $R$ and $D$, running FLB with the paper's parameter choices yields, for large capacity, total reward at least $(\\ln(RD)+3\\ln\\ln(R\\vee D)+O(1))^{-1}$ times the offline optimum; the leading dependence on problem heterogeneity is a single logarithm of the product $RD$.","No online algorithm, including randomized and fractional ones, can achieve an asymptotic logarithmic constant below 1, so the $\\ln(RD)$ factor is an intrinsic price of immediacy and uncertainty, not an artifact of FLB.","With fixed rewards ($R=1$), the bound tightens to $\\ln(D)+O(1)$, and with integer durations the second-order term improves to $\\ln\\ln(R\\vee D)$, so the practical cost of duration heterogeneity is only logarithmic.","The configuration-LP dual-fitting proof and the invariant-based feasibility argument are not tied to this specific primitive family; they provide a template for other interval-occupancy allocation problems."],"supporting_citations":[{"why":"Introduces BALANCE and the large-inventory competitive analysis that FLB generalizes.","marker":"Kalyanasundaram and Pruhs (2000)"},{"why":"Defines the AdWords/BALANCE benchmark for heterogeneous rewards that the $\\ln(RD)$ bound extends to durations.","marker":"Mehta et al. (2007)"},{"why":"Establishes the $e/(e-1)$ baseline for reusable identical jobs, recovered by FLB at $R=D=1$.","marker":"Feng et al. (2019)"},{"why":"Gives the $O(\\log R)$ protection-level benchmark for non-reusable heterogeneous rewards, motivating the logarithmic dependence.","marker":"Ball and Queyranne (2009)"},{"why":"Studies the same model with a single resource and monotonicity assumptions, achieving $\\phi\\ln(RD)$; FLB removes those assumptions and sets the constant to 1.","marker":"Huo and Cheung (2022)"},{"why":"Provides a generalized BALANCE for non-reusable resources whose instance-dependent ratios FLB is compared against.","marker":"Ma and Simchi-Levi (2020)"},{"why":"Yao's lemma converts the randomized lower bound to a deterministic distributional argument.","marker":"Yao (1977)"},{"why":"Proves the $e/(e-1)$ optimal ratio for reusable resources with identical fees and durations, another baseline FLB recovers.","marker":"Goyal et al. (2025)"}],"fun_headline_variants":["Forward-Looking BALANCE achieves optimal ln(RD) ratio","FLB algorithm: online job assignment hits ln(RD) limit","Optimal competitive ratio ln(RD) for online job scheduling","Tight bound: FLB matches ln(RD) for online job allocation"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The guarantee assumes the algorithm knows the reward range $R$ and the duration range $D$ before choosing its penalty parameters, and it is stated in the limit as server capacity grows; the paper itself shows that an algorithm without $(R,D)$ knowledge loses the logarithmic bound.","fun_headline_variants_meta":{"raw":{"variants":["Forward-Looking BALANCE achieves optimal ln(RD) ratio","FLB algorithm: online job assignment hits ln(RD) limit","Optimal competitive ratio ln(RD) for online job scheduling","Tight bound: FLB matches ln(RD) for online job allocation"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000854,"raw_usage":{"total_tokens":3759,"prompt_tokens":1042,"completion_tokens":2717,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":658,"completion_tokens_details":{"reasoning_tokens":2642}},"tokens_in":658,"tokens_out":2717,"duration_ms":23119,"temperature":1.0,"reasoning_tokens":2642,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T05:48:19.661154+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take the paper's adversarial family from Section 5: a single server, jobs numbered by $j\\in[M]$ arriving at $j/M$ with reward $R^{j/M}$ and duration $\\lfloor D^{j/M}\\rfloor$, with the adversary choosing the stopping time $k$ after seeing the online policy. Compute the worst-case ratio of FLB with the Section EC.2.3 parameters as $M$ and $c_{\\min}$ grow; if it exceeds $\\ln(RD)+3\\ln\\ln(R\\vee D)+O(1)$, the upper bound is false. Similarly, if any online policy achieves a ratio below $\\ln(RD)+\\Omega(1)$ on this family, the lower bound is false.","supporting_citations":[{"cited_title":"An optimal deterministic algorithm for online b-matching","cited_arxiv_id":null,"evidence_quote":"Introduces BALANCE and the large-inventory competitive analysis that FLB generalizes."},{"cited_title":"Vazirani, and Vijay V","cited_arxiv_id":null,"evidence_quote":"Defines the AdWords/BALANCE benchmark for heterogeneous rewards that the $\\ln(RD)$ bound extends to durations."},{"cited_title":"Linear programming based online policies for real-time assortment of reusable resources","cited_arxiv_id":null,"evidence_quote":"Establishes the $e/(e-1)$ baseline for reusable identical jobs, recovered by FLB at $R=D=1$."},{"cited_title":"Online reusable resource allocations with multi-class arrivals","cited_arxiv_id":null,"evidence_quote":"Studies the same model with a single resource and monotonicity assumptions, achieving $\\phi\\ln(RD)$; FLB removes those assumptions and sets the constant to 1."},{"cited_title":"Probabilistic computations: Toward a unified measure of complexity (extended abstract)","cited_arxiv_id":null,"evidence_quote":"Yao's lemma converts the randomized lower bound to a deterministic distributional argument."},{"cited_title":"Asymptotically optimal competitive ratio for online allocation of reusable resources","cited_arxiv_id":null,"evidence_quote":"Proves the $e/(e-1)$ optimal ratio for reusable resources with identical fees and durations, another baseline FLB recovers."}],"review_version":1}