Approximating maximum cut on interval graphs and split graphs beyond Goemans-Williamson

DOI10.4230/LIPICS.APPROX/RANDOM.2025.20MaRDI QIDQ7346848zbMATH OpenFDO

Authors Jung-Ho Ahn, Ian DeHaan, Eun Jung Kim, Euiwoong Lee

Publication date 11 September 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.APPROX/RANDOM.2025.20

Mathematics Subject Classification ID

Randomized algorithms (68W20) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Cites work

• Complexity of maximum cut on interval graphs
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• Graph expansion and the unique games conjecture
• Graph theory for systems biology: interval graphs, motifs, and pattern recognition
• scientific article; zbMATH DE number 5764850 (Why is no real title available?)
• scientific article; zbMATH DE number 1496855 (Why is no real title available?)
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• List homomorphisms to reflexive graphs
• MAX-CUT has a randomized approximation scheme in dense graphs
• Maximum cut on interval graphs of interval count four is NP-complete
• Maximum cut on line and total graphs
• Non-approximability results for optimization problems on bounded degree instances
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Reducibility among combinatorial problems

This page was built for publication: Approximating maximum cut on interval graphs and split graphs beyond Goemans-Williamson

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7346848)