Copertina

On the Approximability of Max-Cut on 3-Colorable Graphs and Graphs with Large Independent Sets

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Ghoshal, Suprovat, Huang, Neng, Lee, Euiwoong, Makarychev, Konstantin, Makarychev, Yury
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Constraint Satisfaction Problems with Advice
di: Ghoshal, Suprovat, et al.
Pubblicazione: (2024)

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

Approximation algorithms for satisfiable and nearly satisfiable ordering CSPs
di: Makarychev, Yury
Pubblicazione: (2026)

Max-Cut with Multiple Cardinality Constraints
di: Makarychev, Yury, et al.
Pubblicazione: (2025)

Improved SDP-Based Algorithm for Coloring 3-Colorable Graphs
di: Bansal, Nikhil, et al.
Pubblicazione: (2026)

Hardness of Approximation for Shortest Path with Vector Costs
di: Carlson, Charlie, et al.
Pubblicazione: (2025)

Approximation Algorithms for $\ell_p$-Shortest Path and $\ell_p$-Group Steiner Tree
di: Makarychev, Yury, et al.
Pubblicazione: (2024)

A Simple Average-case Analysis of Recursive Randomized Greedy MIS
di: Dalirrooyfard, Mina, et al.
Pubblicazione: (2026)

SPARSE-PIVOT: Dynamic correlation clustering for node insertions
di: Dalirrooyfard, Mina, et al.
Pubblicazione: (2025)

Pruned Pivot: Correlation Clustering Algorithm for Dynamic, Parallel, and Local Computation Models
di: Dalirrooyfard, Mina, et al.
Pubblicazione: (2024)

Dynamic Algorithm for Explainable k-medians Clustering under lp Norm
di: Makarychev, Konstantin, et al.
Pubblicazione: (2025)

Optimal Phylogenetic Reconstruction from Sampled Quartets
di: Arvanitakis, Dionysis, et al.
Pubblicazione: (2026)

Approximating Small Sparse Cuts
di: Anand, Aditya, et al.
Pubblicazione: (2024)

Approximating Maximum Cut on Interval Graphs and Split Graphs beyond Goemans-Williamson
di: Ahn, Jungho, et al.
Pubblicazione: (2025)

A Polynomial-Time Approximation for Pairwise Fair $k$-Median Clustering
di: Bandyapadhyay, Sayan, et al.
Pubblicazione: (2024)

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

All-Subsets Important Separators with Applications to Sample Sets, Balanced Separators and Vertex Sparsifiers in Directed Graphs
di: Anand, Aditya, et al.
Pubblicazione: (2025)

Local Max-Cut on Sparse Graphs
di: Schwartzman, Gregory
Pubblicazione: (2023)

Improved Approximation Algorithms for Multiway Cut by Large Mixtures of New and Old Rounding Schemes
di: Brakensiek, Joshua, et al.
Pubblicazione: (2026)

Improved Approximation Algorithms for Chromatic and Pseudometric-Weighted Correlation Clustering
di: Fan, Chenglin, et al.
Pubblicazione: (2025)

1.64-Approximation for Chromatic Correlation Clustering via Chromatic Cluster LP
di: Lee, Dahoon, et al.
Pubblicazione: (2025)

Max-Cut with $ε$-Accurate Predictions
di: Cohen-Addad, Vincent, et al.
Pubblicazione: (2024)

Min-CSPs on Complete Instances II: Polylogarithmic Approximation for Min-NAE-3-SAT
di: Anand, Aditya, et al.
Pubblicazione: (2025)

Approximation Ratio of the Min-Degree Greedy Algorithm for Maximum Independent Set on Interval and Chordal Graphs
di: Chaplick, Steven, et al.
Pubblicazione: (2024)

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

Optimal Approximations for the Requirement Cut Problem on Sparse Graph Classes
di: Mallek, Nadym, et al.
Pubblicazione: (2025)

Facility Location on High-dimensional Euclidean Spaces
di: Lee, Euiwoong, et al.
Pubblicazione: (2025)

Separating $k$-Median from the Supplier Version
di: Anand, Aditya, et al.
Pubblicazione: (2024)

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

Approximating Sparsest Cut in Low-Treewidth Graphs via Combinatorial Diameter
di: Chalermsook, Parinya, et al.
Pubblicazione: (2021)

Maximum Weight Independent Set in Hereditary Classes of Ordered Graphs
di: Bieliński, Paweł Rafał, et al.
Pubblicazione: (2026)

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

Exponential Time Approximation for Coloring 3-Colorable Graphs
di: Guruswami, Venkatesan, et al.
Pubblicazione: (2024)

Sketching Cuts in Graphs and Hypergraphs
di: Kogan, Dmitry, et al.
Pubblicazione: (2014)

Almost-Uniform Edge Sampling: Leveraging Independent-Set and Local Graph Queries
di: Adar, Tomer, et al.
Pubblicazione: (2026)

Sum-of-Squares Lower Bounds for Independent Set in Ultra-Sparse Random Graphs
di: Kothari, Pravesh, et al.
Pubblicazione: (2024)

An Improved Greedy Approximation for (Metric) $k$-Means
di: Charikar, Moses, et al.
Pubblicazione: (2026)

Streaming Max-Cut in General Metrics
di: Jiang, Shaofeng H. -C., et al.
Pubblicazione: (2025)

Comparison of Hyperplane Rounding for Max-Cut and Quantum Approximate Optimization Algorithm over Certain Regular Graph Families
di: Tate, Reuben, et al.
Pubblicazione: (2025)

Finding Triangles or Independent Sets; and Other Dual Pair Approximations
di: Dumitrescu, Adrian
Pubblicazione: (2021)