Maximum Coverage Problems: Theory and Application in Optimal Sensor Selection

In this thesis we analyse the class of <i>maximum coverage</i> problems. For all discussed problems, linear programs are formulated. Using the notion of <i>submodularity</i>, we prove that for the weighted version of the basic <i>Maximum Coverage</i> problem, where the weights differ per set, a polynomial-time greedy algorithm guarantees a (1 -...