{"id":"655aa9a8-22c0-4d15-9ad2-72687d2f544c","arxiv_id":"2501.12261","paper_version":4,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A framework yields poly(n,k) or f(k)poly(n) time (1-epsilon)-approximations for diverse-solution variants of several NP-hard problems using resource augmentation and k-best enumeration.","lead":"Algorithms researchers give the first polynomial-time approximation algorithms for generating diverse collections of solutions to several NP-hard optimization problems, allowing a small loss in solution quality. The paper's framework combines local search with budget-constrained k-best enumeration and applies to knapsack, planar independent sets and vertex covers, rectangle packing, enclosing polygons, and unit-disk graphs in convex position.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 18's weight-scaling formula divides by w(S) instead of W, so a feasible c-optimal solution of near-full capacity can be excluded from the scaled search space; this invalidates the diverse-knapsack PTAS (Theorem 5(2)) as stated.","rationale":"The reader's weakest_assumption identifies exactly Lemma 18's weight-scaling denominator, and I agree that this is the most load-bearing concern. Theorem 5(2) is a headline result, and its proof relies on Lemma 18(1) to argue that every original c-optimal solution survives in the scaled instance; that argument is false when the reference solution S has small weight. The signed-score issue in the k-BCBE condition is a secondary formal gap: Condition (3) assumes 0 <= r <= R while Algorithm 1's score function is signed, but this appears repairable by restating the condition with |r| <= R and letting DP score ranges include negative values. Lemma 18, by contrast, requires changing the scaling denominator and re-proving the knapsack application. I do not call for rejection: the framework architecture, the planar MWIS/MWVC construction, and the treewidth-based k-BCBE DP are structurally plausible and mostly independent of the broken weight-scaling lemma. The appropriate verdict remains CONDITIONAL: accept only after Lemma 18 is corrected and Theorem 5(2) is re-verified.","tokens_in":30402,"tokens_out":12116,"duration_ms":123582,"concrete_test":"Run the numerical check with n=2, W=100, w=(1,99), u=(100,99), c=0.5, delta=gamma=0.1, S={item1}. Compute tilde W and tilde w_2 using the printed Lemma 18 formula, and also with the intended tilde W = floor((1+gamma)/gamma * n) to remove typesetting ambiguity. In both readings, tilde w_2 > tilde W, so {item2} is absent from the scaled search space, contradicting Lemma 18(1). Then recompute with tilde w_h = floor(tilde W * w_h / W); the containment tilde w(X) <= tilde W holds for every feasible X. This single check settles whether the diverse-knapsack PTAS's key containment step is valid.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 18 in Appendix A is the load-bearing point. Its profit scaling works because a c-optimal solution X satisfies u(X) >= c*u(S), so the floor loss in each term is absorbed and the summed scaled profit remains above tilde U. The weight scaling copies this template but divides by w(S): tilde w_h = floor((tilde W - n)/w(S) * w_h). For weights, a feasible X only satisfies w(X) <= W, which can be arbitrarily larger than w(S). When a high-profit, low-weight reference solution S is used, a feasible c-optimal solution with weight near W can have tilde w(X) >> tilde W and is excluded from the scaled space. This contradicts Lemma 18(1) and removes the search-space containment argument in the proof of Theorem 5(2). Concretely, with W=100, item weights (1,99), profits (100,99), c=0.5, and S={item1}, the feasible c-optimal solution {item2} maps to a scaled weight far above tilde W, regardless of whether tilde W is the printed value or the intended O(n/gamma) threshold. Since Lemma 16 enumerates only the scaled space, the optimal diverse collection of original c-optimal solutions may be missing. The fix is to divide by W, or by a valid upper bound on all feasible weights, not by w(S); the sentence 'the argument for weights is analogous' is not an analogy.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a general framework (Theorem 9) for computing k diverse, approximately optimal solutions to NP-hard optimization problems, building on the local-search approach of Cevallos et al. and the k-best enumeration ideas of Hanaka et al. and Gao et al. The framework requires four ingredients: a resource-augmented solution space F'_c with a diversity-preservation guarantee, a budget-constrained k-best enumeration (k-BCBE) algorithm, and an exact optimizer for small k. The authors apply the framework to diverse knapsack, diverse maximum-weight independent sets and minimum-weight vertex covers in planar graphs, rectangle packing, enclosing polygons, unit-disk graphs in convex position, and TSP tours, claiming the first poly(n,k) or f(k)poly(n)-time approximation algorithms for several of these problems. The appendices contain full proofs, including a marginal-strata lemma for planar graphs, a k-BCBE dynamic program on tree decompositions, and a scaling/rounding lemma for knapsack.","tokens_in":30706,"tokens_out":16985,"duration_ms":176668,"significance":"If the framework and its applications are correct, this is a substantial contribution: it would give the first polynomial- or f(k)poly(n)-time approximation algorithms for diverse-solution versions of several NP-hard problems, with the planar MWIS/MWVC result being particularly notable. The paper is also explicit about resource augmentation and about the trade-off between diversity and quality, and Theorem 15's k-BCBE on tree decompositions is a concrete algorithmic tool that may be reusable. The claims in the abstract are strong, and they are backed by detailed proofs rather than only sketches. However, the current text has load-bearing gaps in the knapsack scaling lemma and in the treatment of signed score functions inside the framework, so the significance is conditional on those being repaired.","major_comments":[{"comment":"The weight half of Lemma 18(1) is false as stated. The proof handles profits and says that the argument for weights is analogous, but the two arguments are not analogous: the profit scaling uses the c-optimality lower bound u(X) ≥ c·u(S) to absorb the floor losses, whereas for weights a feasible solution X is only known to satisfy w(X) ≤ W, and the reference weight w(S) can be arbitrarily small compared with W. Concretely, take n=2, W=100, item 1 with weight 1 and profit 1000, item 2 with weight 100 and profit 100, c=0.05, and S={item 1}. Then X={item 2} is c-optimal, but with γ=0.1 one has tilde W = floor((1.1/0.1)·2)=22 and tilde w(X) = floor(((22-2)/1)·100) = 2000 > 22 = tilde W, contradicting Lemma 18(1). Since Lemma 16 and the proof of Theorem 5(2) enumerate only the scaled space, such c-optimal solutions can be excluded, so the containment argument for the original optimal diverse collection breaks and the claimed (1-ε) diversity guarantee and (1+γ)W capacity guarantee are not established. The fix is to divide by W, or by a valid upper bound on all feasible weights, rather than by w(S), and to give an actual proof for the weight direction; the weighted planar extension at the end of Section 4 inherits the same defect because it reuses this 'analogous' scaling for vertex weights.","section":"Appendix A, Lemma 18(1) and proof of Theorem 5(2)"},{"comment":"Condition (3) of Theorem 9 is stated only for integer-valued score functions r with 0 ≤ r ≤ R, but Algorithm 1 defines r(e) = Σ_{S_j ∈ S−S_i} (1(e ∉ S_j) − 1(e ∈ S_j)), which can be negative. The proof of Theorem 9 then asserts that r(e) is the number of solutions containing e, but that is not what Equation (1) defines. This is not a cosmetic mismatch: the supplied k-BCBE algorithms are only written for nonnegative scores (Lemma 17 scans R' from nk down to 0, and Theorem 15's proof assumes 0 ≤ R' ≤ R). Adding a constant to every element score does not preserve the order of set scores when feasible solutions have different cardinalities, as they do for knapsack and for c-optimal independent sets. The framework should either extend Condition (3) to signed scores with a range of length 2nk and adapt the enumeration proofs, or explicitly define and justify a nonnegative score that exactly represents the best-swap objective.","section":"Section 3.1, Theorem 9 proof, and Condition (3)"}],"minor_comments":[{"comment":"The summation in Equation (1) is written as Σ_{j∈[i]} but the intended range is j ∈ [k]; please correct the index range.","section":"Section 3.1, Algorithm 1"},{"comment":"The phrase 'Let A_h be a bad set, every p in which satisfies (i′)' is not implied by the definition of a bad set; the counting argument should first assign each bad p to one of the k+1 witness types (one per h plus the diversity type) and then bound each type separately.","section":"Lemma 11 proof"},{"comment":"The bound 'the score of any subset of V is no greater than r(V)' is only valid for nonnegative scores; for the signed scores used in Algorithm 1 the correct bound is |r(S)| ≤ nk, so the proof should explicitly index scores in the range [−nk, nk].","section":"Theorem 15 proof"},{"comment":"The definition w(e) = Σ_{h∈[k]}(1(e∉T_h) − 1(e∉T_h)) has the second indicator reversed; it should be 1(e∈T_h), otherwise the score is identically zero.","section":"Appendix E, proof of Theorem 28(1)"},{"comment":"References [34] and [35] are the same paper and should be merged into a single entry to avoid duplication.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The paper is a good fit for the journal's scope and the overall idea is strong, but the current version has two load-bearing gaps: the weight scaling in Lemma 18 and the use of signed score functions in the framework. Both appear to be fixable with local changes, so I do not recommend rejection. The authors should also make sure that the planar weighted extension is proved directly rather than by an 'analogous' argument that the knapsack lemma does not support."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the paper is the first to put resource augmentation and diversity preservation into a common framework, and the planar MWIS/MWVC result (Theorem 6) looks genuinely new and largely correct. Second, the diverse-knapsack PTAS in Theorem 5(2) is not supported by the current proof: Lemma 18's weight-scaling formula divides by w(S), the weight of one feasible reference solution, instead of a quantity that bounds all feasible solutions. The stress-test counterexample is legitimate. A c-optimal solution with weight near W can map to a scaled weight far above ~W and be excluded from the search space, so the containment in Lemma 18(1) fails and the diversity guarantee in Theorem 5(2) goes with it. This is a load-bearing flaw, not a typo.\n\nWhat is good: Conditions (1) and (2) are a clean extension of the known k-best enumeration frameworks, and the marginal strata lemma for planar graphs is a nice idea. The k-BCBE DP on tree decompositions is plausible, and the paper is honest about how it builds on Hanaka et al., Gao et al., and Cevallos et al. The other applications are sketches, but the framework unifies them.\n\nThe soft spots, in proportion: the weight-scaling error is major but likely fixable (divide by W, or by a proper upper bound on feasible weights; adjust the capacity-violation constant). The signed-score issue is real but minor: the local search score can be negative, while the stated DP range is nonnegative; it can be fixed by shifting the score range. The marginal strata proof is dense and should be checked carefully in review, but I don't see a fatal gap there.\n\nBottom line: the paper deserves a serious referee. The framework and the planar results are worth publishing after revision, and the knapsack PTAS is probably repairable. I would send it out, with instructions to focus on Lemma 18 and on the k-BCBE score range.","headline":"A promising framework and a genuinely new planar MWIS/MWVC result, but the advertised diverse-knapsack PTAS is broken by a wrong denominator in Lemma 18's weight scaling.","tokens_in":31251,"tokens_out":8449,"would_cite":true,"duration_ms":80436,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W25"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper gives the first polynomial-time approximation algorithms for generating diverse collections of solutions to NP-hard problems, using a framework that turns dynamic programs plus a k-best enumeration routine into diversity…","keywords":["diverse solutions","NP-hard problems","approximation algorithms","resource augmentation","knapsack","planar graphs","k-best enumeration","local search"],"falsifier":"Take a knapsack instance with capacity 100, item A of weight 1 and profit 100, and item B of weight 100 and profit 60, with c = 0.5 and delta = gamma = 0.1. Both {A} and {B} are c-optimal, but the weight scaling of Lemma 18 maps B's weight to roughly 2000 while the scaled bound is 22, so B leaves the search space; an implementation that then outputs only solutions derived from A contradicts the claimed (1-epsilon) diversity guarantee over the c-optimal space. Checking whether the algorithm's output diversity exceeds what is achievable using only sets of weight near 1 would settle the matter.","tokens_in":30192,"feed_emoji":"🧩","tokens_out":8156,"duration_ms":82015,"temperature":0.7,"pith_summary":"The paper claims to close a gap: for NP-hard problems, the only previously known algorithms for producing k diverse feasible solutions were FPT with exponential dependence on the input size, while polynomial-time approximations existed only for problems in P. Its framework, stated as Theorem 9, shows that if a problem supplies a resource-augmented solution space, a diversity-preserving collection inside it, a budget-constrained k-best enumeration routine, and an exact optimizer for small k, then one obtains a (1-epsilon)-approximation to the sum of pairwise symmetric differences with only a (1-delta)c quality relaxation. Applying the framework yields a PTAS for diverse knapsack with small capacity violation, and (1-epsilon)-approximations for diverse planar maximum-weight independent sets and minimum-weight vertex covers in $2^{{O(k/(delta epsilon^2))}}$ $n^{{O(1/epsilon)}}$ time. The practical value is that near-optimal, genuinely different alternatives can be generated efficiently, which matters for decision support, robustness, and energy efficiency in applications such as sensor networks.","feed_headline":"First poly-time approximations for diverse NP-hard solutions","feed_subtitle":"A framework turns dynamic programs into diversity approximations, with PTASs for knapsack and planar graphs.","key_machinery":"The load-bearing object is the budget-constrained k-best enumeration (k-BCBE) problem: given an extra integer-valued score r on subsets, return the k distinct c-optimal solutions with the largest r-values. Theorem 9 combines a k-BCBE oracle with the MAX-SUM local-search algorithm of [12], which reaches diversity at least max{1/2, 1 - 2/(k+1)} of optimum after O(k log k) swaps, and with the enumeration-to-swap translation of [27]. Conditions (1) and (2) supply the resource-augmented space F'_c (solutions that are only (1-delta)c-optimal, for example planar independent sets avoiding a deleted marginal layer) and the guarantee that moving from F_c to F'_c costs at most epsilon/2 in diversity. The k-BCBE routines are built by adding a score dimension to textbook dynamic programs and applying the k-best method of [38].","core_discovery":"The central discovery is that the obstacle to polynomial-time diverse solutions for NP-hard problems is not diversity itself but the need to search the full space of c-optimal solutions. The paper defines a resource-augmented search space F'_c of solutions that are only (1-delta)c-optimal and shows that if F'_c contains a collection whose pairwise sum is within (1-epsilon/2) of the optimum over F_c, then applying the local-search/k-best enumeration framework inside F'_c loses only a (1-epsilon) factor in diversity while degrading quality by only delta. This reduces the design task to two ingredients: a budget-constrained k-best enumeration routine over F'_c and an exact diverse optimizer for small k. For the paper's target problems, both ingredients come from augmenting known dynamic programs with an extra score dimension and using a k-best enumeration method; the planar applications additionally use a marginal-layer deletion argument to build F'_c.","pith_inferences":["[Editorial inference] The resource-augmentation design pattern is transferable: any NP-hard problem with a PTAS that restricts to a structured subspace may be a candidate, provided the missing structure contributes only an epsilon fraction to diversity.","[Editorial inference] The k-BCBE ingredient suggests a generic recipe: take the existing dynamic program for the single-solution problem, add a dimension tracking the score function, and apply k-best enumeration; this could extend to other treewidth-bounded or geometric problems beyond those listed.","[Editorial inference] The guarantees concern average pairwise Hamming distance, not minimum pairwise distance; the paper itself connects max-min versions to Hamming-code computations, hinting that max-min diversity may be genuinely harder.","[Editorial inference] Because the local-search factor is max{1/2, 1 - 2/(k+1)}, a user with small k who wants strong diversity needs the exact small-k branch, which only applies when k < 4/epsilon; otherwise the guarantee may be closer to half the optimal diversity."],"forward_implications":["Diverse knapsack admits a PTAS with (1-delta) quality relaxation and solutions of weight at most (1+gamma)W, so a small capacity violation is the price of polynomial running time.","Diverse planar maximum-weight independent sets and minimum-weight vertex covers admit (1-epsilon)-approximations in 2^{O(k/(delta epsilon^2))} n^{O(1/epsilon)} time, making them PTASs when k = O(log n).","Rectangle packing, enclosing polygons, and maximum-weight independent sets on unit-disk graphs of points in convex position inherit the framework with polynomial or f(k)poly(n) running times and explicit diversity-quality trade-offs.","The framework converts the design task for any NP-hard problem with a textbook dynamic program into two ingredient tasks, namely k-BCBE and an exact small-k optimizer, so the results are not isolated algorithms."],"supporting_citations":[{"why":"Supplies the MAX-SUM diversification local-search algorithm whose O(k log k) swaps give the max{1/2, 1 - 2/(k+1)} approximation factor used inside the framework.","marker":"[12]"},{"why":"Shows how to implement the best swap when the solution space is implicit by running k-best enumeration k times, which the paper's Algorithm 1 follows.","marker":"[27]"},{"why":"Provides the earlier diverse-solution framework allowing a user-specified approximation level c, which the paper merges with [27] and extends to NP-hard problems.","marker":"[24]"},{"why":"The planar layer-decomposition technique that defines the resource-augmented space F'_c for planar independent sets and vertex covers.","marker":"[5]"},{"why":"Gives the existing exact FPT algorithm for diverse independent sets and vertex covers used to satisfy Condition (4) for small k.","marker":"[6]"},{"why":"Provides the single-solution (1-delta)-approximation for knapsack used to seed the scaling and rounding step in Lemma 18.","marker":"[46]"},{"why":"The k-best enumeration method that turns the augmented dynamic programs into k-BCBE routines in the applications.","marker":"[38]"}],"fun_headline_variants":["Poly-time diverse solutions for NP-hard problems","Framework yields first poly-time diversity for NP-hard","Diverse NP-hard solutions now in polynomial time","Efficient diversification for knapsack and planar graphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The scaling and rounding step assumes that one feasible solution S can be used to normalize item weights, which only works when S has weight comparable to the knapsack capacity; otherwise a feasible solution of weight near capacity can be rounded above the search bound and silently dropped, breaking both the diversity and capacity guarantees.","fun_headline_variants_meta":{"raw":{"variants":["Poly-time diverse solutions for NP-hard problems","Framework yields first poly-time diversity for NP-hard","Diverse NP-hard solutions now in polynomial time","Efficient diversification for knapsack and planar graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000401,"raw_usage":{"total_tokens":2174,"prompt_tokens":1106,"completion_tokens":1068,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":722,"completion_tokens_details":{"reasoning_tokens":1009}},"tokens_in":722,"tokens_out":1068,"duration_ms":10364,"temperature":1.0,"reasoning_tokens":1009,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T17:23:20.516792+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a knapsack instance with capacity 100, item A of weight 1 and profit 100, and item B of weight 100 and profit 60, with c = 0.5 and delta = gamma = 0.1. Both {A} and {B} are c-optimal, but the weight scaling of Lemma 18 maps B's weight to roughly 2000 while the scaled bound is 22, so B leaves the search space; an implementation that then outputs only solutions derived from A contradicts the claimed (1-epsilon) diversity guarantee over the c-optimal space. Checking whether the algorithm's output diversity exceeds what is achievable using only sets of weight near 1 would settle the matter.","supporting_citations":[{"cited_title":"An improved analysis of local search for MAX-SUM diversification","cited_arxiv_id":null,"evidence_quote":"Supplies the MAX-SUM diversification local-search algorithm whose O(k log k) swaps give the max{1/2, 1 - 2/(k+1)} approximation factor used inside the framework."},{"cited_title":"A framework to design approximation algorithms for finding diverse solutions in combinatorial problems","cited_arxiv_id":null,"evidence_quote":"Shows how to implement the best swap when the solution space is implicit by running k-best enumeration k times, which the paper's Algorithm 1 follows."},{"cited_title":"Obtaining approximately optimal and diverse solutions via dispersion","cited_arxiv_id":null,"evidence_quote":"Provides the earlier diverse-solution framework allowing a user-specified approximation level c, which the paper merges with [27] and extends to NP-hard problems."},{"cited_title":"Approximation algorithms for NP-complete problems on planar graphs.Journal of the ACM (JACM), 41(1):153–180, 1994","cited_arxiv_id":null,"evidence_quote":"The planar layer-decomposition technique that defines the resource-augmented space F'_c for planar independent sets and vertex covers."},{"cited_title":"Diversity of solutions: An exploration through the lens of fixed- parameter tractability theory.Artificial Intelligence, 303:103644, 2022","cited_arxiv_id":null,"evidence_quote":"Gives the existing exact FPT algorithm for diverse independent sets and vertex covers used to satisfy Condition (4) for small k."},{"cited_title":"Springer, 2001","cited_arxiv_id":null,"evidence_quote":"Provides the single-solution (1-delta)-approximation for knapsack used to seed the scaling and rounding step in Lemma 18."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The k-best enumeration method that turns the augmented dynamic programs into k-BCBE routines in the applications."}],"review_version":1}