As a guest user you are not logged in or recognized by your IP address. You have
access to the Front Matter, Abstracts, Author Index, Subject Index and the full
text of Open Access publications.
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.