Approximate Hypergraph Coloring under Low-discrepancy and Related Promises
From MaRDI portal
Publication:5351896
DOI10.4230/LIPIcs.APPROX-RANDOM.2015.152zbMath1375.05085arXiv1506.06444OpenAlexW2963950837MaRDI QIDQ5351896
Vijay V. S. P. Bhattiprolu, Euiwoong Lee, Venkatesan Guruswami
Publication date: 31 August 2017
Full work available at URL: https://arxiv.org/abs/1506.06444
algorithmssemidefinite programmingdiscrepancyhardness of approximationhypergraph coloringrainbow coloringstrong coloring
Analysis of algorithms and problem complexity (68Q25) Semidefinite programming (90C22) Hypergraphs (05C65) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
Rainbow Coloring Hardness via Low Sensitivity Polymorphisms, Quasi-polynomial algorithms for list-coloring of nearly intersecting hypergraphs, The Quest for Strong Inapproximability Results with Perfect Completeness, Rainbow Coloring Hardness via Low Sensitivity Polymorphisms