{"id":"83c79028-f48b-4c85-a2ea-9d481859eb57","arxiv_id":"2506.06138","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":1,"one_line_summary":"EDHR is a tunable generalization of Dembo-Hammer reduction that bounds how many near-break items an optimal 0-1 knapsack solution can omit or include.","lead":"This paper extends a classical knapsack reduction rule so that, instead of fixing every near-break item, it allows a tunable number of exceptions and splits the problem into many smaller instances. The general-interest angle is a possible speedup for exact solvers like CPLEX, though the theoretical case is not made cleanly.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Missing 'Lemma 1' is the sole support for the O(n^{2i}) exact-resolution claim; the paper concedes the residual subproblem is NP-hard, so the claimed runtime is unsupported.","rationale":"I read the paper's main theoretical contribution as the claim that EDHR not only reduces the instance to n^{2i} sub-instances but does so in O(n^{2i}) time, i.e., the decisions on N_{i,1} and N_{i,4} can be exactly resolved in that bound. The enumeration bound |Y_i| ≤ n^{2i} follows from Theorems 2 and 3, assuming those proofs are correct. I examined the proofs: Theorem 2's proof has some questionable steps (e.g., Claim 1 appears to select q by minimum density rather than minimum p/(w+r/i), and inequality (11) omits the X'-selected items in N_{i,4}∪N_{i,5}), but the theorem itself can likely be established by a direct exchange argument, so I did not make the proof defects the load-bearing objection. The truly load-bearing weakness is the unstated Lemma 1. The paper uses it as the only justification for turning a reduction into a polynomial-time exact algorithm, and the authors' own final remark that the residual subproblem remains NP-hard makes the existence of such a lemma impossible in general. The reader's weakest_assumption identifies exactly this gap, so I agree with the rejection.","tokens_in":12185,"tokens_out":23234,"duration_ms":201517,"concrete_test":"Re-derive the final §3 sentence ('Based on Lemma 1... exactly solved in time complexity O(n^{2i})') using only the stated theorems. Since no Lemma 1 appears in the manuscript, test the two possible reconstructions: (i) Lemma 1 asserts the residual sub-instance on N_{i,2}∪N_{i,3}∪N_{i,5} is polynomially solvable—this contradicts the paper's own statement that this subproblem 'is still a NP-hard problem'; (ii) Lemma 1 merely counts the N^*_{i,1}/N^*_{i,4} subsets—this does not bound the cost of solving each residual sub-instance. If neither reconstruction makes the sentence true, the O(n^{2i}) claim is unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing step is in §3 (after the definition of Y_i): 'Based on Lemma 1, although the 0-1 KP is NP-hard, the decision variables of two subsets N_{i,1} and N_{i,4} can be exactly solved in time complexity O(n^{2i}).' This sentence is the only bridge from the combinatorial bound |Y_i| ≤ n^{2i} to the claimed O(n^{2i}) runtime. Yet Lemma 1 never appears in the paper; it is neither stated, proved, nor cited. The preceding argument shows only that any optimal solution Y lies in Y_i, where each Y_i is built from an optimal solution of a residual sub-instance on N_{i,2}∪N_{i,3}∪N_{i,5} with capacity reduced by the chosen N^*_{i,1}. To actually produce Y, each of the ≤ n^{2i} residual sub-instances must be solved exactly. Those residual sub-instances are unrestricted 0-1 knapsack problems: in the IC instances (Table 4), N_{i,1} and N_{i,4} are empty and the residual sub-instance is the entire original instance. The paper itself concedes (§3 after Theorem 4) that 'the subproblem consist by N_{i,2}, N_{i,3} and N_{i,5} is still a NP-hard problem.' Hence no Lemma 1 can supply a polynomial-time oracle for all residual sub-instances; the O(n^{2i}) claim collapses to 'there are at most n^{2i} NP-hard subproblems.' This is the central unsupported premise of the paper.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes an extension of Dembo-Hammer's reduction algorithm (EDHR) for the 0-1 knapsack problem. The algorithm partitions the item set N into five subsets N_{i,1},...,N_{i,5} depending on a user-chosen positive integer i and on the break item's profit density. The main structural claims are Theorem 2 (N_{i,1} contains at most i-1 items not in any optimal solution) and Theorem 3 (N_{i,4} contains at most i-1 items in any optimal solution). From these the paper concludes that the optimal solution belongs to a family Y_i of at most n^{2i} candidate solutions, and asserts that, based on a 'Lemma 1', the decisions on N_{i,1} and N_{i,4} can be exactly solved in time O(n^{2i}). The paper reports computational experiments on five randomly generated instance families showing that EDHR with i=2 reduces CPLEX's internal 'ticks' relative to solving the original instance directly, with zero improvement on inverse-strongly-correlated instances.","tokens_in":12557,"tokens_out":13751,"duration_ms":123367,"significance":"If the main complexity claim were correct, the paper would provide a substantial theoretical advance: a reduction of 0-1 KP to a polynomial number of subinstances along with a polynomial-time exact resolution of the decision variables in the 'exceptional' sets. The underlying idea of bounding the number of deviations from the break solution is natural, and the experimental study is transparent in reporting a baseline and in admitting cases (IC instances and literature instances) where the method yields no improvement. However, the central algorithmic claim is not established. The paper makes no machine-checked proofs or reproducible code available, and the key step from the combinatorial bound to the O(n^{2i}) time bound depends on a lemma that never appears. The present manuscript therefore does not support the advertised complexity result.","major_comments":[{"comment":"The sentence 'Based on Lemma 1, although the 0-1 KP is NP-hard, the decision variables of two subsets N_{i,1} and N_{i,4} can be exactly solved in time complexity O(n^{2i})' is the only bridge from the combinatorial bound |Y_i| ≤ n^{2i} to the claimed runtime. Lemma 1 is never stated, proved, or cited anywhere in the manuscript. Without it, the preceding argument only shows that the optimal solution is contained in a family of at most n^{2i} candidate solutions, each obtained by adjoining some N*_{i,1} and N*_{i,4} to an optimal solution of a residual 0-1 KP on N_{i,2}∪N_{i,3}∪N_{i,5}. Since the paper itself states at the end of Section 3 that this residual subproblem 'is still a NP-hard problem', the O(n^{2i}) exact-resolution claim is unsupported. This is a load-bearing gap in the main result.","section":"Section 3, paragraph after the definition of Y_i"},{"comment":"The chain labeled (12) replaces the ratio (Σ_{j∈D_{i,2}} p_j + Σ_{j∈D_{i,3}} p_j)/(Σ_{j∈D_{i,2}} w_j + Σ_{j∈D_{i,3}} w_j) by Σ_{j∈D_{i,1}} p_j/(Σ_{j∈D_{i,1}} w_j + r) with a strict inequality. Claim 1, as stated, gives only a non-strict inequality, and the paper does not establish strictness. Inequality (13), Σ_{j∈F_{i,3}} p_j - Σ_{j∈F_{i,1}} p_j < (Σ_{j∈F_{i,3}} w_j - Σ_{j∈F_{i,1}} w_j) · (ratio), is asserted without derivation. In particular, the derivation of (16) from (14) and (15) multiplies by the quantity Σ_{j∈F_{i,3}} w_j - Σ_{j∈F_{i,1}} w_j, which could be negative, reversing the inequality; the paper does not prove this quantity is nonnegative. These gaps leave the proof of Theorem 2 incomplete, and Theorem 3 relies on it by symmetry.","section":"Section 3, proof of Theorem 2, equations (12) and (13)"},{"comment":"The text states |N_{i,2} ∪ N_{i,3} ∪ N_{i,5}| = n - n_{i,1} - n_{i,2}; by Definition 2 the correct expression is n - n_{i,1} - n_{i,4}. In addition, the abstract and introduction promise a reduction to at most n^i subinstances, while Section 3 obtains the bound |Y_i| ≤ n_{i,1}^i n_{i,4}^i ≤ n^{2i}. For i=1 the actual number of candidate solutions is 1, not n^2, so the stated bounds are inconsistent. This is not merely cosmetic, because the claimed size of the reduction is the paper's central quantitative message.","section":"Section 3, paragraph starting 'Let n_{i,1}=|N_{i,1}|'"},{"comment":"The statement 'Constant i has no upper bound' is not a formal complexity assertion, and the proof only shows that for any proposed bound m there exists a particular instance in which a specific item q requires i > m to satisfy inequality (8). This does not establish that the residual subproblem is NP-hard; that NP-hardness is already evident from the definition and from the NP-hardness of 0-1 KP. The concluding sentence 'Since constant i has no upper bound, ... the subproblem ... is still a NP-hard problem' is therefore a non sequitur in context. The discussion also conflates the user-fixed algorithmic parameter i with an instance-dependent quantity, which obscures the meaning of the claimed time bound.","section":"Section 3, Theorem 4 and the following paragraph"}],"minor_comments":[{"comment":"The abstract and the introduction state that EDHR reduces an instance to at most n^i subinstances, while Section 3 states n^{2i}; the two quantities should be reconciled, and the parameter i should be defined once in a consistent way.","section":"Abstract and introduction"},{"comment":"The explanation of inequality (9) says 'the left side of inequality (9) is always negative when w_j < r/i'; this statement is correct only if the intended expression is p_j/(w_j - r/i), but the surrounding notation is ambiguous and the prose 'implies that these items are never selected by the optimal solution, which contradicts the actual scenario' is unclear.","section":"Section 3, paragraph after Definition 2"},{"comment":"The experimental section does not provide an algorithm pseudocode for EDHR, nor does it state how the candidate subinstances are solved in the reported runs (for example, whether CPLEX is invoked on each reduced subinstance and whether enumeration overhead is counted in the reported 'ticks'). This makes the experimental comparison difficult to reproduce and to interpret.","section":"Section 4"},{"comment":"The table header refers to |N_{2,1} ∪ N_{2,4}| while the notation in the text uses N_{i,1} and N_{i,4}; the indexing should be made uniform.","section":"Section 4, Table 6"},{"comment":"The sentence 'Our method also reduces the interval gap of the distances from power of 2 to integer and decreases the complexity of the method given by Dey et al.' is not supported by any result or experiment in the paper; either it should be substantiated or removed.","section":"Introduction, last sentence"}],"recommendation":"reject","confidential_remarks":"The manuscript appears to be missing a statement of Lemma 1, which is invoked as the sole support for the central O(n^{2i}) exact-resolution claim. Combined with the paper's own admission that the residual subproblem is NP-hard, the claimed complexity result is not merely underproved but apparently impossible without a polynomial-time oracle for an NP-hard problem. The structural theorems may be salvageable as bounded-deviation results, but the advertised algorithm does not follow. I would suggest the authors re-scope the contribution as a preprocessing heuristic and provide complete proofs and an explicit algorithm before resubmission."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper's real content is a modest generalization of Dembo-Hammer's reduction, but the headline complexity claim does not hold up. Theorems 2 and 3, which bound the number of exceptional items in N_{i,1} and N_{i,4} by i-1, are a natural extension of DHR (the i=1 case gives the classic result). The reduction rule itself could be useful as a preprocessing step: enumerate at most n^{2i} candidate subsets of the \"hard\" items, then solve the residual subproblems. That is a plausible strategy, and the experiments show real tick reductions on several random families, with honest reporting of zero improvement on IC instances.\n\nThe soft spots are serious. The O(n^{2i}) exact-resolution claim is supported only by a 'Lemma 1' that is never stated, proved, or cited. The paper itself concedes that the residual subproblem on N_{i,2} ∪ N_{i,3} ∪ N_{i,5} is NP-hard. Therefore no lemma can supply a polynomial-time oracle for each subinstance; the claimed complexity collapses to 'there are at most n^{2i} NP-hard subproblems.' That is a load-bearing flaw, not a technicality.\n\nThe proof of Theorem 2 also has unjustified steps. Equation (12) turns an inequality into an equality without comment. Inequality (13) is asserted without derivation, and the direction depends on the sign of Σ_{F_i,3}w − Σ_{F_i,1}w, which is not handled. The abstract says the method reduces to at most n^i subinstances, while Section 3 says n^{2i}; that discrepancy affects the stated complexity. The experiments are not reproducible: no code or data, and the parameter i = 2 is chosen after seeing performance.\n\nDespite these problems, the reduction theorems might be salvageable. If the author supplies complete proofs of Theorems 2 and 3 and drops the polynomial-time resolution claim, replacing it with the actual enumeration count plus the explicit NP-hardness of the residual subproblem, the idea could become a short note. As submitted, the central claim is unsupported and the proof is too unreliable. I would not send this to peer review in its current form; the missing lemma alone is disqualifying. If a revised version appears with a complete proof and a corrected complexity statement, it would deserve review.","headline":"Theorems 2 and 3 are a genuine but modest generalization of Dembo-Hammer's reduction, yet the O(n^{2i}) exact-resolution claim rests on an unstated Lemma 1 that cannot exist given the paper's own concession that the residual subproblem is NP-hard.","tokens_in":13043,"tokens_out":8883,"would_cite":false,"duration_ms":81563,"reading_group":"no","serious_thinker":"no","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C27","90C10","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that a 0-1 knapsack instance can be reduced to at most $n^{2i}$ subinstances by extending Dembo-Hammer reduction, leaving only a thin band of uncertain items around the break item.","keywords":["0-1 knapsack problem","reduction algorithm","Dembo-Hammer reduction","break item","core","NP-hardness","search tree","CPLEX"],"falsifier":"Take a random instance with $n=200$, set $i=2$, compute $N_{2,1}$ as defined in the paper, and use an independent exact solver to enumerate all optimal solutions; if two or more items of $N_{2,1}$ are missing from every optimal solution, Theorem 2 is false and the reduction bound collapses.","tokens_in":11997,"feed_emoji":"🎒","tokens_out":11456,"duration_ms":102362,"temperature":0.7,"pith_summary":"The paper proposes EDHR, an extension of Dembo and Hammer's reduction algorithm for the 0-1 knapsack problem. The idea is to leave a thin band of items around the break item unresolved: at most $i-1$ items on the high-density side can be missing from an optimal solution, and at most $i-1$ items on the low-density side can be present. Enumerating these few exceptions reduces an $n$-item instance to at most $n^{2i}$ subinstances, so a practitioner who sets $i=2$ gets $O(n^2)$ subinstances. The author reports experiments on randomly generated instances showing that this preprocessing, run before CPLEX, reduces CPLEX's search-tree size by roughly half for uncorrelated and strongly correlated data and by smaller amounts for other families. The value of the claim, if correct, is a tunable polynomial-time reduction that turns most of the knapsack problem into fixed decisions and leaves only a small core to be searched.","feed_headline":"Knapsack search shrinks to n-squared subinstances","feed_subtitle":"An extension of Dembo-Hammer's algorithm lets practitioners pick how thin the uncertain core gets.","key_machinery":"The load-bearing object is the five-set partition generated by the break item $b$, the residual capacity $r = C - \\sum_{j<b} w_j$, and the integer $i$. The set $N_{i,1}$ collects high-density items whose density stays above $p_b/w_b$ even when their weight is inflated by $r/i$, and $N_{i,4}$ collects low-density items whose density stays below $p_b/w_b$ even when their weight is deflated by $r/i$; the middle sets $N_{i,2}$, $N_{i,3}$, $N_{i,5}$ hold everything else. Theorems 2 and 3 are proved by a counting argument: if too many $N_{i,1}$ items were missing, the compensating profits from $N_{i,4}$ and $N_{i,5}$ items would have to have a higher average density than the missing items can supply, contradicting optimality. This conversion of an intractable search over all $2^n$ subsets into an enumeration over thin exceptional layers is what carries the reduction.","core_discovery":"The central claim is Theorem 2 plus Theorem 3: after ordering items by profit density and locating the break item $b$ with residual capacity $r$, define the partition $N_{i,1}, \\ldots, N_{i,5}$ via the adjusted ratio tests $p_j/(w_j+r/i) > p_b/w_b$ and $p_j/(w_j-r/i) < p_b/w_b$. Then $N_{i,1}$ contains at most $i-1$ items that are not chosen in an optimal solution, and $N_{i,4}$ contains at most $i-1$ items that are chosen. The proof combines the Dantzig bound, the break solution as a lower bound, and a double-counting comparison of the profit lost from missing $N_{i,1}$ items against the profit gained from extra $N_{i,4}$ and $N_{i,5}$ items; Claim 1 bounds the average density of the compensating set. Consequently every optimal solution lies in the family $Y_i$ formed by taking all but at most $i-1$ items of $N_{i,1}$, at most $i-1$ items of $N_{i,4}$, and an optimal solution of the subinstance on $N_{i,2} \\cup N_{i,3} \\cup N_{i,5}$. The author concludes that the original problem is reduced to at most $n^{2i}$ subinstances and, on the strength of an invoked lemma, that the decision variables on $N_{i,1}$ and $N_{i,4}$ are exactly solvable in $O(n^{2i})$ time. The abstract states the bound as $n^i$, while the body's enumeration argument bounds the family by $n^{2i}$; for $i=2$ both are $O(n^2)$.","pith_inferences":["Beyond the paper: the real workload will sit in the subinstances on $N_{i,2} \\cup N_{i,3} \\cup N_{i,5}$; a fair test of EDHR as a solver would report time spent solving those subinstances, not only the reduction's effect on CPLEX ticks.","Beyond the paper: because Theorem 4 shows no fixed $i$ classifies all density-different items, EDHR is best viewed as a parameterized core-reduction scheme; it could be combined with dynamic programming or branch-and-bound on the middle sets to get a hybrid exact solver.","Beyond the paper: a natural experiment is to measure how often $N_{2,1} \\cup N_{2,4}$ is empty on hard benchmark classes; the author's Table 6 suggests such empty cases give zero speedup, so instance generation that maximizes this set would test the algorithm's advertised advantage."],"forward_implications":["Setting $i=1$ reproduces Dembo-Hammer's original reduction, so EDHR is a strict generalization with a single tuning parameter.","With $i=2$ the reduction produces at most $O(n^2)$ subinstances, and the paper's experiments show CPLEX ticks drop by 53.88% on uncorrelated, 51.24% on strongly correlated, and 38.05% on almost strongly correlated instances.","If the invoked lemma holds, EDHR gives a polynomial-time preprocessing step that fixes all but a small core of items before an exact solver runs.","The paper's Theorem 4 says the required $i$ has no universal upper bound, so the practical benefit is instance-dependent rather than a uniform worst-case speedup.","The sets $N_{i,1}$ and $N_{i,4}$ can be used to prune search spaces in metaheuristic solvers, as the author lists as future work."],"supporting_citations":[{"why":"Introduces the original Dembo-Hammer reduction algorithm that EDHR extends.","marker":"[7]"},{"why":"States Theorem 1 and the empirical observation that only a few items around the break item differ between the break solution and an optimal solution.","marker":"[8]"},{"why":"Provides the Dantzig bound and the break-item construction used in the partition definition.","marker":"[18]"},{"why":"Supplies the break-solution lower bound used in the proof of Theorem 2 and the expanding-core context for the reduction.","marker":"[2]"},{"why":"Gives the branch-and-bound polynomial-time result for random binary IPs that EDHR aims to complement with a smaller search tree.","marker":"[19]"},{"why":"Establishes NP-hardness of the knapsack problem, the reason polynomial-time reductions matter.","marker":"[10]"}],"fun_headline_variants":["Knapsack reduction algorithm gains tunable depth","Reduce knapsack to n^i subinstances with new method","Dembo-Hammer extension shrinks knapsack search tree","Knapsack solver cuts search via adjustable reduction","New knapsack reduction allows i-wise subinstance split"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"EDHR's polynomial-time claim rests on an unstated lemma that the leftover subinstances can be solved quickly; if that lemma does not hold, each of the $n^{2i}$ subinstances is itself an NP-hard knapsack problem, and the claimed $O(n^{2i})$ step is unjustified.","fun_headline_variants_meta":{"raw":{"variants":["Knapsack reduction algorithm gains tunable depth","Reduce knapsack to n^i subinstances with new method","Dembo-Hammer extension shrinks knapsack search tree","Knapsack solver cuts search via adjustable reduction","New knapsack reduction allows i-wise subinstance split"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00032,"raw_usage":{"total_tokens":1868,"prompt_tokens":1073,"completion_tokens":795,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":689,"completion_tokens_details":{"reasoning_tokens":714}},"tokens_in":689,"tokens_out":795,"duration_ms":7671,"temperature":1.0,"reasoning_tokens":714,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T06:01:28.794926+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a random instance with $n=200$, set $i=2$, compute $N_{2,1}$ as defined in the paper, and use an independent exact solver to enumerate all optimal solutions; if two or more items of $N_{2,1}$ are missing from every optimal solution, Theorem 2 is false and the reduction bound collapses.","supporting_citations":[{"cited_title":"Dembo, Peter Ladislaw Hammer","cited_arxiv_id":null,"evidence_quote":"Introduces the original Dembo-Hammer reduction algorithm that EDHR extends."},{"cited_title":"An expanding-core algorithm for the exact 0-1 knapsack problem","cited_arxiv_id":null,"evidence_quote":"States Theorem 1 and the empirical observation that only a few items around the break item differ between the break solution and an optimal solution."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the Dantzig bound and the break-item construction used in the partition definition."},{"cited_title":"A Minimal Algorithm for the 0-1 Knapsack Problem","cited_arxiv_id":null,"evidence_quote":"Supplies the break-solution lower bound used in the proof of Theorem 2 and the expanding-core context for the reduction."},{"cited_title":"Dey, Yatharth Dubey, Marco Molinaro","cited_arxiv_id":null,"evidence_quote":"Gives the branch-and-bound polynomial-time result for random binary IPs that EDHR aims to complement with a smaller search tree."},{"cited_title":"Reducibility among Combinatorial Problems","cited_arxiv_id":null,"evidence_quote":"Establishes NP-hardness of the knapsack problem, the reason polynomial-time reductions matter."}],"review_version":1}