<p>As pointed out in the comments already, this is an instance of weighted geometric set cover. Here are some recent relevant references: 
<a href="http://www.divms.uiowa.edu/~kvaradar/paps/weightedcover.pdf" rel="nofollow">http://www.divms.uiowa.edu/~kvaradar/paps/weightedcover.pdf</a> 
See also the follow up work:
<a href="http://www.cs.uwaterloo.ca/~tmchan/cover_soda.pdf" rel="nofollow">http://www.cs.uwaterloo.ca/~tmchan/cover_soda.pdf</a></p>

CC BY-SA 3.0
2012-02-10T14:30:19.470Z
2012-02-10T14:30:19.470Z
Sariel Har-Peled
<p>I am new here as a writer but I read this group from time to time.
I am thinking about the following problem.</p>

<hr>

<p>Problem description:</p>

<p>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&gt;0$, $c_2&gt;c_1$ and $c_3&gt;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&gt;0$, $r_2&gt;r_1$, $r_3&gt;r_2$. Radius is fixed and given as an input.</p>

<p>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?</p>

<hr>

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

<p>This is not a homework from university, just my own riddle :)</p>

CC BY-SA 3.0
2012-02-01T15:39:47.477Z
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
CC BY-SA 3.0
2012-02-01T17:01:07.683Z
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
CC BY-SA 3.0
2012-02-01T17:34:22.700Z
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* (http://en.wikipedia.org/wiki/Set_cover_problem) in which the cost of the collection $S_{x,w}$ is $c_w$.
Marzio De Biasi
CC BY-SA 3.0
2012-02-01T18:43:53.340Z
Thank both of you for your answers :)
Piotr
CC BY-SA 3.0
2012-02-04T11:51:22.113Z
@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
CC BY-SA 3.0
2012-02-17T12:21:09.600Z
Yes, thank you. Actually after a trivial transformation it is a Weighted Set Cover Problem. I have accepted the answer below to point that this is solved and closed.
Piotr
<ds.algorithms><optimization>
What kind of optimization problem is that?
Piotr
# What kind of optimization problem is that?

(Asked by: username_0 on 2012-02-01)

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 :)

**Tags:** ds.algorithms, optimization
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_2**: 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* (http://en.wikipedia.org/wiki/Set_cover_problem) in which the cost of the collection $S_{x,w}$ is $c_w$.  
> **username_0**: Thank both of you for your answers :)  
> **username_2**: @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 ?  
> **username_0**: Yes, thank you. Actually after a trivial transformation it is a Weighted Set Cover Problem. I have accepted the answer below to point that this is solved and closed.  

---

## 1 answers

### Answer by username_3 on 2012-02-10. Score: 1 | Accepted answer

As pointed out in the comments already, this is an instance of weighted geometric set cover. Here are some recent relevant references:
<http://www.divms.uiowa.edu/~kvaradar/paps/weightedcover.pdf>
See also the follow up work:
<http://www.cs.uwaterloo.ca/~tmchan/cover_soda.pdf>


---

