A Linear Bound on the Rainbow Cycle Number and Approximate EFX

Varun Sivashankar

It is open whether every fair-division instance with additive valuations admits a complete envy-free-up-to-any-good (EFX) allocation. A well-studied relaxation allows some goods to…