Learning-augmented streaming algorithms for approximating MAX-CUT

DOI10.4230/LIPICS.ITCS.2025.44MaRDI QIDQ7296683zbMATH OpenFDO

Authors Yinhao Dong, Pan Peng, Ali Vakilian

Publication date 14 July 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ITCS.2025.44

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• (1 + (1))-approximation to MAX-CUT requires linear space
• An improved data stream summary: the count-min sketch and its applications
• An optimal space lower bound for approximating MAX-CUT
• Competitive Caching with Machine Learned Advice
• Constraint satisfaction problems with advice
• Fast and Space Efficient Spectral Sparsification in Dynamic Streams
• Graph searching with predictions
• scientific article; zbMATH DE number 7650400 (Why is no real title available?)
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Learning-augmented maximum independent set
• On dynamic graph algorithms with predictions
• On the complexity of algorithms with predictions for dynamic graph problems
• Online Metric Algorithms with Untrusted Predictions
• Online Scheduling via Learned Weights
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Property testing. Problems and techniques
• Random sampling with a reservoir
• Sketching cuts in graphs and hypergraphs
• Streaming Lower Bounds for Approximating MAX-CUT

Cited in

(1)

• Graph Coarsening Enables Escaping Local Optima in Compute-Constrained Nonconvex MAX-CUT

This page was built for publication: Learning-augmented streaming algorithms for approximating MAX-CUT

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