Pith. sign in

REVIEW 6 minor 48 references

Polyhedral extended formulations that approximate the Gomory closure for packing problems

T0 review · 0 major / 6 minor · reviewed 2026-07-13 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Polynomial-size polyhedral extended formulations approximate any fixed iterate of the Gomory closure of packing polytopes within factor (1+ε)^t.

desk verdict 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. read the letter →

arxiv 2607.09222 v1 pith:NL4SWGCY submitted 2026-07-10 math.OC

Friedrich Eisenbrand , Samuel Fiorini , Lars Rohwedder , Jiaye Wei This is my paper · ORCID
classification math.OC MSC 90C1090C2790C57
keywords packingproblemsGomoryclosureextendedformulationsintegerprogrammingcuttingplaneshypergraphmatchingcommunicationcomplexityChvatalrank
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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).

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 6 minor

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).

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.

minor comments (6)
  1. 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.
  2. §2, paragraph after Lemma 5: “Danzig-Wolfe” should be “Dantzig-Wolfe”.
  3. 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.
  4. 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.
  5. 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.
  6. 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: pure first-principles existence proof via neighborhood-exact EFs and derivation-DAG distributions

full rationale

The paper constructs an explicit polyhedral extended formulation (Lemma 5) that is r-neighborhood-exact by enumerating the polynomially many 0/1 points supported on N(T) for |T|=r, then proves by induction on rank t (Lemma 6) that this Q (1+ε)^t-approximates P^{(t)}. The inductive step reduces low-RHS rank-t Gomory cuts to a coverage lower bound (Lemma 7) obtained from a carefully re-weighted random walk on the derivation DAG after heavy-node elimination (Section 3.3, Lemmas 8–10). Every object (N(T), forcing sets, path weights λ̃, coverage probability ε^t(1-ε)^{2t-1}-τ) is defined independently of the final approximation guarantee; the averaging argument is a direct probabilistic calculation, not a fit or a self-referential definition. The communication-complexity EF (Theorem 3, Lemma 11) likewise extends Yannakakis’ protocol by an explicit deterministic protocol whose complexity is O(δ_max log^{2} n). No parameters are fitted to data, no uniqueness theorem is imported from the authors’ prior work, and no intermediate quantity is renamed as a prediction of itself. The derivation is therefore self-contained against external benchmarks.

Assumptions & free parameters 3 free parameters · 3 assumptions · 2 invented entities

The paper works entirely inside standard polyhedral combinatorics and communication complexity. The only free choices are the approximation parameter ε and the rank t (both fixed by the user) and the technical thresholds au, au used to ignore tiny coefficients; these are set explicitly in terms of ε and t and are not fitted to data. No new physical or mathematical entities are postulated beyond ordinary combinatorial objects (neighborhoods, derivation DAGs, forcing sets).

free parameters (3)
  • ε (approximation factor)
    User-chosen fixed constant in (0,1/2); appears in all size and approximation statements.
  • t (Gomory rank)
    User-chosen fixed positive integer; controls both the target closure and the size exponent.
  • au (coefficient threshold) = ½ ε^t (1-ε)^{2t-1}
    Set to half of ε^t(1-ε)^{2t-1} to ignore tiny matrix entries; purely technical, not data-driven.
assumptions (3)
  • standard math Gomory cuts are valid for the integer hull and the Chvátal-Gomory procedure produces a finite hierarchy for rational polyhedra.
    Classical results of Gomory and Schrijver; invoked throughout Sections 1-3.
  • domain assumption Packing polytopes are downward-monotone: if x∈P and 0≤y≤x then y∈P.
    Used to discard negative coefficients and to apply the inductive Lemma 6.
  • standard math Yannakakis' theorem relating deterministic communication complexity of the slack matrix to the size of extended formulations.
    Invoked in Section 5 to turn the protocol of Lemma 11 into an extended formulation.
