# What kind of optimization problem is that?

I am new here as a writer but I read this group from time to time. I am thinking about the following problem.

Problem description:

Assume we have an area $A$ of size $1000 \times 1000$ cells. One cell is addressed with $(x,y)$ pair, where $x$ and $y$ are positive integers. We are given the set of points (locations) on area $A$, lets say we have $N$ locations. These locations are fixed and given as an input. In practice N is lower than 1000. In each location we can build a sender station that sends some signal. Sender stations can have 4 levels: 0,1,2,3. Building a sender station with proper level costs: $c_0=0$, $c_1>0$, $c_2>c_1$ and $c_3>c_2$ respectively. Costs are equal for each location. Moreover costs are fixed and given as an input. Each sender station covers given circular area with signal. Radius are following: $r_0=0$, $r_1>0$, $r_2>r_1$, $r_3>r_2$. Radius is fixed and given as an input.

Question: What level of sender station should be build in each location in such a way, that: all locations are covered with signal and the total cost of building is minimized?

My question to that is: what kind of theoretical problem is that? Is there some easy transformation to some well known optimization problem?

This is not a homework from university, just my own riddle :)

-
This is a covering problem. Given an $n\times n$ square and $N$ centers with radius and cost $r_i,\dots,r_n$, $c_i, \dots,c_n$, cover the square such that cost is minimized. – Nicholas Mancuso Feb 1 '12 at 15:39
I agree that this is very similar to the disc covering problem, but is it really the same? You cannot place the discs (name from the orginal covering problem) in any place - here you can only place them in some of given locations. – Piotr Feb 1 '12 at 17:01
You can calculate the family of sets $S_{x,w}$ of points covered by placing a station of level $w$ at location $x$ ($w \in \{1,2,3\}$, $x \in \{1,..,N\}$) in polynomial time. Then your problem reduces to the weighted set cover (en.wikipedia.org/wiki/Set_cover_problem) in which the cost of the collection $S_{x,w}$ is $c_w$. – Marzio De Biasi Feb 1 '12 at 17:34
Thank both of you for your answers :) – Piotr Feb 1 '12 at 18:43
@Piotr: perhaps, if the answer is satisfactory, I can convert the comment to an answer and you can accept and close the question. Or are you waiting other answers / details ? – Marzio De Biasi Feb 4 '12 at 11:51