Imagen de Portada

Improved SDP-Based Algorithm for Coloring 3-Colorable Graphs

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Bansal, Nikhil, Huang, Neng, Lee, Euiwoong
Formato:	Preprint
Publicado:	2026
Materias:	Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

On the Approximability of Max-Cut on 3-Colorable Graphs and Graphs with Large Independent Sets
por: Ghoshal, Suprovat, et al.
Publicado: (2026)

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

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

Improved Sublinear Algorithms for Classical and Quantum Graph Coloring
por: Ferber, Asaf, et al.
Publicado: (2025)

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

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

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

Coloring 3-Colorable Graphs with Low Threshold Rank
por: Hsieh, Jun-Ting
Publicado: (2025)

A Near-Real-Time Reduction-Based Algorithm for Coloring Massive Graphs
por: Zhu, Chenghao, et al.
Publicado: (2025)

Fully Dynamic Algorithms for Coloring Triangle-Free Graphs
por: Assadi, Sepehr, et al.
Publicado: (2026)

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

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

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

Improved linearly ordered colorings of hypergraphs via SDP rounding
por: Louis, Anand, et al.
Publicado: (2024)

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

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

Optimal 4-Approximation for the Correlated Pandora's Problem
por: Bansal, Nikhil, et al.
Publicado: (2025)

Improved Streaming Edge Coloring
por: Chechik, Shiri, et al.
Publicado: (2025)

Arboricity-Dependent Algorithms for Edge Coloring
por: Bhattacharya, Sayan, et al.
Publicado: (2023)

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

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

Improved Bounds for Twin-Width Parameter Variants with Algorithmic Applications to Counting Graph Colorings
por: Baril, Ambroise, et al.
Publicado: (2025)

Connectivity Labeling in Faulty Colored Graphs
por: Petruschka, Asaf, et al.
Publicado: (2024)

Coloring tournaments with few colors: Algorithms and complexity
por: Klingelhoefer, Felix, et al.
Publicado: (2023)

Online Graph Coloring for $k$-Colorable Graphs
por: Kawarabayashi, Ken-ichi, et al.
Publicado: (2025)

An Improved Bound for the Beck-Fiala Conjecture
por: Bansal, Nikhil, et al.
Publicado: (2025)

A Quasi-Polynomial Time Algorithm for 3-Coloring Circle Graphs
por: S, Ajaykrishnan E, et al.
Publicado: (2025)

Approximating Small Sparse Cuts
por: Anand, Aditya, et al.
Publicado: (2024)

Matroid-Based TSP Rounding for Half-Integral Solutions
por: Gupta, Anupam, et al.
Publicado: (2021)

Improved Algorithms for Overlapping and Robust Clustering of Edge-Colored Hypergraphs: An LP-Based Combinatorial Approach
por: Lee, Changyeol, et al.
Publicado: (2025)

Online Coloring for Graphs of Large Odd Girth
por: Yoneda, Hirotaka, et al.
Publicado: (2026)

Dynamic Graph Coloring: Sequential, Parallel, and Distributed
por: Ghaffari, Mohsen, et al.
Publicado: (2025)

Faster Vizing and Near-Vizing Edge Coloring Algorithms
por: Assadi, Sepehr
Publicado: (2024)

On the FirstFit Algorithm for Online Unit-Interval Coloring
por: Krekelberg, Bob, et al.
Publicado: (2025)

Density-Sensitive Algorithms for $(Δ+ 1)$-Edge Coloring
por: Bhattacharya, Sayan, et al.
Publicado: (2023)

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

Coloring Reconfiguration under Color Swapping
por: Fuchs, Janosch, et al.
Publicado: (2025)

Expander Decomposition with Almost Optimal Overhead
por: Bansal, Nikhil, et al.
Publicado: (2026)

On Approximating Cutwidth and Pathwidth
por: Bansal, Nikhil, et al.
Publicado: (2023)

Coloring Graphs with Few Colors in the Streaming Model
por: Assadi, Sepehr, et al.
Publicado: (2025)