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

  • 2
    $\begingroup$ 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. $\endgroup$ Feb 1, 2012 at 15:39
  • 1
    $\begingroup$ 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. $\endgroup$
    – Piotr
    Feb 1, 2012 at 17:01
  • 3
    $\begingroup$ 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$. $\endgroup$ Feb 1, 2012 at 17:34
  • $\begingroup$ Thank both of you for your answers :) $\endgroup$
    – Piotr
    Feb 1, 2012 at 18:43
  • $\begingroup$ @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 ? $\endgroup$ Feb 4, 2012 at 11:51

1 Answer 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.