Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

share|improve this question
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

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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