pith. sign in

arxiv: 2604.17661 · v1 · submitted 2026-04-19 · 🧮 math.OC · cs.DM

Maximum Cuts and Fractional Cut Covers: A Computational Study of a Randomized Semidefinite Programming Approach

Nathan Benedetto Proen\c{c}a , Marcel K. de Carli Silva , Cristiane M. Sato , Levent Tun\c{c}el This is my paper

Pith reviewed 2026-05-10 05:02 UTC · model grok-4.3

classification 🧮 math.OC cs.DM
keywords maximum cutfractional cut coversemidefinite programmingGoemans-Williamson algorithmrandomized roundingapproximation algorithmscomputational study
0
0 comments X

The pith

A randomized SDP method with hyperplane sampling simultaneously approximates max-cut and fractional cut covers to the 0.878 Goemans-Williamson ratio using far fewer samples than theory requires.

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

The paper tests a primal-dual framework that solves an SDP relaxation for either the max-cut problem or the weighted fractional cut-covering problem, then draws random cuts via the hyperplane method. It shows that practical implementations can certify approximate optimality for both problems at the Goemans-Williamson guarantee after only about 128 times the natural log of the number of edges. This marks the first reported computational study of the weighted fractional cut-covering problem and works reliably with standard SDP and LP solvers after careful perturbation of near-optimal solutions. The approach deviates from pure theory by substituting an LP solver for the fractional cover, yet still produces certifiably good results across tested instances.

Core claim

Through a unified experimental pipeline, the authors demonstrate that random-hyperplane rounding of SDP solutions, followed by LP-based certification of a fractional cut cover, reliably achieves the approximation ratio α_GW ≈ 0.878 for both the maximum-cut value and the weighted fractional cut-covering value on the same collection of cuts, after only ⌈128 ln m⌉ samples.

What carries the argument

Random-hyperplane rounding applied to SDP relaxations of max-cut, paired with LP computation of a fractional cut cover to produce simultaneous primal and dual certificates.

If this is right

  • For most tested instances the practical pipeline produces better certificates than the original theoretical rounding algorithm after the same number of samples.
  • Both first-order and second-order SDP solvers can be used when instances receive suitable pre-processing and numeric post-processing.
  • The method simultaneously yields a high-quality cut and a matching fractional cover that together certify the approximation ratio.
  • The observed sample complexity is substantially lower than existing theoretical bounds on the number of trials needed to reach the Goemans-Williamson guarantee.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Empirical evidence suggests that existing theoretical sample-complexity bounds for random-hyperplane rounding can be tightened for practical graph families.
  • The same perturbation-plus-LP-certification pattern may extend to other SDP-based approximation schemes that require dual certificates.
  • Numerical stability techniques developed here could be reused in other randomized rounding pipelines that suffer from floating-point drift.

Load-bearing premise

Replacing the theoretical algorithm for the fractional cut cover with a standard LP solver, together with suitable perturbation of near-optimal SDP solutions, still produces valid certificates that preserve the 0.878 guarantee.

What would settle it

A single graph instance on which, after exactly ⌈128 ln m⌉ random hyperplane samples, either the best cut found or the LP-computed fractional cover fails to certify a ratio of at least 0.878 relative to the SDP value.

Figures

Figures reproduced from arXiv: 2604.17661 by Cristiane M. Sato, Levent Tun\c{c}el, Marcel K. de Carli Silva, Nathan Benedetto Proen\c{c}a.

