Approximate graph colouring and the hollow shadow
| Autor: | Zivny, S, Ciardo, L |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2023 |
| DOI: | 10.1145/3564246.3585112 |
| Popis: | 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 reflection and satisfy a sparsity condition, which may be of independent interest. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|