invented entities (2)
  • r-neighborhood-exact relaxation
    purpose: Polyhedral surrogate for the Decomposition Theorem that only needs to capture integer hulls on neighborhoods of r rows.
    Defined in Section 3.1; the whole approximation rests on this object.
  • derivation DAG with heavy-node elimination
    purpose: Models a rank-t Gomory cut so that a probability distribution over original rows can be extracted even when intermediate right-hand sides are large.
    Introduced in Section 3.3; the reweighting factor (1-ε) is crucial for Lemma 8.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Polyhedral extended formulations that approximate the Gomory closure for packing problems." pith.science (2026). https://pith.science/paper/NL4SWGCY

@misc{pith2026260709222,
  author       = {Pith},
  title        = {Pith review of: Polyhedral extended formulations that approximate the Gomory closure for packing problems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NL4SWGCY}},
  note         = {Machine review of arXiv:2607.09222}
}
abstract

We consider $0/1$ packing problems $\max\{c^T x \colon Ax \leq 1, \, x \in \{0,1\}^n\}$, with $A \in \mathbb{R}_{\geq 0}^{m \times n}$. A way to solve such problems is via tightening the linear programming relaxation $P$ with Gomory \emph{cutting-planes}. The Gomory-closure $P'$ of $P$ is the intersection of $P$ with all its cutting planes. The optimization problem over $P'$ is NP-hard. Mastrolilli (2020) has shown that for fixed ${\epsilon}>0$, the Lasserre hierarchy yields a polynomial-size convex but non-polyhedral extended formulation that approximates $P'$ up to a factor of $1+{\epsilon}$. Our main result is the construction of a polyhedral and polynomial extended formulation that approximates $P'$ with the same approximation guarantee. Our construction is based on first principles. Like Mastrolilli's approach, ours also applies to higher iterates $P^{(t)}$ for fixed $t$ and ${\epsilon}>0$. In contrast to an explicit construction, communication complexity provides an alternative way to describe extended formulations. Using this approach we obtain a quasi-polynomial polyhedral extended formulation for the above problem that is superior in some parameter regimes. To achieve this, we describe a communication protocol extending Yannakakis' protocol to decide whether the clique of Alice and the stable set of Bob intersect.

Figures

Figures reproduced from arXiv: 2607.09222 by the authors.

Figure 1
Figure 1. Elimination of a heavy node. Lemma 10. For all nodes v ∈ V˜ with d(v) ≤ 1, we have c˜ ∗ v = c ∗ v and for all nodes v ∈ V˜ with d(v) > 1, we have c˜ ∗ v ≥ (1 − 𝜀) d (v)−1 c ∗ v . Moreover, we have 𝛿˜ v = 𝛿v for all nodes v ∈ V˜ . Proof. The statement concerning nodes v ∈ V˜ with d(v) ≤ 1 is straightforward since no descendant of v in D got eliminated. Now let v ∈ V˜ have d(v) > 1. For every path 𝜋˜ in D˜ , we have a… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

48 extracted references

  1. [1]

    Extended formulations from communication protocols in output-efficient time

    Manuel Aprile and Yuri Faenza. “Extended formulations from communication protocols in output-efficient time”. In:Mathematical Programming (B) 183 (2020), pp. 41–59

    2020

  2. [2]

    A comprehensive analysis of polyhedral lift-and-project methods

    Yu Hin Au and Levent Tunçel. “A comprehensive analysis of polyhedral lift-and-project methods”. In:SIAM Journal on Discrete Mathematics 30.1 (2016), pp. 411–451

    2016

  3. [3]

    Mixed 0-1 programming by lift-and- project in a branch-and-cut framework

    Egon Balas, Sebastian Ceria, and Gérard Cornuéjols. “Mixed 0-1 programming by lift-and- project in a branch-and-cut framework”. In:Management Science42.9 (1996), pp. 1229–1246. 4Here and throughout the paper,log n denotes the base-2 logarithm of n. 18

    1996

  4. [4]

    No Small Linear Pro- gram Approximates Vertex Cover within a Factor2 − 𝜀

    Abbas Bazzi, Samuel Fiorini, Sebastian Pokutta, and Ola Svensson. “No Small Linear Pro- gram Approximates Vertex Cover within a Factor2 − 𝜀”. In:2015 IEEE 56th Annual Sympo- sium on Foundations of Computer Science. 2015, pp. 1123–1142

    2015

  5. [5]

    Approximate fixed-rank closures of covering prob- lems

    Daniel Bienstock and Mark Zuckerberg. “Approximate fixed-rank closures of covering prob- lems”. In:Mathematical Programming (2006)

    2006

  6. [6]

    On the Chvátal Rank of Polytopes in the 0/1 Cube

    Alexander Bockmayr, Friedrich Eisenbrand, Mark E. Hartmann, and Andreas S. Schulz. “On the Chvátal Rank of Polytopes in the 0/1 Cube”. In:Discrete Applied Mathematics 98 (1999), pp. 21–27

    1999

  7. [7]

    Primal separation and approximation for the 0,1/2- closure

    Lukas Brandl and Andreas S. Schulz. “Primal separation and approximation for the 0,1/2- closure”. In:Operations Research Letters 57 (2024), p. 107156

    2024

  8. [8]

    On linear and semidefinite programming relaxations for hypergraph matching

    Yuk Hei Chan and Lap Chi Lau. “On linear and semidefinite programming relaxations for hypergraph matching”. In:Mathematical Programming 135.1 (2012), pp. 123–148

    2012

