Cover Image

Max-Cut with $ε$-Accurate Predictions

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Cohen-Addad, Vincent, d'Orsi, Tommaso, Gupta, Anupam, Lee, Euiwoong, Panigrahi, Debmalya
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms Computational Complexity F.0
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Complexity of Local Search for CSPs Parameterized by Constraint Difference
by: Anand, Aditya, et al.
Published: (2025)

A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering
by: Cohen-Addad, Vincent, et al.
Published: (2024)

Combinatorial Optimization using Comparison Oracles
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Multi-View Stochastic Block Models
by: Cohen-Addad, Vincent, et al.
Published: (2024)

On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
by: S., Karthik C., et al.
Published: (2024)

Private graphon estimation via sum-of-squares
by: Chen, Hongjie, et al.
Published: (2024)

Perturb-and-Project: Differentially Private Similarities and Marginals
by: Cohen-Addad, Vincent, et al.
Published: (2024)

Maximum Partial List H-Coloring on P_5-free graphs in polynomial time
by: Lokshtanov, Daniel, et al.
Published: (2024)

Near-Optimal Bounds for Parameterized Euclidean k-means
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
by: Cohen-Addad, Vincent, et al.
Published: (2026)

An Optimal Randomized Algorithm for Finding the Saddlepoint
by: Dallant, Justin, et al.
Published: (2024)

Superpolynomial smoothed complexity of 3-FLIP in Local Max-Cut
by: Michel, Lukas, et al.
Published: (2023)

Asymptotically Optimal Hardness for $k$-Set Packing and $k$-Matroid Intersection
by: Lee, Euiwoong, et al.
Published: (2024)

Replicability in High Dimensional Statistics
by: Hopkins, Max, et al.
Published: (2024)

Planarizing Gadgets for (k, l)-tight Graphs Do Not Exist
by: Chauhan, Archit, et al.
Published: (2026)

On Purely Private Covariance Estimation
by: d'Orsi, Tommaso, et al.
Published: (2025)

Tight Differentially Private PCA via Matrix Coherence
by: d'Orsi, Tommaso, et al.
Published: (2025)

On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems
by: DeHaan, Ian, et al.
Published: (2025)

Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median
by: Cohen-Addad, Vincent, et al.
Published: (2022)

Multi-Pass Streaming Lower Bounds for Approximating Max-Cut
by: Fei, Yumou, et al.
Published: (2025)

Online Paging with Heterogeneous Cache Slots
by: Chrobak, Marek, et al.
Published: (2022)

On the (Classical and Quantum) Fine-Grained Complexity of Approximate CVP and Max-Cut
by: Huang, Jeremy Ahrens, et al.
Published: (2024)

Max Cut with Small-Dimensional SDP Solutions
by: Chang, Hsien-Chih, et al.
Published: (2026)

Minimum Stable Cut and Treewidth
by: Lampis, Michael
Published: (2021)

Linear-Time MaxCut in Multigraphs Parameterized Above the Poljak-Turzík Bound
by: Lill, Jonas, et al.
Published: (2024)

On the formalization of the notion of an algorithm
by: Middelburg, C. A.
Published: (2024)

Pseudodeterministic Algorithms for Minimum Cut Problems
by: Agarwala, Aryan, et al.
Published: (2025)

Parameterized Critical Node Cut Revisited
by: Knop, Dušan, et al.
Published: (2025)

Parameterized Max Min Feedback Vertex Set
by: Lampis, Michael, et al.
Published: (2023)

Self-referential instances of the dominating set problem are irreducible
by: Zhou, Guangyan
Published: (2026)

A $(2+\varepsilon)$-Approximation Algorithm for Metric $k$-Median
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Complexity of Finding and Enumerating Interconnection Trees
by: Demange, Noé, et al.
Published: (2026)

Parallel Complexity of Depth-First-Search and Maximal path in restricted graph classes
by: Chauhan, Archit, et al.
Published: (2025)

On the Approximability of Train Routing and the Min-Max Disjoint Paths Problem
by: Bhaskar, Umang, et al.
Published: (2025)

U-Bubble Model for Mixed Unit Interval Graphs and its Applications: The MaxCut Problem Revisited
by: Kratochvíl, Jan, et al.
Published: (2020)

I/O complexity and pebble games with partial computations
by: Sobczyk, Aleksandros
Published: (2024)

A tight quasi-polynomial bound for Global Label Min-Cut
by: Jaffke, Lars, et al.
Published: (2022)

Connectivity-Preserving Important Separators: A Framework for Cut-Uncut Problems
by: Kenig, Batya
Published: (2025)

Improved Hardness and Approximations for Cardinality-Based Minimum $s$-$t$ Cuts Problems in Hypergraphs
by: Adriaens, Florian, et al.
Published: (2024)

Planar Multiway Cut with Terminals on Few Faces
by: Pandey, Sukanya, et al.
Published: (2025)