{"id":"d8e9a9d4-9ce3-47db-bd1a-65805a8d5918","arxiv_id":"2412.00717","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"A polynomial-time, constant-factor approximation algorithm exists for selecting k matroid-constrained solutions to maximize the expected value of the best solution under independent Bernoulli item activations.","lead":"This paper defines a new portfolio problem: given a combinatorial problem and a distribution over scenarios, pick k candidate solutions so that the best one is as good as possible in expectation. It gives a polynomial-time, constant-factor approximation algorithm for matroid constraints when each item is active independently.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 5.5's step (5) assumes e∈S_{i*} and e∈~A are independent given i*, but conditioning on the argmax correlates V_{i*} with A; the equality is false, so the constant factor for Case 1 is unproven.","rationale":"The reader's verdict identifies conditional-feasibility after conditioning on i*,C* as the weakest assumption. That is a legitimate concern, but the single most load-bearing problem is one step further into Lemma 5.5: even granting that the CRS guarantee holds under the conditioning, the proof does not validly convert per-element retention into expected active retained elements. The equality at line (5) is an independence assertion that fails whenever the event i* is informative about V_{i*}, which it always is because i* is defined through |V_i∩~A|. The toy calculation makes this concrete and removes any ambiguity about interpretation. This is load-bearing because Lemma 5.5 is the exclusive support for Case 1 (high-probability items). Section 5.4 splits the analysis into Case 1 and Case 2; if Lemma 5.5 fails, the column portfolio is not shown to be a constant-factor approximation in Case 1, and Algorithm 2's guarantee is unsupported regardless of the correctness of Lemma 5.7. The issue is not a matter of tight constants; the 1/8 factor can vanish entirely if the correlation is adversarial. The recommendation is CONDITIONAL rather than REJECT, because the underlying claim may be true and the gap is localized: the authors could potentially repair the proof by applying the CRS to the active elements directly, by conditioning on a richer event that makes the sampled set and activation independent, or by replacing the column-portfolio analysis with a different argument. But as written, the proof of Theorem 3.1 is incomplete, and acceptance should be contingent on such a repair. No issue with novelty or experiments; this is a technical correctness gap in the main theorem's proof.","tokens_in":37571,"tokens_out":20468,"duration_ms":188158,"concrete_test":"Recompute Lemma 5.5's disputed equality in the toy instance: ground set {x,y,z,w}, matroid U_{2,4}, prefix B1={x,z}, B2={y,w}, reference base with one high element of probability 1/2, k=2, and fixed tie-breaking to the smaller index. Let x be a fixed element of the high column. Enumerate the 16 equiprobable outcomes (or use a short script) to compute P(x∈V_1,A_x=1|i*=1) and P(x∈V_1|i*=1)·P(A_x=1|i*=1): the first is 2/7 and the second 1/4. Then repeat with the CRS of Algorithm 5 or an idealized CRS keeping each sampled element with probability 1/8, and check whether the equality at line (5) holds. If the numbers differ, Lemma 5.5 needs a corrected proof or the theorem requires a different argument.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The main theorem rests on Lemma 5.5 for Case 1. The proof's Step 2 converts the CRS guarantee into a bound on expected active elements kept, and the conversion uses the equality at line (5): Pr[e∈S_{i*}∩~A | i*=i'] = Pr[e∈S_{i*}|i*=i'] · Pr[e∈~A|i*=i'], claimed by independence. This is not valid. Since i* is the argmax of |V_i∩~A|, conditioning on i*=i' correlates V_{i*} with the activation pattern ~A. Consequently e∈V_{i*} and e∈~A are dependent given i*=i', and since S_{i*}=CRS(V_{i*}), the same dependence propagates to e∈S_{i*} unless the CRS retention is independent of V_{i*} (which Algorithm 5 does not provide). A minimal instance illustrates the failure: take a U_{2,4} matroid with prefix bases B1={x,z}, B2={y,w}, one high column {x,y} with p=1/2 and zero-probability elements z,w; k=2; tie-breaking to the smaller index. Enumerating outcomes gives P(x∈V_1|i*=1)=1/2, P(A_x=1|i*=1)=1/2, but P(x∈V_1,A_x=1|i*=1)=2/7, so the factorization used in the proof is false. With an idealized CRS that keeps sampled elements with independent probability 1/8, the corresponding S_1/A_x factorization also fails. Thus Lemma 5.5, and with it the Θ(1) guarantee in Case 1 of Theorem 3.1, is not established by the written proof.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a stochastic portfolio-optimization problem over matroids: given a matroid and a product distribution over active elements, choose k independent sets so as to maximize the expected size of the best (largest) selected set under a random activation pattern. The main claim (Theorem 3.1) is a polynomial-time constant-factor approximation algorithm. The algorithm greedily orders disjoint maximum-expectation bases, considers all prefixes of this ordering, and for each prefix constructs two portfolios (uniform sampling and column-wise sampling), each followed by a contention resolution scheme. The analysis splits into a high-probability case, handled by the column portfolio, and a low-probability case, handled by the uniform portfolio. A simpler constant-factor algorithm for uniform matroids is given first as a warm-up.","tokens_in":37960,"tokens_out":20504,"duration_ms":185794,"significance":"The problem is well motivated and the paper contains a substantial algorithmic idea: constructing portfolios that exploit anti-concentration by mixing over columns, and using contention resolution schemes under conditioning on outlier events. The manuscript is self-contained, makes no use of fitted constants, and includes explicit reductions justifying the three simplifying assumptions, plus an NP-hardness reduction for general distributions. If the missing step in the matroid analysis is repaired, the paper would be a solid contribution to data-driven algorithm design and randomized combinatorial optimization. In its current form, however, one load-bearing step in the proof of the constant-factor guarantee is not justified.","major_comments":[{"comment":"The proof of Lemma 5.5 passes from Eq. (4) to Eq. (5) by asserting that, conditioned on i*=i', the events e∈S_{i*} and e∈~A are independent, and therefore Pr[e∈S_{i*}∩~A | i*=i'] = Pr[e∈S_{i*}|i*=i'] · Pr[e∈~A|i*=i']. This is false: the conditioning event i*=argmax_i |V_i∩~A| correlates the sampled positions V_i with the activation pattern ~A, and this dependence propagates to S_{i*} because S_{i*} is obtained from V_{i*}. For a concrete instance, take the rank-2 uniform matroid U_{2,4}, prefix bases {x,z} and {y,w}, one column {x,y} with d=2, k=2, p_x=p_y=1/2, z,w inactive, and tie-breaking to the smaller index. Enumerating the sixteen equiprobable outcomes gives Pr[x∈V_1|i*=1]=7/13, Pr[A_x=1|i*=1]=6/13, but Pr[x∈V_1, A_x=1|i*=1]=4/13; the product is 42/169, not 4/13. The same failure persists with an idealized CRS that retains sampled elements independently with probability 1/8: conditional on i*=1, Pr[x∈S_1|i*=1]=(1/8)·(7/13) and Pr[A_x=1|i*=1]=6/13, but Pr[x∈S_1, A_x=1|i*=1]=(1/8)·(4/13), so the factorization used in line (5) is still invalid. Consequently, the proof of Lemma 5.5, and with it the Case 1 half of Theorem 3.1, is not established as written.","section":"5.4.1, Lemma 5.5, Eq. (5)"},{"comment":"Lemma 5.5 also relies on the assertion that, after conditioning on i*=i' and C*=C', the sets V_i are still generated by a feasible sampling strategy in the sense of Definition 5.1. The proof gives a short argument for the marginal condition but only states that the negative-dependence condition 'can be proven by the principle of deferred decisions' without providing the actual argument. This is not a purely formal gap: conditioning on the argmax correlates the joint distribution of sampled elements with the activation pattern, so the inequality Pr[e∈span(V_i\\{e}) | e∈V_i, i*, C*] ≤ Pr[e∈span(V_i\\{e}) | i*, C*] needs a separate, non-obvious proof. As written, Theorem 5.2 cannot be invoked after this conditioning, so the 1/8 retention guarantee in Eq. (≀) is unsupported.","section":"5.4.1, Lemma 5.5, conditional feasibility"}],"minor_comments":[{"comment":"The loop 'for i = 1, . . . , n do Order[n−i−1] = e*' appears to be off by one: for i=n it writes to index −1 and the last position Order[n−1] is never assigned. The intended assignment is probably Order[n−i] (or the loop should use zero-based indices consistently).","section":"Appendix C, Algorithm 5"},{"comment":"In the final display of the proof, the text says 'for (4) we used a union-bound', but the step replaces sum_{A'∈W} Pr[A=A'] by Pr[A∈W], which is an equality because the events are disjoint; the explanation should be corrected accordingly.","section":"Lemma 5.10"},{"comment":"The pseudocode samples r elements with replacement and then removes duplicates, so the resulting sets may have size strictly less than r. The subsequent analysis treats S_i as a set of distinct elements; this is consistent, but it would help to state explicitly that the value of a solution counts distinct elements, and that feasibility under the uniform matroid is preserved.","section":"Section 4, Algorithm 1"}],"recommendation":"major_revision","confidential_remarks":"The gap in Lemma 5.5 is load-bearing for the main theorem, so the current version should not be accepted. The issue is a genuine technical error in the proof, not merely a missing reference or an unclear sentence, but it may be repairable with a more careful conditional-CRS argument. If the authors can either prove the conditional independence/feasibility properly or restructure the proof of Lemma 5.5, the paper is likely to be publishable in a strong venue."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is a genuinely new algorithmic result with a clever algorithm, but the proof of the main theorem has a gap in Lemma 5.5 that needs to be fixed before the result is citable.\n\nThe paper formulates a natural problem—choosing k solutions to maximize the expected best under independent Bernoulli activations on a matroid—and shows the naive greedy/submodular view is not enough because the solution space is huge. The uniform-matroid warm-up (Section 4) is solid and clearly explained. The general algorithm, based on an ordering of disjoint bases, a column decomposition, and a contention resolution scheme, is interesting and the high-level strategy is sound. The paper also does the right thing in stating assumptions and proving they are w.l.o.g. There is no circularity or fitted constants.\n\nThe problem is in Lemma 5.5, Case 1 of the general analysis. The proof's step (5) assumes that, after conditioning on the identity of the winning set i*, the events e∈S_i* and e∈~A are independent. They are not. Conditioning on i* correlates the composition of the winning set with the activation pattern: a set is more likely to win if it sampled active elements. The stress-test's U_{2,4} example demonstrates this concretely: P(x∈V1,A_x=1|i*=1)=2/7, whereas the product of marginals is 1/4. So the factorization used to lower-bound the kept active elements is false. This is not a cosmetic issue: the 1/8 retention bound in Case 1 depends on it, and Case 1 is half of the main theorem. The proof needs an alternative argument—perhaps a positive-correlation inequality, since the bias seems to go in the right direction, or a different conditioning—to recover the bound. The minimal example does not suggest the theorem is false; the inequality may still hold. But as written, the main result is not fully proven for Case 1.\n\nThe rest of the analysis, including Lemma 5.7, has similar conditioning-on-outlier concerns, but I did not find a concrete counterexample there. The proof's deferred-decision arguments are plausible, just under-specified.\n\nWho should read this: anyone working on data-driven algorithm design, portfolio optimization, or matroid contention resolution. The problem statement alone is worth knowing. But a serious referee should push for a corrected Lemma 5.5 before accepting. I would send it to review, and I hope the authors can fix the gap; if they do, the paper is a strong accept.","headline":"Fresh problem, clever algorithm, but a real gap in Lemma 5.5 makes the main theorem unproven as written.","tokens_in":38479,"tokens_out":14166,"would_cite":false,"duration_ms":125711,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W25","05B35","90C27"],"pacs":[],"model":"deepseek-v4-flash","headline":"A polynomial-time algorithm constructs a portfolio of k matroid solutions whose best is within a constant factor of the optimum.","keywords":["portfolio optimization","matroid","approximation algorithm","contention resolution scheme","stochastic optimization","data-driven algorithm design","Poisson binomial","submodularity"],"falsifier":"A direct numerical check would compute, on the smallest matroid where the column decomposition creates dependencies (for instance a graphic matroid on three elements with prefix length $d=2$), the conditional marginal vector and both sides of the negative-dependence inequality after conditioning on $i^*=i'$ and $C^*=C'$; if either condition of Definition 5.1 fails, Theorem 5.2's retention bound of $1/8$ cannot hold and the constant-factor claim collapses. Alternatively, simulate Algorithm 2 on random graphic matroids with adversarial probabilities and compare the empirical approximation ratio; a ratio tending to zero would disprove the theorem.","tokens_in":37394,"feed_emoji":"🎲","tokens_out":5758,"duration_ms":151395,"temperature":0.7,"pith_summary":"This paper proposes a stochastic portfolio-optimization problem and claims an efficient solution for it. Given a matroid whose elements are independently active with known probabilities, the goal is to choose $k$ independent sets offline so that the expected size of the best one (the one with most active elements) is maximized. Because the solution family is usually exponential, the natural submodular greedy approach is infeasible. The paper's central claim is a polynomial-time algorithm returning a portfolio whose expected value is within a constant factor $\\Theta(1)$ of the optimal portfolio, for every matroid. The significance is that a single, data-independent selection of $k$ solutions can hedge against uncertainty whenever the underlying feasibility constraint is a matroid.","feed_headline":"Constant-factor portfolios for matroids in polynomial time","feed_subtitle":"The best of k precomputed solutions is provably near the optimum under element-wise uncertainty","key_machinery":"The central machinery is a column decomposition plus a feasible-sampling contention-resolution scheme (CRS). For a prefix of $d$ bases and next base $B_{d+1}$, basis-exchange bijections map each element of $B_{d+1}$ to $d$ elements in the prefix, producing columns; the column portfolio samples one element per column. The CRS used is designed for 'feasible sampling strategies' (Definition 5.1): marginal inclusion probabilities whose half-vector lies in the matroid polytope, plus a negative-dependence condition. Theorem 5.2 gives that every element is retained by the CRS with probability at least $1/8$, and the proof of the constant factor hinges on showing that even after conditioning on outlier events (the winning index $i^*$, the active columns $C^*$, or the sampled independent set $I^*$), the sampling remains feasible via deferred decisions. The remaining analysis uses stochastic dominance lemmas for Poisson-Binomial variables and a balls-and-bins bound on distinct sampled elements.","core_discovery":"The central claim is Theorem 3.1: under a product distribution (each element active independently with probability $p_e$), Algorithm 2 is a $\\Theta(1)$-approximation for the $k$-portfolio solution problem over any matroid, with polynomial time complexity. The proof builds an ordering of disjoint highest-expectation bases, examines every prefix, and for each prefix constructs two portfolios — one by uniform sampling from the prefix, one by sampling one element from each 'column' of a basis-exchange decomposition — then trims each sampled set with a contention-resolution scheme. A key structural insight is that the optimal portfolio restricted to elements outside the chosen prefix already achieves $\\Theta(1)$ of OPT, and these solutions can be stochastically dominated by independent copies of the next highest-expectation basis. The analysis then splits on whether high- or low-probability elements of that basis drive the optimum, showing the column portfolio handles the first case and the uniform portfolio the second. The paper also establishes that for general distributions no $(1-1/e+\\epsilon)$-approximation is possible unless P=NP.","pith_inferences":["One testable extension is whether the same constant-factor guarantee survives positively correlated activation (for example, a common latent factor), since the proof's independence assumptions enter through the CRS feasibility and the Poisson-Binomial dominance lemmas.","The column-decomposition idea suggests a template for other implicitly defined solution sets: whenever basis-exchange bijections exist and a feasible sampling strategy can be defined, a similar prefix-and-portfolio algorithm may yield constant-factor guarantees.","The paper leaves open the tightest constant; reading off the proof constants suggests improvements are possible by sharpening the CRS retention probability or the concentration arguments, so the true approximability might be a smaller constant than the one exhibited.","An immediate practical heuristic suggested by the analysis is to test the empirical approximation on real traffic or sports-betting data, where the product assumption is only approximate; graceful degradation would indicate robustness."],"forward_implications":["For uniform matroids, sorting by activation probability and trying prefixes gives a $\\Theta(1)$-approximation; the paper's example shows a disjoint-only strategy can be exponentially worse, achieving $O(\\log\\log k)$ where mixing achieves $\\Theta(\\log k/\\log\\log k)$.","For arbitrary matroids, the algorithm runs in time polynomial in the ground set and portfolio size, so it applies to implicit solution families like spanning trees where listing all solutions is impossible.","For general (non-product) distributions, no polynomial-time algorithm beats $(1-1/e+\\epsilon)$ unless P=NP, so the product-distribution assumption is essential.","Because the optimal value is submodular, the known greedy bound is $(1-1/e)$ but with running time polynomial in the number of solutions; the new result trades a constant-factor loss for polynomial dependence on the input description."],"supporting_citations":[{"why":"Supplies the basis-exchange bijections used to build the column decomposition and to map optimal solutions to copies of the next highest-expectation base.","marker":"[Bru69]"},{"why":"Introduces contention-resolution schemes, the framework the algorithm's trimming step is built on.","marker":"[CVZ11]"},{"why":"Provides the matroid-polytope fact used in the low-probability case: for a fractional vector in the matroid polytope, the expected rank of the sampled set is at least $(1-1/e)$ times its expected size.","marker":"[VCZ11]"},{"why":"Defines segmentation problems, the conceptual antecedent that this paper reformulates stochastically as portfolio optimization.","marker":"[KPR04]"},{"why":"Shows the objective is monotone submodular and gives the greedy $(1-1/e)$ baseline whose running time is polynomial in the size of the solution set.","marker":"[NWF78]"},{"why":"Supplies the max-k-cover inapproximability threshold used to prove that general distributions are hard to approximate within $(1-1/e+\\epsilon)$.","marker":"[Fei98]"}],"fun_headline_variants":["Best-of-k portfolios: constant-factor guarantee for matroids","Matroid solution portfolios: near-optimal best in polynomial time","Pick k diverse solutions, get near-best expected value","Constant-factor approximation for k-portfolio over matroids","Polynomial-time portfolios that hedge bets on the best solution"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument depends on the deferred-decisions claim that, after conditioning the sampling on events such as the winning solution $i^* = i'$ and the set of columns it hit, the conditional process still satisfies Definition 5.1 — that is, the scaled marginals stay in the matroid polytope and sampling an element does not raise its chance of being spanned by the other sampled elements.","fun_headline_variants_meta":{"raw":{"variants":["Best-of-k portfolios: constant-factor guarantee for matroids","Matroid solution portfolios: near-optimal best in polynomial time","Pick k diverse solutions, get near-best expected value","Constant-factor approximation for k-portfolio over matroids","Polynomial-time portfolios that hedge bets on the best solution"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000463,"raw_usage":{"total_tokens":2342,"prompt_tokens":998,"completion_tokens":1344,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":614,"completion_tokens_details":{"reasoning_tokens":1278}},"tokens_in":614,"tokens_out":1344,"duration_ms":10678,"temperature":1.0,"reasoning_tokens":1278,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T05:07:24.095981+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A direct numerical check would compute, on the smallest matroid where the column decomposition creates dependencies (for instance a graphic matroid on three elements with prefix length $d=2$), the conditional marginal vector and both sides of the negative-dependence inequality after conditioning on $i^*=i'$ and $C^*=C'$; if either condition of Definition 5.1 fails, Theorem 5.2's retention bound of $1/8$ cannot hold and the constant-factor claim collapses. Alternatively, simulate Algorithm 2 on random graphic matroids with adversarial probabilities and compare the empirical approximation ratio; a ratio tending to zero would disprove the theorem.","supporting_citations":[],"review_version":1}