{"id":"2dea3cdc-8c4f-436d-9926-7f1b0b2d60c4","arxiv_id":"2607.09222","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":3,"one_line_summary":"Polynomial-size polyhedral extended formulations approximate the t-th Gomory closure of packing polytopes to factor (1+ε)^t, with a quasi-polynomial alternative via communication protocols.","lead":"The paper builds polynomial-size polyhedral extended formulations that approximate the Gomory closure of packing LPs to within 1+ε, matching prior non-polyhedral SDP results but using only linear programming. This gives a practical, first-principles alternative for tightening integer packing relaxations and improves the number of Gomory rounds needed for hypergraph matching.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The reader correctly isolates the probabilistic averaging + heavy-node reweighting as the most intricate part of the argument. That part, however, is fully spelled out (Lemmas 8–10, explicit probability calculation in 3.4) and survives direct verification: the (1-ε) loss per elimination is accounted for, the floor-free fractional inequalities remain valid conic combinations of the original rows, and the final \tau-subtraction is elementary. All other ingredients (neighborhood-exact EF of size (nm)^{(1/ε)^{O(t)}}, inductive reduction via Lemma 6, communication-protocol EF) are standard and free of hidden assumptions. Consequently the high-confidence ACCEPT verdict stands; no adjustment is warranted.","tokens_in":21530,"tokens_out":558,"duration_ms":35702,"concrete_test":"Construct an explicit rank-2 derivation DAG containing one heavy intermediate node with δ_v = ⌊1/ε⌋, apply the elimination rule of Section 3.3, recompute the adjusted multipliers and the resulting ˜c^* vector, and verify numerically that ˜c^* ≥ (1-ε) c^* holds componentwise for a concrete packing matrix of size 5\times10; if the inequality fails for any coordinate the coverage lower bound of Lemma 8 collapses.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (Theorem 1) rests on the existence of an r-neighborhood-exact polyhedral EF (Lemma 5) together with a carefully constructed row distribution that makes every low-RHS rank-t Gomory cut valid up to factor 1+ε after averaging (Lemmas 7–8). The only delicate step is the heavy-node elimination inside the derivation DAG (Section 3.3) and the subsequent lower bound on path weights (Lemma 10 and the calculation in 3.4). Upon close inspection the re-weighting factor is at least 1-ε per eliminated node, the fractional coefficients satisfy ˜c^* ≥ (1-ε)^{d(v)-1} c^*, the random-walk probabilities remain a valid distribution, and the final coverage probability is at least ε^t (1-ε)^{2t-1}-τ as claimed. No algebraic gap, missing case, or circularity appears.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper constructs polyhedral extended formulations that (1+ε)^t-approximate the t-th Gomory closure P^{(t)} of a packing polytope P={x≥0:Ax≤1}⊆[0,1]^n. Theorem 1 gives an explicit linear EF of size (nm)^{(1/ε)^{O(t)}} via r-neighborhood-exact relaxations (Lemmas 4–5) obtained by enumerating integer hulls on neighborhoods N(T) of r rows, combined with an inductive reduction to low-RHS cuts (Lemma 6) and a probabilistic averaging argument that relies on a carefully reweighted row distribution extracted from a derivation DAG after heavy-node elimination (Lemmas 7–10, §3.3–3.4). Theorem 2 shows that O(log k) Gomory rounds already reduce the integrality gap of the standard LP for k-uniform hypergraph matching to (k+1)/2. Theorem 3 supplies a quasi-polynomial EF of size m+n^{(2/ε)·log n} via a deterministic communication protocol that generalizes Yannakakis’ clique-vs-stable-set protocol to packing polytopes and bounded RHS (Lemma 11).","tokens_in":21773,"tokens_out":966,"duration_ms":22614,"significance":"If correct, the result is a genuine advance: it replaces Mastrolilli’s non-polyhedral Lasserre/SoS construction by a purely polyhedral, first-principles LP extended formulation of comparable size, while remaining optimal for t=1 by the Rothvoss–Sinha lower bounds on approximate matching. The hypergraph-matching rank bound (Theorem 2) substantially improves the previous O(k^{2}) of Singh–Talwar. The communication-complexity formulation (Theorem 3) yields a clean trade-off when m≫n and extends a classical protocol in a non-trivial way. The proofs are self-contained, free of fitted parameters, and the constructions (neighborhood-exact EFs, heavy-node elimination) are reusable. These strengths make the paper a solid contribution to polyhedral combinatorics and extended formulations.","major_comments":[],"minor_comments":[{"comment":"Throughout the overview and §2 the name is inconsistently spelled “Mastrollili” (missing “i”) versus the correct “Mastrolilli” used in the abstract and references; please standardize.","section":null},{"comment":"§2, paragraph after Lemma 5: “Danzig-Wolfe” should be “Dantzig-Wolfe”.","section":null},{"comment":"Lemma 5 claims size O(m^r n^{1+r/τ}); the subsequent display writes O(n m^r (n choose r/τ)). The two expressions are equivalent up to polynomial factors, but a single consistent bound would improve readability.","section":null},{"comment":"Figure 1 caption and surrounding text: the elimination process is clear, yet a short remark that the order of elimination does not affect the final lower bound on path weights (used in Lemma 10) would remove any residual ambiguity.","section":null},{"comment":"Theorem 3 and Remark 4: the quasi-polynomial EF is existential (via communication complexity). A one-sentence pointer that the protocol itself is constructive would clarify the algorithmic status.","section":null},{"comment":"Appendix A: the translation from (1+ε)^t to a pure (1+ε̃) factor is correct but the O(ε^{2}) remainder is left implicit; writing the exact substitution ε=(1+ε̃)^{1/t}-1 would make the size bound fully explicit.","section":null}],"recommendation":"minor_revision","confidential_remarks":"The manuscript is technically solid and the reader/skeptic assessments align with my own reading: the heavy-node reweighting is the only delicate step and it checks out. Fit for a top discrete-optimization or combinatorial-optimization journal is excellent. No novelty or citation concerns."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This paper gives the first polyhedral extended formulation that approximates the t-th Gomory closure of a packing polytope to factor (1+ε)^t with size (nm)^(1/ε)^O(t). That is the real advance: Mastrolilli already had the same guarantee via Lasserre, but the construction here is pure LP, built from neighborhood-exact relaxations and a carefully re-weighted sampling distribution over rows after heavy-node elimination in the derivation DAG.\n\nWhat works well is the modular structure. Lemmas 4–5 produce an r-neighborhood-exact polyhedron of the claimed size by enumerating integer points on the neighborhoods of r rows. Lemma 6 reduces the induction to low-RHS cuts. The probabilistic averaging (Lemma 7) plus the DAG reweighting (Lemmas 8–10) then show those cuts survive up to 1+ε. The heavy-node elimination loses only a (1-ε) factor per eliminated node and the final coverage probability is exactly as claimed; the stress-test found no algebraic gap and I agree. The hypergraph-matching result (Theorem 2) is a clean improvement from O(k^{2}) to O(log k) rounds, and the communication-protocol EF (Theorem 3) is a nice extension of Yannakakis that is superior when m ≫ n.\n\nSoft spots are minor and already flagged by the authors. The main construction is exponential in 1/ε and t, so it is theoretical rather than practical for large rank. Theorem 3 is non-constructive. The free parameters \tau and r are chosen cleanly and do not hide circularity. Citations are accurate and the proofs are self-contained.\n\nThis is for people who care about extended formulations, cutting-plane hierarchies, or packing polytopes. It deserves a serious referee. I would accept it for peer review without hesitation and would cite the polyhedral construction and the matching-rank bound myself.","headline":"Clean polyhedral replacement for Mastrolilli's SDP approximation of the Gomory closure, plus a useful O(log k) rank bound and a quasi-poly communication EF.","tokens_in":22372,"tokens_out":523,"would_cite":true,"duration_ms":7146,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C10","90C27","90C57"],"pacs":[],"model":"grok-4.5","headline":"Polynomial-size polyhedral extended formulations approximate any fixed iterate of the Gomory closure of packing polytopes within factor (1+ε)^t.","keywords":["packing problems","Gomory closure","extended formulations","integer programming","cutting planes","hypergraph matching","communication complexity","Chvatal rank"],"falsifier":"Exhibit a concrete packing polytope, a fixed ε and t, and a point that lies in every r-neighborhood-exact relaxation of the claimed size yet violates some rank-t Gomory cut by more than the factor (1+ε)^t.","tokens_in":22448,"feed_emoji":"📦","tokens_out":1030,"duration_ms":43382,"temperature":0.7,"pith_summary":"Packing integer programs can be tightened by adding all Gomory cutting planes, but optimizing over the resulting Gomory closure is NP-hard. The paper constructs an explicit polyhedral extended formulation of size (nm) raised to (1/ε) to the power O(t) that approximates the t-th Gomory closure within (1+ε)^t for any fixed accuracy ε and rank t. The construction uses only linear programming: it enforces the exact integer hull on every small neighborhood of rows and averages the resulting local inequalities against a probability distribution read off the derivation of each cut. The same guarantee was previously known only via non-polyhedral semidefinite hierarchies. A second, communication-complexity argument yields a quasi-polynomial formulation that can be smaller when the number of inequalities is large, and the method also improves the number of Gomory rounds needed for hypergraph matching.","feed_headline":"Polynomial LPs approximate packing Gomory closures","feed_subtitle":"First-principles polyhedral formulations match the power of non-polyhedral hierarchies for fixed accuracy and rank","key_machinery":"The r-neighborhood-exact relaxation: a downward-monotone polyhedron whose projection onto the variables neighboring any r rows lies inside the integer hull of those variables. It is realized by an extended formulation that convex-combines all feasible 0-1 points supported in each such neighborhood; a carefully re-weighted distribution over rows extracted from the (heavy-node-eliminated) derivation DAG of a low-right-hand-side Gomory cut then makes every such cut approximately valid by probabilistic averaging.","core_discovery":"For every packing polytope P = {x ≥ 0 : Ax ≤ 1} and every fixed ε ∈ (0,1/2) and t ≥ 1 there exists a polyhedral relaxation Q of the integer hull of P that is a (1+ε)^t-approximation of the t-th Gomory closure P^(t) and admits a linear extended formulation of size (nm)^(1/ε)^O(t).","pith_inferences":["Local polyhedral descriptions of neighborhoods appear sufficient to capture the strength of Gomory cuts for packing, suggesting that semidefinite hierarchies may be replaceable by pure LP for this class.","The same neighborhood-exact idea may extend to other cutting-plane operators whose derivations admit a DAG representation with bounded right-hand sides.","The communication protocol generalizes Yannakakis' clique-stable-set protocol and could yield quasi-polynomial formulations for other packing-type integer hulls with bounded right-hand-side inequalities."],"forward_implications":["For any fixed accuracy and rank, approximate optimization over the Gomory closure of a packing IP reduces to ordinary linear programming of polynomial size.","O(log k) rounds of Gomory cutting planes already bring the integrality gap of k-uniform hypergraph matching down to (k+1)/2.","When the number of inequalities m is much larger than n, a communication protocol yields a quasi-polynomial extended formulation of size m + n^O((1/ε) log n) that still approximates every iterate.","The same inductive averaging works for covering problems, recovering polynomial extended formulations for their fixed-rank Gomory closures."],"fun_headline_variants":["Polyhedral extended formulations approximate packing Gomory closures","Polynomial polyhedra match Lasserre for packing Gomory closures","First-principles polyhedral EFs approximate packing Gomory","Quasi-polynomial polyhedral EFs for packing Gomory via communication","Polynomial LPs approximate t-th Gomory closures in packing"],"cache_read_input_tokens":16512,"weakest_assumption_plain":"The averaging argument that any r-neighborhood-exact relaxation automatically satisfies every low-right-hand-side Gomory cut up to factor 1+ε once a suitable distribution is taken from the cut's derivation after heavy intermediate nodes are removed.","fun_headline_variants_meta":{"raw":{"variants":["Polyhedral extended formulations approximate packing Gomory closures","Polynomial polyhedra match Lasserre for packing Gomory closures","First-principles polyhedral EFs approximate packing Gomory","Quasi-polynomial polyhedral EFs for packing Gomory via communication","Polynomial LPs approximate t-th Gomory closures in packing"]},"model":"grok-4.5","effort":"low","cost_usd":0.00567,"raw_usage":{"total_tokens":1539,"prompt_tokens":843,"num_sources_used":0,"completion_tokens":86,"cost_in_usd_ticks":56700000,"prompt_tokens_details":{"text_tokens":843,"audio_tokens":0,"image_tokens":0,"cached_tokens":128},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":610,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":843,"tokens_out":86,"duration_ms":7215,"temperature":1.0,"reasoning_tokens":610,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-13T04:34:30.354610+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Exhibit a concrete packing polytope, a fixed ε and t, and a point that lies in every r-neighborhood-exact relaxation of the claimed size yet violates some rank-t Gomory cut by more than the factor (1+ε)^t.","supporting_citations":[],"review_version":1}