Figure 1
Figure 1. Figure 1: Pipeline The customization points are: • Solver receives as input an weighted graph, which it uses to approximately solve either (2) or (12). Different im￾plementations correspond to different solvers and optimization problems. • Scaler ensures that the weighted graph sent to Solver is normalized appropriately. After the SDP relax￾ation is solved, it scales back both the input (i.e., Weighted Graph) and th… view at source ↗
Figure 2
Figure 2. Figure 2: Running time breakdown of experiments with ε = 1/64 in [PITH_FULL_IMAGE:figures/full_fig_p021_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Running time breakdown of experiments with ε = 1/64 in [PITH_FULL_IMAGE:figures/full_fig_p022_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Number of samples F necessary to attain feasibility for (G, z) where G = K3, z12 = z13 = 1, and z23 = γ. For γ = 8−5 we failed to achieve feasibility after 2304 = 64 × ⌈32 ln m⌉ samples for all 10 independent runs. our certificates by a multiplicative factor of 1 − ε [5, Theorem 21]. To prove (35), we use two observations. The first one is that (36) A ⪯ B implies 1 4 L ∗ G(A) ≤ 1 4 L ∗ G(B) for every A, B … view at source ↗
Figure 5
Figure 5. Figure 5: Overview of A˜ and F˜. Each point represents an instance, with the average value of A˜ and F˜ defining its coordinates. In orange we have sparse instances, whereas in blue we have dense instances [PITH_FULL_IMAGE:figures/full_fig_p049_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Each of the 10 recorded values of A˜ and F˜ for a subset of the instances [PITH_FULL_IMAGE:figures/full_fig_p050_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Insteresting instances [PITH_FULL_IMAGE:figures/full_fig_p050_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Value of fcc(Ft , z) for email-univ across ⌈1024 ln m⌉ samples [PITH_FULL_IMAGE:figures/full_fig_p053_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Value of fcc(Ft , z) for inf-USAir97 across ⌈1024 ln m⌉ samples [PITH_FULL_IMAGE:figures/full_fig_p053_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Value of fcc(Ft , z) for johnson16-2-4 across ⌈2275 ln m⌉ samples [PITH_FULL_IMAGE:figures/full_fig_p054_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Value of fcc(Ft , z) for johnson16-2-4 across ⌈2275 ln m⌉ samples [PITH_FULL_IMAGE:figures/full_fig_p054_11.png] view at source ↗
read the original abstract

We present experimental work on a primal-dual framework simultaneously approximating maximum cut and weighted fractional cut-covering instances. In this primal-dual framework, we solve a semidefinite programming (SDP) relaxation to either the maximum cut problem or to the weighted fractional cut-covering problem, and then independently sample a collection of cuts via the random-hyperplane technique. We then simultaneously certify the approximate optimality of a cut and a fractional cut cover. We present several implementations which reliably achieve the celebrated Goemans and Williamson approximation ratio of $\alpha_{\mathrm{GW}} \approx 0.878$ for both optimization problems simultaneously, after $\lceil 128 \ln m \rceil$ samples, a number significantly smaller than the best theoretical bounds. This is the first experimental work approximating the weighted fractional cut-covering problem, and we deliver robust and repeatable results despite the use of randomized algorithms and floating-point arithmetic. Careful pre-processing of instances and post-processing of numeric results allow for good empirical outcomes with both first-order and second-order SDP solvers. Nearly optimal SDP solutions are suitably perturbed to ensure better probabilistic and numerical behavior. Our experiments deviate from theory by using a linear programming (LP) solver to compute fractional cut covers. For most instances studied, LP solving produces certifiably better results than the theoretical algorithm after $\lceil 128 \ln m \rceil$ samples. All our experiments strictly follow a unified pipeline which explicitly documents all parameters used in each run.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The paper presents a primal-dual computational framework that solves an SDP relaxation for either the max-cut or weighted fractional cut-cover problem, samples cuts via the random-hyperplane method, and uses the samples to simultaneously certify approximate optimality for both problems. It reports that several implementations reliably attain the Goemans-Williamson ratio α_GW ≈ 0.878 for both problems after ⌈128 ln m⌉ samples (smaller than known theoretical bounds), with the first experimental results on weighted fractional cut covers; the pipeline employs LP solvers for the covers, ad-hoc perturbations of near-optimal SDP vectors, and careful pre-/post-processing to handle randomization and floating-point arithmetic.

Significance. If the empirical claims hold under the stated deviations from theory, the work supplies the first reproducible computational evidence that the GW ratio can be realized jointly for max-cut and fractional cut cover with a modest, explicitly documented sampling budget. The unified pipeline, use of both first- and second-order SDP solvers, and explicit parameter logging constitute concrete strengths that could guide future practical implementations.

major comments (3)
  1. [Abstract and fractional cut cover section] Abstract and the section describing the fractional-cut-cover computation: the claim that the implementations achieve the α_GW guarantee for both problems simultaneously rests on replacing the theoretically analyzed construction of the fractional cover with an off-the-shelf LP solver; no re-derivation or bounding argument is supplied showing that the resulting LP certificate remains a valid dual whose value is still at most 1/α_GW times the SDP value.
  2. [SDP perturbations and sampling section] The section on SDP perturbations and random-hyperplane sampling: ad-hoc perturbations are applied to near-optimal SDP vectors before sampling, yet the manuscript provides no analysis confirming that these perturbations preserve the expectation of the cut indicator under the random-hyperplane distribution that underlies the original Goemans-Williamson 0.878 bound.
  3. [Results] Results tables and the paragraph asserting 'certifiably better results': the empirical observation that LP covers outperform the theoretical algorithm does not, by itself, establish that the joint α_GW ratio is attained, because the distributional assumptions linking the sampled cut value to the cover value have been altered by both the LP substitution and the perturbations.
minor comments (2)
  1. [Abstract] The abstract states that the number of samples is 'significantly smaller than the best theoretical bounds' but does not cite the specific theoretical bound being compared.
  2. [Methods] Notation for the weighted fractional cut cover and its LP formulation could be introduced with an explicit equation early in the methods section to improve readability.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the thorough review and valuable comments on our manuscript. We address each of the major comments below, clarifying the empirical focus of our work and outlining the revisions we will make to better distinguish between theoretical guarantees and computational observations.

read point-by-point responses

  1. Referee: [Abstract and fractional cut cover section] Abstract and the section describing the fractional-cut-cover computation: the claim that the implementations achieve the α_GW guarantee for both problems simultaneously rests on replacing the theoretically analyzed construction of the fractional cover with an off-the-shelf LP solver; no re-derivation or bounding argument is supplied showing that the resulting LP certificate remains a valid dual whose value is still at most 1/α_GW times the SDP value.

    Authors: We agree that our approach deviates from the theoretical analysis by employing an LP solver for the fractional cut cover. The LP yields a feasible dual certificate, and our experiments demonstrate that the ratio of the sampled cut value to this cover value consistently meets or exceeds α_GW. However, we do not provide a theoretical bounding argument for this specific substitution. In the revised manuscript, we will update the abstract and the fractional cut cover section to emphasize that the simultaneous achievement is an empirical observation supported by the computational results, rather than a proven theoretical guarantee. revision: yes

  2. Referee: [SDP perturbations and sampling section] The section on SDP perturbations and random-hyperplane sampling: ad-hoc perturbations are applied to near-optimal SDP vectors before sampling, yet the manuscript provides no analysis confirming that these perturbations preserve the expectation of the cut indicator under the random-hyperplane distribution that underlies the original Goemans-Williamson 0.878 bound.

    Authors: The perturbations are small adjustments made to improve numerical stability and avoid issues with floating-point precision in the sampling process, as detailed in the manuscript. While we lack a formal analysis proving exact preservation of the cut expectation, the perturbations are minimal and our results across numerous instances show approximation ratios aligning with the Goemans-Williamson bound. We will revise the section to include a discussion of the heuristic rationale for perturbations and note that they do not appear to degrade the observed performance. revision: partial

  3. Referee: [Results] Results tables and the paragraph asserting 'certifiably better results': the empirical observation that LP covers outperform the theoretical algorithm does not, by itself, establish that the joint α_GW ratio is attained, because the distributional assumptions linking the sampled cut value to the cover value have been altered by both the LP substitution and the perturbations.

    Authors: We concur that the alterations mean our results are empirical demonstrations rather than a strict certification under the original theoretical assumptions. The paragraph will be revised to state that the LP-based covers provide certifiably better or equivalent results in our experiments, with the joint ratio observed empirically after the specified number of samples. Additional details on the computation of the ratios will be added to strengthen the presentation of the evidence. revision: yes

Circularity Check

0 steps flagged

No circularity: experimental results rely on external GW SDP and independent runs

full rationale

The paper is a computational study that runs established SDP relaxations (Goemans-Williamson) followed by random-hyperplane sampling and reports observed approximation ratios on concrete instances. It explicitly notes deviations (LP solver for the cover, ad-hoc perturbations) and presents the outcomes as empirical performance after a fixed sample budget, not as a re-derived theoretical guarantee. No equation or claim reduces a result to a fitted parameter, self-definition, or load-bearing self-citation; the central observations are produced by executing the pipeline on test data and are therefore independent of the paper's own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the correctness of the Goemans-Williamson SDP relaxation and random-hyperplane rounding, plus the assumption that LP-based covers remain valid certificates when substituted for the theoretical algorithm.

axioms (1)
  • domain assumption The Goemans-Williamson SDP relaxation yields an α_GW-approximate solution whose random hyperplane rounding preserves the 0.878 guarantee in expectation.
    Invoked throughout as the foundation for both the primal cuts and the simultaneous dual certification.

pith-pipeline@v0.9.0 · 5590 in / 1387 out tokens · 70259 ms · 2026-05-10T05:02:01.903272+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

47 extracted references · 47 canonical work pages

  1. [1]

    Global approaches for facility layout and VLSI floorplanning

    M. F. Anjos and F. Liers. “Global approaches for facility layout and VLSI floorplanning”. In: Handbook on semidefinite, conic and polynomial optimization. Volume 166. Internat. Ser. Oper. Res. Management Sci. Springer, New York, 2012, pages 849–877

    work page 2012

  2. [2]

    Beyond product state approximations for a quantum analogue of max cut

    A. Anshu, D. Gosset, and K. Morenz. “Beyond product state approximations for a quantum analogue of max cut”. In:15th Conference on the Theory of Quantum Computation, Commu- nication and Cryptography. Volume 158. LIPIcs. Leibniz Int. Proc. Inform. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2020, Art. No. 7, 15

    work page 2020

  3. [3]

    Experiments in quadratic0-1 programming

    F. Barahona, M. Jünger, and G. Reinelt. “Experiments in quadratic0-1 programming”. In: Math. Programming44.2 (1989), pages 127–137

    work page 1989

  4. [4]

    On the computational complexity of Ising spin glass models

    F. Barahona. “On the computational complexity of Ising spin glass models”. In:J. Phys. A 15.10 (1982), pages 3241–3253

    work page 1982

  5. [5]

    A Primal-Dual Extension of the Goemans–Williamson Algorithm for the Weighted Fractional Cut-Covering Problem

    N. Benedetto Proença, M. K. de Carli Silva, C. M. Sato, and L. Tunçel. “A Primal-Dual Extension of the Goemans–Williamson Algorithm for the Weighted Fractional Cut-Covering Problem”. In:Mathematical Programming(April 23, 2025)

    work page 2025

  6. [6]

    Benedetto Proença, M

    N. Benedetto Proença, M. K. de Carli Silva, C. M. Sato, and L. Tunçel.Generalized Cuts and Grothendieck Covers: a Primal-Dual Approximation Framework Extending the Goemans– Williamson Algorithm. June 26, 2024. arXiv:2406.18670 [cd.DS]

    work page arXiv 2024

  7. [7]

    L. Blum, F. Cucker, M. Shub, and S. Smale.Complexity and Real Computation. New York, NY: Springer, 1998. xvi+453 pages

    work page 1998

  8. [8]

    Lifting and separation procedures for the cut polytope

    T. Bonato, M. Jünger, G. Reinelt, and G. Rinaldi. “Lifting and separation procedures for the cut polytope”. In:Math. Program.146.1-2 (2014), pages 351–378

    work page 2014

  9. [9]

    Proof of the Goldberg-Seymour conjecture on edge-colorings of multigraphs

    G. Chen, G. Jing, and W. Zang. “Proof of the Goldberg-Seymour conjecture on edge-colorings of multigraphs”. In:J. Comb. Optim.50.3 (2025), Paper No. 23, 91

    work page 2025

  10. [10]

    A linear programming and rounding approach to max 2-sat

    J. Cheriyan, W. H. Cunningham, L. Tunçel, and Y. Wang. “A linear programming and rounding approach to max 2-sat”. In:Cliques, coloring, and satisfiability (New Brunswick, NJ, 1993). Volume 26. DIMACS Ser. Discrete Math. Theoret. Comput. Sci. Amer. Math. Soc., Providence, RI, 1996, pages 395–414

    work page 1993

  11. [11]

    An improved lower bound for the number of edges in a largest bipartite subgraph

    C. S. Edwards. “An improved lower bound for the number of edges in a largest bipartite subgraph”. In:Recent advances in graph theory (Proc. Second Czechoslovak Sympos., Prague, 1974). Academia, Prague, 1975, pages 167–181

    work page 1974

  12. [12]

    On some extremal problems in graph theory

    P. Erdős. “On some extremal problems in graph theory”. In:Israel J. Math.3 (1965), pages 113– 116

    work page 1965

  13. [13]

    Anti-blocking polyhedra

    D. R. Fulkerson. “Anti-blocking polyhedra”. In:J. Combinatorial Theory Ser. B12 (1972), pages 50–71

    work page 1972

  14. [14]

    Blocking and anti-blocking pairs of polyhedra

    D. R. Fulkerson. “Blocking and anti-blocking pairs of polyhedra”. In:Math. Programming1 (1971), pages 168–194

    work page 1971

  15. [15]

    Almost optimal classical approximation algorithms for a quantum generalization of Max-Cut

    S. Gharibian and O. Parekh. “Almost optimal classical approximation algorithms for a quantum generalization of Max-Cut”. In:Approximation, randomization, and combinatorial optimization. Algorithms and techniques. Volume 145. LIPIcs. Leibniz Int. Proc. Inform. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2019, Art. No. 31, 17

    work page 2019

  16. [16]

    Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

    M. X. Goemans and D. P. Williamson. “Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming”. In:J. ACM 42.6 (1995), pages 1115–1145

    work page 1995

  17. [17]

    The ellipsoid method and its consequences in combinatorial optimization

    M. Grötschel, L. Lovász, and A. Schrijver. “The ellipsoid method and its consequences in combinatorial optimization”. In:Combinatorica 1.2 (1981), pages 169–197

    work page 1981

  18. [18]

    The biparticity of a graph

    F. Harary, D. Hsu, and Z. Miller. “The biparticity of a graph”. In:J. Graph Theory1.2 (1977), pages 131–133. REFERENCES 57

    work page 1977

  19. [19]

    Solving quadratic(0, 1)-problems by semidefinite programs and cutting planes

    C. Helmberg and F. Rendl. “Solving quadratic(0, 1)-problems by semidefinite programs and cutting planes”. In:Math. Programming82.3 (1998), pages 291–315

    work page 1998

  20. [20]

    A note on the minimum cut cover of graphs

    T. Y. Ho and L. H. Hsu. “A note on the minimum cut cover of graphs”. In:Oper. Res. Lett. 15.4 (1994), pages 193–194

    work page 1994

  21. [21]

    D. S. Johnson and M. A. Trick, editors.Cliques, coloring, and satisfiability. Volume 26. DIMACS Series in Discrete Mathematics and Theoretical Computer Science. Papers from the workshop held as part of the 2nd DIMACS Implementation Challenge in New Brunswick, NJ, October 11–13, 1993. American Mathematical Society, Providence, RI, 1996, pages xii+657

    work page 1993

  22. [22]

    Efficient implementation of interior-point methods for quantum relative entropy

    M. Karimi and L. Tunçel. “Efficient implementation of interior-point methods for quantum relative entropy”. In:INFORMS J. Comput.37.1 (2025), pages 3–21

    work page 2025

  23. [23]

    Reducibility among combinatorial problems

    R. M. Karp. “Reducibility among combinatorial problems”. In:Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972). Plenum, New York, 1972, pages 85–103

    work page 1972

  24. [24]

    Fractional coloring with local demands and applications to degree- sequence bounds on the independence number

    T. Kelly and L. Postle. “Fractional coloring with local demands and applications to degree- sequence bounds on the independence number”. In:Journal of Combinatorial Theory, Series B 169 (2024), pages 298–337

    work page 2024

  25. [25]

    Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?

    S. Khot, G. Kindler, E. Mossel, and R. O’Donnell. “Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?” In:SIAM J. Comput.37.1 (2007), pages 319–357

    work page 2007

  26. [26]

    The unique games conjecture, integrability gap for cut problems and embeddability of negative-type metrics intoℓ1

    S. A. Khot and N. K. Vishnoi. “The unique games conjecture, integrability gap for cut problems and embeddability of negative-type metrics intoℓ1”. In:J. ACM 62.1 (2015), Art. 8, 39

    work page 2015

  27. [27]

    BiqCrunch: a semidefinite branch-and-bound method for solving binary quadratic problems

    N. Krislock, J. Malick, and F. Roupin. “BiqCrunch: a semidefinite branch-and-bound method for solving binary quadratic problems”. In:ACM Trans. Math. Software43.4 (2017), Art. 32, 23

    work page 2017

  28. [28]

    Minimal cut cover of a graph with an application to the testing of electronic boards

    R. Loulou. “Minimal cut cover of a graph with an application to the testing of electronic boards”. In:Oper. Res. Lett.12.5 (1992), pages 301–305

    work page 1992

  29. [29]

    k-components, clusters and slicings in graphs

    D. W. Matula. “k-components, clusters and slicings in graphs”. In:SIAM J. Appl. Math.22 (1972), pages 459–480

    work page 1972

  30. [30]

    An experimental evaluation of semidefinite programming and spectral algorithms for max cut

    R. Mirka and D. P. Williamson. “An experimental evaluation of semidefinite programming and spectral algorithms for max cut”. In:ACM J. Exp. Algorithmics28 (2023), Art. 2.1, 18

    work page 2023

  31. [31]

    Semidefinite relaxation and nonconvex quadratic optimization

    Y. Nesterov. “Semidefinite relaxation and nonconvex quadratic optimization”. In:Optim. Methods Softw.9.1-3 (1998), pages 141–160

    work page 1998

  32. [32]

    On fractional cut covers

    J. Neto and W. Ben-Ameur. “On fractional cut covers”. In:Discrete Appl. Math.265 (2019), pages 168–181

    work page 2019

  33. [33]

    Matrix Market

    NIST. Matrix Market. https://math.nist.gov/MatrixMarket/

    work page

  34. [34]

    Conic Optimization via Operator Splitting and Homogeneous Self-Dual Embedding

    B. O’Donoghue, E. Chu, N. Parikh, and S. Boyd. “Conic Optimization via Operator Splitting and Homogeneous Self-Dual Embedding”. In:Journal of Optimization Theory and Applications 169.3 (June 2016), pages 1042–1068

    work page 2016

  35. [35]

    O’Donoghue, E

    B. O’Donoghue, E. Chu, N. Parikh, and S. Boyd.SCS: Splitting Conic Solver, version 3.2.7. https://github.com/cvxgrp/scs. August 2024

    work page 2024

  36. [36]

    Parallel branch and bound algorithms for quadratic zero-one programs on the hypercube architecture

    P. M. Pardalos and G. P. Rodgers. “Parallel branch and bound algorithms for quadratic zero-one programs on the hypercube architecture”. In: volume 22. 1-4. Supercomputers and large-scale optimization: algorithms, software, applications (Minneapolis, MN, 1988). 1990, pages 271–292

    work page 1988

  37. [37]

    Solving the max-cut problem using eigenvalues

    S. Poljak and F. Rendl. “Solving the max-cut problem using eigenvalues”. In: volume 62. 1-3. Partitioning and decomposition in combinatorial optimization. 1995, pages 249–278

    work page 1995

  38. [38]

    A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound

    S. Poljak and D. Turzík. “A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound”. In:Discrete Math.58.1 (1986), pages 99–104

    work page 1986

  39. [39]

    Maximum bipartite subgraphs of Kneser graphs

    S. Poljak and Z. Tuza. “Maximum bipartite subgraphs of Kneser graphs”. In:Graphs Combin. 3.2 (1987), pages 191–199

    work page 1987

  40. [40]

    G. Reinelt. TSPLIB95. http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/. 58 REFERENCES

    work page

  41. [41]

    Solving max-cut to optimality by intersecting semidefi- nite and polyhedral relaxations

    F. Rendl, G. Rinaldi, and A. Wiegele. “Solving max-cut to optimality by intersecting semidefi- nite and polyhedral relaxations”. In:Math. Program.121.2 (2010), pages 307–335

    work page 2010

  42. [42]

    Cubical coloring—fractional covering by cuts and semidefinite programming

    R. Šámal. “Cubical coloring—fractional covering by cuts and semidefinite programming”. In: Discrete Math. Theor. Comput. Sci.17.2 (2015), pages 251–266

    work page 2015

  43. [43]

    Armadillo: an Efficient Framework for Numerical Linear Algebra

    C. Sanderson and R. Curtin. “Armadillo: an Efficient Framework for Numerical Linear Algebra”. In: 2025 17th International Conference on Computer and Automation Engineering (ICCAE). 2025, pages 303–307

    work page 2025

  44. [44]

    E. R. Scheinerman and D. H. Ullman.Fractional graph theory. Dover Publications, Inc., Mineola, NY, 2011. xviii+211 pages

    work page 2011

  45. [45]

    Schrijver.Theory of linear and integer programming

    A. Schrijver.Theory of linear and integer programming. Wiley-Interscience Series in Discrete Mathematics. A Wiley-Interscience Publication. John Wiley & Sons, Ltd., Chichester, 1986, pages xii+471

    work page 1986

  46. [46]

    O. Tange. GNU Parallel 20221122. November 2022

    work page 2022

  47. [47]

    AnO(√nL)-iteration homogeneous and self-dual linear programming algorithm

    Y. Ye, M. J. Todd, and S. Mizuno. “AnO(√nL)-iteration homogeneous and self-dual linear programming algorithm”. In:Math. Oper. Res.19.1 (1994), pages 53–67. Appendix A. Using the Software A.1. Basic Dependencies. Before compiling our code, you need to install its dependencies. Our core dependencies are: git, pkg-config, Boost, CMake, BLAS and LAPACK. On Ub...

    work page 1994