3
$\begingroup$

Question:

Given a tree representing a neighbourhood where each node is a house. Assign an antenna to each node such that the whole tree is covered.

An antenna of strength 0 can only provide a signal to itself. An antenna of strength j can provide a signal to itself and nodes that are j steps away from it. The cost of building an antenna at a house is given by a cost function f(ni, j) where ni is the i'th node and j is the signal strength. Additionally the cost of an antenna with strength j has to be less or equal the cost of an antenna with strength i if j is weaker than i. 

     7 
     | 
     6 
   / | \
  3  4  5
 / \
1   2

For example an optimal solution in this tree for a cost function f(ni, j) = j + 1 would be to place an antenna of strength 2 at node 6.

This is a school assignment and the ultimate goal is to write a dynamic programm that can solve it in O(n^2). As far as my understanding goes the 'trick' of dynamic programming is to find a recursive algorithm that can solve the problem in exp. time and then use a table to cache the intermediate answers that build upon each other to improve the time complexity.

I fail in seeing a recurrence in the problem and and would appreciate if someone could point me in the right direction.

Improve this question
$\endgroup$
12
  • 4
    $\begingroup$ Cute and by no means easy problem! The "trick" of DP is figuring out which side conditions you can add to subproblems to make it possible to solve them all in terms ot solutions to smaller subproblems. Hint: Root the tree somewhere, and try solving subproblems of the form "The cheapest (partial) solution for the subtree rooted at $v$ and having excess $m$", where $v$ is any vertex and $m$ is an integer in the range $[-|V|, |V|]$. Getting the time down from $O(n^3)$ to $O(n^2)$ is tricky in itself, and involves computing only certain "baseline" sums and using subtraction to get the others. $\endgroup$ – j_random_hacker Jun 8 '20 at 19:02
  • 2
    $\begingroup$ This is supposed to be a learning exercise, and that would give the game away I think. "Excess" is just a term I came up with -- it doesn't have any standard meaning. FWIW I've solved many DP problems and it took me a couple of hours to come up with a working strategy for this one; if you are new to DP, I suggest starting with much easier problems. Independent Set on a tree is a nice one. $\endgroup$ – j_random_hacker Jun 9 '20 at 10:58
  • 1
    $\begingroup$ Where did you encounter this task? Please credit the source of all copied material (see cs.stackexchange.com/help/referencing). $\endgroup$ – D.W.♦ Jun 10 '20 at 20:21
  • 3
    $\begingroup$ You can still credit the author of the problem (e.g., your professor/instructor) and the course where you encountered it. $\endgroup$ – D.W.♦ Jun 10 '20 at 20:26
  • 2
    $\begingroup$ The probable source for this problem is a homework assignment from the "Algorithmentheorie" course at Technische Universität Berlin. The authors credited on the assignment are: Niedermeier, Nichterlein, Bentert and Heeger. $\endgroup$ – awmanthisissad Jun 26 '20 at 20:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.