The country of Ecolinearia has managed to find a method of recycling every singl

Question

The country of Ecolinearia has managed to find a method of recycling every single item that used to go to landfills. The last step in becoming a zero waste society is for the government to decide where to place k recycling plants. This is where you come in. There are n cities in Ecolinearia, and there is a completely straight central road that passes through all the cities. The cities have positions pi , Pn, all of which can be considered to be integers, and you can assume that pi P2 ···Pn. The government has funds to build k n recycling plants, and each of these k plants must be in a city(ie, if we decide to put a plant in a city, the position of the plant is the same as the position of the city) 2 Your goal is to come up with an algorithm that places the recycling plants, such that the average distance between a city and the nearest recycling plant is minimized. Prove the correctness of your algorithm, and state its runtime.

Explanation / Answer

Consider the problem in the following way:

Given n nodes, cluster them into k groups such that their radius is minimized.

This problem can be solved using Dynamic Programming

For k = 1, the problem is trivial (just put it in the center),

Let us denote this solution as Rn,1.

Now the required solution is denoted by R(n,k) where there are k centers in the first n nodes.

For k>1, consider all the cases, according to the number (let's say x) of points, that are present in the last cluster (meaning the last cluster contains the rightmost continuous sequence of x points.)  

The algorithm can be described by the following formula:

R(n,k) = min0<=x<=n {R(n-x,k-1)+Rx,1}

The time complexity is O(n2 * k) and the space complexity is O(n2)

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.