Approximate graph colouring and the hollow shadow
We show that approximate graph colouring is not solved by constantly many levels of the liftand-project hierarchy for the combined basic linear programming and affine integer programming relaxation. The proof involves a construction of tensors whose fixed-dimensional projections are equal up to refl...
| Asıl Yazarlar: | , |
|---|---|
| Materyal Türü: | Conference item |
| Dil: | English |
| Baskı/Yayın Bilgisi: |
Association for Computing Machinery
2023
|