Lagrangian relaxation for the directional sensor coverage problem with continuous orientation

We prove NP-hardness of DSCCP and introduce a Lagrangian relaxation model. We design a dual ascent procedure based on acting on a single multiplier at a time accompanied by a heuristics to find a feasible solution at each ascent iteration. We report also the results of the method on several test problems.