We experimentally evaluate the performance of several Max Cut approximation algorithms. In particular, we compare the results of the Goemans and Williamson algorithm using semidefinite programming with Trevisan’s algorithm using spectral partitioning. The former algorithm has a known .878 approximation guarantee whereas the latter has a .614 approximation guarantee. We investigate whether this gap in approximation guarantees is evident in practice or whether the spectral algorithm performs as well as the SDP. We also compare the performances to the standard greedy Max Cut algorithm which has a .5 approximation guarantee, two additional spectral algorithms, and a heuristic from Burer, Monteiro, and Zhang (BMZ). The algorithms are tested on Erdős–Renyi random graphs, complete graphs from TSPLIB, and real-world graphs from the Network Repository. We find, unsurprisingly, that the spectral algorithms provide a significant speed advantage over the SDP. In our experiments, the spectral algorithms and BMZ heuristic return cuts with values which are competitive with those of the SDP.

More from our Archive

• DOI: 10.3390/computation11070143 2023

  Mathematical Modelling of Tuberculosis Outbreak in an East African Country Incorporating Vaccination and Treatment

  Kayode Oshinubi, Olumuyiwa James Peter, Emmanuel Addai, Enock Mwizerwa, Oluwatosin Babasola, Ifeoma Veronica Nwabufo, Ibrahima Sane, Umar Muhammad Adam, Adejimi Adeniji, Janet O. Agbaje

• DOI: 10.3390/a16070337 2023

  A Hybrid Model for Analysis of Laser Beam Distortions Using Monte Carlo and Shack–Hartmann Techniques: Numerical Study and Experimental Results

  Ilya Galaktionov, Julia Sheldakova, Alexander Nikitin, Vladimir Toporovsky, Alexis Kudryashov

• DOI: 10.3390/a16070324 2023

  A Fast Surrogate Model-Based Algorithm Using Multilayer Perceptron Neural Networks for Microwave Circuit Design

  Mohammad (Behdad) Jamshidi, Salah I. Yahya, Saeed Roshani, Muhammad Akmal Chaudhary, Yazeed Yasin Ghadi, Sobhan Roshani

• DOI: 10.3390/computation11070126 2023

  Response Spectrum Analysis of Multi-Story Shear Buildings Using Machine Learning Techniques

  Manolis Georgioudakis, Vagelis Plevris

• DOI: 10.3390/a16070343 2023

  Deep Learning for Detecting Verticillium Fungus in Olive Trees: Using YOLO in UAV Imagery

  Marios Mamalis, Evangelos Kalampokis, Ilias Kalfas, Konstantinos Tarabanis

• DOI: 10.3390/a16070338 2023

  A Largely Unsupervised Domain-Independent Qualitative Data Extraction Approach for Empirical Agent-Based Model Development

  Rajiv Paudel, Arika Ligmann-Zielinska

• DOI: 10.3390/computation11070130 2023

  Applications of Modified Bessel Polynomials to Solve a Nonlinear Chaotic Fractional-Order System in the Financial Market: Domain-Splitting Collocation Techniques

  Mohammad Izadi, Hari Mohan Srivastava

• DOI: 10.3390/a16070325 2023

  Risk-Sensitive Policy with Distributional Reinforcement Learning

  Thibaut Théate, Damien Ernst

• DOI: 10.3390/computation11070129 2023

  Computation of the Exact Forms of Waves for a Set of Differential Equations Associated with the SEIR Model of Epidemics

  Nikolay K. Vitanov, Zlatinka I. Dimitrova

• DOI: 10.3390/computation11070127 2023

  Analytical and Numerical Results for the Diffusion-Reaction Equation When the Reaction Coefficient Depends on Simultaneously the Space and Time Coordinates

  Ali Habeeb Askar, Ádám Nagy, Imre Ferenc Barna, Endre Kovács