Show all 48 references
  1. [9]

    Edmonds polytopes and a hierarchy of combinatorial problems

    Vašek Chvátal. “Edmonds polytopes and a hierarchy of combinatorial problems”. In:Discrete Mathematics 4 (1973), pp. 305–337

    1973

  2. [10]

    On Cutting-Plane Proofs in Combi- natorial Optimization

    Vašek Chvátal, William Cook, and Mark E. Hartmann. “On Cutting-Plane Proofs in Combi- natorial Optimization”. In:Linear Algebra and its Applications114/115 (1989), pp. 455–499

    1989

  3. [11]

    Integer Programming

    Michele Conforti, Gérard Cornuéjols, and Giacomo Zambelli. Integer Programming. Graduate Texts in Mathematics. Springer International Publishing, 2014

    2014

  4. [12]

    Cunningham, William R

    William Cook, William H. Cunningham, William R. Pulleyblank, and Alexander Schrijver. Combinatorial Optimization. John Wiley, 1998

    1998

  5. [13]

    On the rational polytopes with Chvátal rank 1

    Gérard Cornuéjols, Dabeen Lee, and Yanjun Li. “On the rational polytopes with Chvátal rank 1”. In:Mathematical Programming 179.1 (2020), pp. 21–46

    2020

  6. [14]

    When the Gomory–Chvátal closure coincides with the integer hull

    Gérard Cornuéjols and Yanjun Li. “When the Gomory–Chvátal closure coincides with the integer hull”. In:Operations Research Letters 46.2 (2018), pp. 251–256

    2018

  7. [15]

    Improved approximation for 3-dimensional matching via bounded pathwidth local search

    Marek Cygan. “Improved approximation for 3-dimensional matching via bounded pathwidth local search”. In:2013 IEEE 54th Annual Symposium on Foundations of Computer Science. IEEE. 2013, pp. 509–518

    2013

  8. [16]

    Decomposition principle for linear programs

    George B Dantzig and Philip Wolfe. “Decomposition principle for linear programs”. In:Op- erations research 8.1 (1960), pp. 101–111

    1960

  9. [17]

    Maximum matching and a polyhedron with 0,1-vertices

    Jack Edmonds. “Maximum matching and a polyhedron with 0,1-vertices”. In: Journal of Re- search of the National Bureau of Standards69 (1965), pp. 125–130

    1965

  10. [18]

    On the membership problem for the elementary closure of a polyhe- dron

    Friedrich Eisenbrand. “On the membership problem for the elementary closure of a polyhe- dron”. In:Combinatorica 19.2 (1999), pp. 297–300

    1999

  11. [19]

    Bounds on the Chvátal Rank of Polytopes in the 0/1-Cube

    Friedrich Eisenbrand and Andreas S. Schulz. “Bounds on the Chvátal Rank of Polytopes in the 0/1-Cube”. In:Combinatorica 23 (2003), pp. 245–261

    2003

  12. [20]

    Strengthening convex relaxations of 0/1- sets using Boolean formulas

    Samuel Fiorini, Tony Huynh, and Stefan Weltge. “Strengthening convex relaxations of 0/1- sets using Boolean formulas”. In:Math. Program. 190, 467–482 (2021)

    2021

  13. [21]

    Approximating the k-Set Packing Problem by Local Improve- ments

    Martin Fürer and Huiwen Yu. “Approximating the k-Set Packing Problem by Local Improve- ments”. In:Combinatorial Optimization: Third International Symposium, ISCO 2014, Lisbon, Por- tugal, March 5-7, 2014, Revised Selected Papers. Springer. 2014, p. 408

    2014

  14. [22]

    Faces of an integer polyhedron

    Ralph E. Gomory. “Faces of an integer polyhedron”. In: Proceedings of the National Academy of Sciences of the United States of America 57 (1967), pp. 16–18

    1967

  15. [23]

    Outline of an algorithm for integer solutions to linear programs

    Ralph E. Gomory. “Outline of an algorithm for integer solutions to linear programs”. In: Bulletin of the American Mathematical Society 64 (1958), pp. 275–278. 19

    1958

  16. [24]

    Randomized Communi- cation versus Partition Number

    Mika Göös, T. S. Jayram, Toniann Pitassi, and Thomas Watson. “Randomized Communi- cation versus Partition Number”. In:ACM Trans. Comput. Theory 10.1 (Jan. 2018)

    2018

  17. [25]

    Deterministic Communication vs. Par- tition Number

    Mika Göös, Toniann Pitassi, and Thomas Watson. “Deterministic Communication vs. Par- tition Number”. In: 2015 IEEE 56th Annual Symposium on Foundations of Computer Science . 2015, pp. 1077–1088

    2015

  18. [26]

    On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems

    Cor A. J. Hurkens and Alexander Schrijver. “On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems”. In: SIAM Journal on Discrete Mathematics 2.1 (1989), pp. 68–72

    1989

  19. [27]

    Integrality Gaps of Linear and Semi- Definite Programming Relaxations for Knapsack

    Anna R. Karlin, Claire Mathieu, and C. Thach Nguyen. “Integrality Gaps of Linear and Semi- Definite Programming Relaxations for Knapsack”. In: Integer Programming and Combinatoral Optimization. Ed. by Oktay Günlük and Gerhard J. Woeginger. Berlin, Heidelberg: Springer Berlin H...

    2011

  20. [28]

    Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs

    Pravesh K. Kothari, Raghu Meka, and Prasad Raghavendra. “Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs”. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing . STOC 2017. Montreal, Canada: Associatio...

    2017

  21. [29]

    An explicit exact SDP relaxation for nonlinear 0-1 programs

    Jean B. Lasserre. “An explicit exact SDP relaxation for nonlinear 0-1 programs”. In: Inte- ger programming and combinatorial optimization (Utrecht, 2001) . Vol. 2081. Lecture Notes in Comput. Sci. Berlin: Springer, 2001, pp. 293–303

    2001

  22. [30]

    A comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre re- laxations for 0-1 programming

    Monique Laurent. “A comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre re- laxations for 0-1 programming”. In:Mathematics of Operations Research28.3 (2003), pp. 470– 496

    2003

  23. [31]

    Asymptotically Optimal Hardness for k-set packing and k-Matroid Intersection

    Euiwoong Lee, Ola Svensson, and Theophile Thiery. “Asymptotically Optimal Hardness for k-set packing and k-Matroid Intersection”. In:Proceedings of the 57th Annual ACM Symposium on Theory of Computing. 2025, pp. 54–61

    2025

  24. [32]

    On the Shannon capacity of a graph

    László Lovász. “On the Shannon capacity of a graph”. In: IEEE Transactions on Information theory 25.1 (1979), pp. 1–7

    1979

  25. [33]

    Matrix cones, projection representations, and stable set polyhedra

    László Lovász and Alexander Schrijver. “Matrix cones, projection representations, and stable set polyhedra”. In:Polyhedral Combinatorics. Ed. by W. Cook and P. D. Seymour. DIMACS, 1990, pp. 1–17

    1990

  26. [34]

    High Degree Sum of Squares Proofs, Bienstock-Zuckerberg hierarchy and Chvátal-Gomory cuts

    Monaldo Mastrolilli. “High Degree Sum of Squares Proofs, Bienstock-Zuckerberg hierarchy and Chvátal-Gomory cuts”. In:SIAM Journal of Optimization (2020)

    2020

  27. [35]

    Sherali-Adams relaxations of the matching polytope

    Claire Mathieu and Alistair Sinclair. “Sherali-Adams relaxations of the matching polytope”. In: Proceedings of the forty-first annual ACM symposium on Theory of computing . 2009, pp. 293– 302

    2009

  28. [36]

    Nemhauser and Laurence A

    George L. Nemhauser and Laurence A. Wolsey. Integer and Combinatorial Optimization. John Wiley, 1988

    1988

  29. [37]

    Communication complexity: and applications

    Anup Rao and Amir Yehudayoff. Communication complexity: and applications. Cambridge Uni- versity Press, 2020

    2020

  30. [38]

    The matching polytope has exponential extension complexity

    Thomas Rothvoß. “The matching polytope has exponential extension complexity”. In: Jour- nal of the ACM (JACM) 64.6 (2017), pp. 1–19

    2017

  31. [39]

    0/1 polytopes with quadratic Chvátal rank

    Thomas Rothvoß and Laura Sanita. “0/1 polytopes with quadratic Chvátal rank”. In: Opera- tions Research 65.1 (2017), pp. 212–220

    2017

  32. [40]

    Combinatorial optimization

    Alexander Schrijver. Combinatorial optimization. Polyhedra and efficiency (3 volumes).Algorithms and Combinatorics 24. Berlin: Springer., 2003. 20

    2003

  33. [41]

    On cutting planes

    Alexander Schrijver. “On cutting planes”. In: Annals of Discrete Mathematics 9 (1980). Com- binatorics 79 (Proc. Colloq., Univ. Montréal, Montreal, Que., 1979), Part II, pp. 291–296

    1980

  34. [42]

    Theory of Linear and Integer Programming

    Alexander Schrijver. Theory of Linear and Integer Programming. John Wiley, 1986

    1986

  35. [43]

    A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems

    Hanif D Sherali and Warren P Adams. “A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems”. In:SIAM Journal on Discrete Mathematics 3.3 (1990), pp. 411–430

    1990

  36. [44]

    Improving Integrality Gaps via Chvátal-Gomory Round- ing

    Mohit Singh and Kunal Talwar. “Improving Integrality Gaps via Chvátal-Gomory Round- ing”. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Tech- niques. Ed. by Maria Serna, Ronen Shaltiel, Klaus Jansen, and José Rolim. Berlin, Heidelberg: Spring...

    2010

  37. [45]

    Lower bounds for approximating the matching polytope

    Makrand Sinha. “Lower bounds for approximating the matching polytope”. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms . SODA ’18. New Orleans, Louisiana: Society for Industrial and Applied Mathematics, 2018, pp. 1585–1604

    2018

  38. [46]

    Integer programming

    Laurence A Wolsey. Integer programming. John Wiley & Sons, 2020

    2020

  39. [47]

    Expressing combinatorial optimization problems by linear programs

    Mihalis Yannakakis. “Expressing combinatorial optimization problems by linear programs”. In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing . STOC ’88. Chicago, Illinois, USA: Association for Computing Machinery, 1988, pp. 223–228

    1988

  40. [48]

    Expressing combinatorial optimization problems by linear programs

    Mihalis Yannakakis. “Expressing combinatorial optimization problems by linear programs”. In: Journal of Computer and System Sciences43.3 (1991), pp. 441–466. A Approximation factor of Theorem 1 In Theorem 1, (1+𝜀)t is the target approximation factor. By taking𝜀 = (1+ ˜𝜀)1/t −1...

    1991

Pith tools

Reviewed July 13, 2026 · model on record in the stance chip above.