{"id":"1268a494-e058-4717-a3bd-c17ad51bf248","arxiv_id":"2509.01086","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"A central lemma used for all lower bounds in this scheduling paper, that chains with different skinny job lengths cannot overlap, is contradicted by a simple parallel schedule, so the claimed hardness and online lower bounds are not established.","lead":"This paper claims almost tight hardness of approximation and matching online bounds for precedence-constrained resource scheduling, using a new 'chains' construction. The construction's key incompatibility lemma appears false: chains of different types can be scheduled in parallel, which breaks the lower-bound proofs.","discovery_kind":"unclear","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.3's t_max hardness is unsupported: the reduction keeps the number of LTS machines ρ constant, so t_max≤2^ρ is constant, and no o((log t_max)^α) bound for growing t_max follows.","rationale":"The reader's primary attack on Property 2.3 does not land. Under the paper's intended semantics, fat jobs act as zero-length but resource-exclusive barriers, so skinny jobs from different chains cannot be freely interleaved. The proof of Property 2.3 via Property 2.2 and Lemma A.1 is coherent: any feasible schedule can be batched, each chain contributes at most one skinny job per batch, and the credit argument gives makespan Ω(Σ 2^{m_t}). The specific C(3,1)+C(3,2) example in the reader's verdict ignores that a chain with four length-2 skinny jobs needs four barrier-separated batches; the optimum is 12, not 8, and 12 is indeed Ω(16). Thus the chains toolbox itself is not the fatal flaw. However, the reader's secondary observation about t_max is correct and load-bearing. Theorem 3.3 claims a P=NP lower bound of o((log t_max)^α) for growing t_max, but the only LTS hardness invoked has ρ constant, making t_max constant in the reduced instances. The reduction therefore cannot establish an asymptotic in t_max, and scaling s does not bridge the gap because the LTS hardness threshold is then a constant while o(s^α) permits unbounded ratios. The central 'almost tight' t_max hardness claim is unsupported, so the reader's REJECT verdict stands, albeit for a different reason than its main argument.","tokens_in":42505,"tokens_out":32719,"duration_ms":419896,"concrete_test":"Set ρ=2 in the §3.3 construction and compute t_max of rsΠ: it is at most 2^ρ = 4, so log t_max is a constant. To settle whether the o((log t_max)^α) claim can be rescued, try modifying the construction to C(f(i)+s, i+s) while keeping ρ fixed. Track the LTS approximation guarantee produced by an o((log t_max)^α) algorithm: with t_max = 2^{ρ+s}, the guarantee is g(s) with g(s)=o(s^α). Since g(s) may be unbounded (e.g., g(s)=log s), it is not necessarily below the constant LTS threshold ρ^α/4, so no contradiction is obtained. This verifies that the t_max asymptotics cannot be derived from the constant-ρ reduction.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing gap is in the proof of Theorem 3.3, not in the chains toolbox. The reduction in §3.3 keeps the number of LTS machines ρ constant (Theorem 3.2). In the constructed scheduling instance, every skinny job has length 2^i for i ≤ ρ, so t_max ≤ 2^ρ = O(1), independent of n. The proof then uses log t_max = ρ, so the assumed o((log t_max)^α) factor is o(ρ^α) with ρ fixed, i.e., O(1) — this can contradict only the constant-factor hardness of LTS, yielding Corollary 3.15, not an o((log t_max)^α) lower bound for growing t_max. Scaling skinny lengths by an extra 2^s does not repair the argument: with ρ fixed, the LTS hardness threshold ρ^α/4 is a constant, while an o((log t_max)^α) = o(s^α) algorithm may have ratio growing like log s and never fall below that constant. Letting ρ grow makes each chain's tuple count 2^{ρ-i} ℓ(m_i) exponential in ρ, so the reduction ceases to be polynomial. Thus Theorem 3.3 as stated is unsupported; the honest deliverable from this reduction is constant-factor hardness.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies precedence-constrained resource scheduling with a resource budget, in both offline and online settings. It claims (i) for some constant α>0, no polynomial-time o((log t_max)^α)-factor approximation exists unless P=NP, and similarly no o((log n)^α)-factor approximation unless NP⊂DTIME(2^{polylog n}); (ii) an o(log t_max)-approximation for the scheduling problem would imply an o(|Σ|)-approximation for Shortest Common Supersequence (SCS); (iii) no randomized online algorithm is o(log n)-competitive or o(log t_max)-competitive; and (iv) a deterministic online algorithm with competitive ratio O(d + min{log n, log t_max}). The proofs are built around a new gadget called chains, with an asserted 'incompatibility' property stating that independent chains whose skinny jobs have different powers-of-two lengths cannot be parallelized and force makespan Ω(sum 2^{m_i}).","tokens_in":42773,"tokens_out":14708,"duration_ms":196748,"significance":"The claimed results, if valid, would be significant: they would give the first non-constant hardness of approximation for the offline problem with a fixed number of resource types, a new conditional connection to SCS, and tight bounds for the online problem. The chains toolbox is a natural idea, and the deterministic online algorithm in Section 6 is a useful contribution if its analysis is sound. However, the central incompatibility property is false, and the main t_max hardness theorem is not supported by the reduction as written. These are load-bearing defects in the two headline results of the paper, not presentation issues.","major_comments":[{"comment":"Property 2.3 is false as stated. Take two chains C(3,1) and C(3,2). Each chain has total length 8, and its fat jobs have length 0. Because skinny jobs have resource requirement <1/n, the skinny jobs from the two chains can run concurrently; the zero-length fat jobs do not occupy any time. Scheduling the two chains in parallel gives makespan 8, contradicting the claimed Ω(2^3+2^3)=Ω(16). This is not a technicality: the zero-length fat jobs do not act as time barriers. The error is load-bearing in Lemma 5.4, which asserts E[T_Dj]≥(m/4)·2^m because the m/4 completed chains of different types are assumed to require sequential execution. Since chains of different types can in fact run in parallel, the argument yields only a 2^m bound per gadget, and the Ω(log n) and Ω(log t_max) lower bounds of Theorem 5.1 collapse.","section":"§2.1, Property 2.3 (and Appendix A)"},{"comment":"The reduction from LTS fixes the number of machines ρ to a constant, as stated immediately before Remark 3.13. Consequently every constructed scheduling instance has t_max ≤ 2^ρ = O(1), independent of n. An o((log t_max)^α)-approximation hypothesis is then an o(1)-factor condition on instances with constant t_max; it cannot be used to contradict the constant-factor LTS hardness of Theorem 3.12. Scaling all skinny lengths by an additional 2^s does not repair the argument: with ρ fixed, ρ^α/4 is a constant while an o((log t_max)^α)=o(s^α) algorithm may have ratio growing like log s and never fall below that constant. Letting ρ grow makes each chain contain 2^{ρ-i}ℓ(m_i) tuples, exponential in ρ, so the reduction ceases to be polynomial. Thus Theorem 3.3 as stated is unsupported; the honest deliverable of this reduction is the constant-factor hardness of Corollary 3.15.","section":"§3.3, proof of Theorem 3.3"},{"comment":"The online lower-bound construction also fails for a more concrete reason. In each gadget D_i, all m chains have total length exactly 2^m, irrespective of their skinny-job length. Even if the algorithm does not know the random blocking chain, it can run all m chains of D_i in parallel as soon as they are revealed; the blocking chain then completes in time 2^m along with every other chain in the gadget. Hence the expected time between end(i-1) and end(i) is 2^m, not Ω(m·2^m). Lemma 5.3 is consistent with this, since it gives an expectation of at least m/4 completed chains, but Lemma 5.4's step from m/4 completed chains to m/4·2^m time is precisely the false incompatibility assumption. The claimed Ω(m) competitive ratio therefore does not follow; the construction gives only an Ω(1) lower bound.","section":"§5.1, Lemmas 5.3–5.5"}],"minor_comments":[{"comment":"The paper repeatedly motivates chains by asserting that 'if the chains are of different types, the makespan is Ω(p·x)', but this statement is used in the technical overview before being proved. After Property 2.3 is shown false, the overview should be revised.","section":"§1.1 and §2"},{"comment":"The 'without loss of generality' reduction for zero-time jobs only converts zero-length jobs to jobs of length 1; it does not restore the claimed incompatibility of different chain types. This should be stated explicitly, since the whole paper relies on zero-length fat jobs.","section":"§1, zero-time jobs"},{"comment":"The proof of Lemma 3.5 is incomplete: when moving a job v to a later partition to restore the deleted precedence u≺v, the proof does not check the outgoing edges of v. The lemma may be true, but the argument should handle successors of v or be rewritten.","section":"§3.2.1, Lemma 3.5"},{"comment":"There are many typographical issues, including misplaced braces, inconsistent notation (OPT vs opt, D_j vs T_Dj), and undefined symbols such as 'ℓ' in the statement of Theorem 5.1. These should be cleaned up in any revision.","section":"Throughout"}],"recommendation":"reject","confidential_remarks":"The paper is a journal version of a SPAA 2025 paper. The false incompatibility property is not a minor gap: it invalidates the online lower bound, one of the paper's headline contributions. The t_max hardness theorem is also not supported because the reduction keeps the number of LTS machines constant. The SCS reduction may be salvageable via Lemma 2.4 independently of Property 2.3, but the paper's main claims as stated are not. I recommend rejection, though the deterministic online algorithm and the conflict-free LTS transformations contain ideas that could be part of a future, carefully corrected version."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper's central technical tool, the chains incompatibility property, does not hold. Property 2.3 claims that p independent chains with pairwise different skinny job lengths have optimum makespan Omega(sum 2^{m_i}). That is false: two chains C(3,1) and C(3,2) can be scheduled in makespan 12, not Omega(16). The reader's specific counterexample (makespan 8) is not accurate because the zero-length fat jobs still force some serialization, but the property fails anyway. A simpler witness: Property 2.2, which the proof of Property 2.3 relies on, is itself false. You cannot generally turn a parallel schedule into a non-overlapping one without increasing makespan.\n\nThe t_max claim in Theorem 3.3 is also unsupported. The reduction keeps the number of LTS machines rho constant, so t_max is at most 2^rho, i.e., O(1). Thus log t_max is constant, and an o((log t_max)^alpha) lower bound is vacuous. The honest conclusion is constant-factor hardness, which the authors already state as Corollary 3.15.\n\nWhat does the paper do well? The deterministic online algorithm in Section 6 is a constructive, independent result and appears to be a real contribution. The paper is clearly written and the ambition of connecting resource scheduling to SCS is interesting. But the SCS reduction and the online lower bound both rely on the false chains property, so those results do not stand.\n\nMy bottom line: the paper is not publishable in anything close to its current form. The negative results are load-bearing and they break. The online algorithm should be separated and perhaps submitted independently. If the authors can repair the chains lemma or restrict their claims to the positive algorithm, there is something worth revisiting. As is, I would desk reject: a serious referee would quickly hit the same counterexample.","headline":"The chains toolbox is broken: Property 2.3 is false, the t_max hardness claim is vacuous, and the online lower bound and reductions collapse; only the positive online algorithm is salvageable.","tokens_in":646,"tokens_out":1021,"would_cite":false,"duration_ms":181761,"reading_group":"no","serious_thinker":"yes","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68W25","68W27","90B35"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that the precedence-constrained resource scheduling problem—jobs that draw on a shared resource while respecting dependency order—has no polynomial-time o((log t_max)^alpha)-factor approximation unless P=NP, no o((log n)^a","keywords":["precedence-constrained resource scheduling","hardness of approximation","online scheduling","competitive ratio","shortest common supersequence","chain gadget","makespan","loading-time scheduling"],"falsifier":"Run two independent chains C(3,1) and C(3,2) in a one-resource instance with budget 1, skinny jobs requiring less than 1/n of the budget, and fat jobs of length 0. If both chains finish in makespan 8 by running all skinny jobs concurrently, Property 2.3's Omega(2^3 + 2^3) bound is refuted, which removes the premise behind the LTS reduction, the SCS reduction, and the Omega(log n) online lower bound.","tokens_in":42296,"feed_emoji":"⏱️","tokens_out":7499,"duration_ms":87245,"temperature":0.7,"pith_summary":"This paper takes on a fifty-year-old question: can precedence-constrained resource scheduling—jobs that consume units of a shared resource while respecting dependency order—be approximated in polynomial time within a constant factor? The answer it argues is no: for some constant alpha>0, any o((log t_max)^alpha)-factor approximation is impossible unless P=NP, and any o((log n)^alpha)-factor approximation would put NP in subexponential time. It further shows that an o(log t_max)-approximation would improve the approximation ratio for shortest common super-sequence below the alphabet-size barrier, a long-standing open problem. In the online setting, it proves that no randomized algorithm can beat Omega(log n) or Omega(log t_max) competitive ratio, and it supplies a deterministic algorithm with matching O(min(log n, log t_max))-competitive ratio, plus a term for the number of resource types. The vehicle for all these results is a gadget called a chain, whose defining property is meant to make chains with different skinny-job lengths mutually incompatible.","feed_headline":"Resource scheduling: no near-log approximation unless P=NP","feed_subtitle":"An o(log t_max) offline approximation would also crack the shortest-common-supersequence barrier; online bounds are tight.","key_machinery":"The chain gadget: a skinny job of length 2^i (resource use below 1/n, so many can run in parallel) followed by a zero-length fat job consuming the full budget, repeated to make total length 2^m; chains of the same type pack in parallel, while chains of different types are asserted to be incompatible, forcing additive makespan. This incompatibility property is the load-bearing mechanism: it converts scheduling instances into combinatorial objects that can encode LTS partitions and SCS supersequences, and it makes every online algorithm guess which chain blocks the next gadget.","core_discovery":"The paper's central claim is that the makespan of precedence-constrained resource scheduling is governed, in the worst case, by the sum of incomparable 'chain' lengths rather than by their maximum. A chain C(m,i) is built from repeated tuples, each a skinny job of processing time 2^i followed by a fat job of length 0 that claims the entire resource; the chain has total length 2^m. The paper asserts that if several chains have pairwise different skinny-job lengths, their fat jobs act as barriers so that the optimum makespan is Omega(2^{m_1}+...+2^{m_p}), even though chains sharing a skinny length pack together at cost max 2^{m_j}. This incompatibility is then used to simulate loading-time sch","pith_inferences":["Our inference: the lower-bound proofs require the zero-length fat jobs to act as real barriers between skinny jobs of different lengths; if skinny jobs from different chains are allowed to run concurrently, the claimed Omega(sum of chain lengths) property would fail, and with it the LTS reduction, the SCS reduction, and the online adversary. The paper does not address this edge case.","Our inference: a direct test of the central gadget is to simulate two chains C(3,1) and C(3,2) with resource budget 1 and skinny requirement below 1/n: Property 2.3 predicts makespan Omega(16), while a schedule that runs all skinny jobs concurrently would finish both in 8.","Our inference: if the chain gadget were repaired by giving fat jobs positive length, the reduction sizes and parameter mapping (t_max = 2^rho, log n = Theta(log t_max)) would need rechecking, since positive-length fat jobs add another multiplicative factor to chain length.","Our inference: the SCS connection is one-directional; the paper shows scheduling hardness implies SCS hardness, but not that SCS approximation would improve scheduling, and establishing the converse would require a different gadget."],"forward_implications":["If P != NP, the offline problem admits no polynomial-time o((log t_max)^alpha)-approximation, so the known O(log n) upper bound is almost matched in the worst case.","Any polynomial-time o((log t_max)^alpha)-approximation algorithm would imply P = NP; any o((log n)^alpha)-approximation would imply NP is contained in DTIME(2^{polylog n}).","An o(log t_max)-approximation for scheduling would yield an o(|Sigma|)-approximation for shortest common super-sequence, breaking the alphabet-size barrier that has stood for decades.","No randomized online algorithm has competitive ratio o(log n) or o(log t_max), and the paper's deterministic algorithm achieves O(d + min(log n, log t_max)), matching up to constants.","With d >= 3 resource types, no online algorithm, randomized or not, can achieve a competitive ratio better than (d-1)/2."],"supporting_citations":[{"why":"Supplies the loading-time-scheduling (LTS) hardness-of-approximation result that the offline lower bounds reduce from.","marker":"[12]"},{"why":"Defines the precedence-constrained resource scheduling problem and gives the classical bound that motivates the constant-factor question.","marker":"[34]"},{"why":"Gives the |Sigma|-approximation for shortest common super-sequence that Theorem 4.1's conditional improvement would beat.","marker":"[45]"},{"why":"Establishes that shortest common super-sequence is NP-hard even on a binary alphabet, background for the SCS connection.","marker":"[61]"},{"why":"Provides the O(log n)-approximation upper bound for offline scheduling that the paper's hardness results almost match.","marker":"[5]"},{"why":"Supplies the minimax principle used to convert deterministic online lower bounds on a randomized instance into lower bounds for randomized algorithms.","marker":"[54]"},{"why":"Gives the fixed-alphabet SCS inapproximability used in the proof of the o((log n)^alpha) hardness of Theorem 3.16.","marker":"[57]"},{"why":"Provides the classic list-scheduling background and the baseline greedy online behavior that the paper later shows can be Omega(n)-competitive.","marker":"[36]"}],"fun_headline_variants":["Resource scheduling: no near-log approx unless P=NP","Matching online bounds for resource-constrained scheduling","Offline hardness, online optimality for resource scheduling","Scheduling with resources: o(log) hardness and online tightness"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The whole lower-bound structure assumes that chains with different skinny-job lengths cannot overlap in time, so p distinct chains cost Omega(sum of their lengths); but the paper defines skinny jobs to use less than 1/n of the resource each and fat jobs to have length 0, so skinny jobs from different chains can actually run concurrently and zero-length fat jobs create no barrier.","fun_headline_variants_meta":{"raw":{"variants":["Resource scheduling: no near-log approx unless P=NP","Matching online bounds for resource-constrained scheduling","Offline hardness, online optimality for resource scheduling","Scheduling with resources: o(log) hardness and online tightness"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000427,"raw_usage":{"total_tokens":2093,"prompt_tokens":885,"completion_tokens":1208,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":629,"completion_tokens_details":{"reasoning_tokens":1142}},"tokens_in":629,"tokens_out":1208,"duration_ms":14151,"temperature":1.0,"reasoning_tokens":1142,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T12:56:40.006989+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run two independent chains C(3,1) and C(3,2) in a one-resource instance with budget 1, skinny jobs requiring less than 1/n of the budget, and fat jobs of length 0. If both chains finish in makespan 8 by running all skinny jobs concurrently, Property 2.3's Omega(2^3 + 2^3) bound is refuted, which removes the premise behind the LTS reduction, the SCS reduction, and the Omega(log n) online lower bound.","supporting_citations":[{"cited_title":"Bhatia, S","cited_arxiv_id":null,"evidence_quote":"Supplies the loading-time-scheduling (LTS) hardness-of-approximation result that the offline lower bounds reduce from."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the precedence-constrained resource scheduling problem and gives the classical bound that motivates the constant-factor question."},{"cited_title":"On the approximation of shortest common supersequences and longest common subsequences","cited_arxiv_id":null,"evidence_quote":"Gives the |Sigma|-approximation for shortest common super-sequence that Theorem 4.1's conditional improvement would beat."},{"cited_title":"The shortest common supersequence problem over binary alphabet is np-complete","cited_arxiv_id":null,"evidence_quote":"Establishes that shortest common super-sequence is NP-hard even on a binary alphabet, background for the SCS connection."},{"cited_title":"Strip packing with precedence constraints and strip packing with release times","cited_arxiv_id":null,"evidence_quote":"Provides the O(log n)-approximation upper bound for offline scheduling that the paper's hardness results almost match."},{"cited_title":"Randomized algorithms","cited_arxiv_id":null,"evidence_quote":"Supplies the minimax principle used to convert deterministic online lower bounds on a randomized instance into lower bounds for randomized algorithms."},{"cited_title":"Duella P","cited_arxiv_id":null,"evidence_quote":"Gives the fixed-alphabet SCS inapproximability used in the proof of the o((log n)^alpha) hardness of Theorem 3.16."},{"cited_title":"Bounds for certain multiprocessing anomalies","cited_arxiv_id":null,"evidence_quote":"Provides the classic list-scheduling background and the baseline greedy online behavior that the paper later shows can be Omega(n)-competitive."}],"review_version":1}