Cycle-based facets of chromatic scheduling polytopes

Chromatic scheduling polytopes arise as solution sets of the bandwidth allocation problem in certain radio access networks, which supply wireless access to voice/data communication for customers with fixed antennas and individual demands. This problem is NPNP-complete and, moreover, does not admit polynomial-time approximation algorithms with a fixed quality guarantee. As algorithms based on cutting planes have shown to be successful for many other combinatorial optimization problems, our goal is to apply such methods to the bandwidth allocation problem. To gain the required knowledge on the associated polytopes, the present paper contributes by considering three new classes of valid inequalities based on cycles in the interference graph. We discuss in which cases they define facets and explore the associated separation problems, showing that two of them are solvable in polynomial time.