MAXIMUM FREQUENCY ALLOCATION

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

INSTANCE: Graph $G=\left(V,E\right)$ , and, for each node u, a finite set $L(u) \subset Z^+$ of available frequencies and an integer .
SOLUTION: A frequency allocation for G, i.e., for each node u, a subset S(u) of L(u) such that, for all $u \in V$ , $1\leq\vert S(u)\vert\leq M_u$ , and, for all $(u,v) \in E$ , $S(u) \cap S(v) = \emptyset$ .
MEASURE: The stability number of the allocation, i.e., $\sum_{u \in V}\vert S(u)\vert$ .
Good News: Approximable within 2 [369].
Bad News: APX-complete [369].
Comment: Reduction from MAXIMUM 3-SATISFIABILITY.

Viggo Kann
2000-03-20