Next: MINIMUM RED-BLUE SEPARATION Up: Miscellaneous Previous: MINIMUM PHYLOGENETIC TREE DISTANCE Index

### MAXIMUM FREQUENCY ALLOCATION

- INSTANCE: Graph , and, for each node u, a finite set of available frequencies and an integer Mu.
- SOLUTION: A frequency allocation for G, i.e., for each node u, a subset S(u) of L(u) such that, for all , , and, for all , .
- MEASURE: The stability number of the allocation, i.e., .

- Good News: Approximable within 2 [349].
- Bad News: APX-complete [349].
- Comment: Reduction from MAXIMUM 3-SATISFIABILITY.