This paper considers the cover by s-defective independent sets problem (or, simply, the s-defective coloring problem), which generalizes the classical coloring problem. In the coloring problem, each color class should induce an edgeless subgraph. The s-defective coloring problem relaxes this requirement, allowing for at most s edges to appear in each color class's induced subgraph. We propose a local search neighborhood and apply the GRASP metaheuristic to the related minimization problem. The quality of the heuristically-generated solutions is evaluated with a commercial MIP solver. The integer programming formulation that we use generalizes the asymmetric representatives formulation.
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
Tel.: +1 703 830 6300
Fax: +1 703 830 2300 firstname.lastname@example.org
(Corporate matters and books only) IOS Press c/o Accucoms US, Inc.
For North America Sales and Customer Service
West Point Commons
Lansdale PA 19446
Tel.: +1 866 855 8967
Fax: +1 215 660 5042 email@example.com