Re: Polynomial time...Could someone please help...give any idea...thanks.



On Jun 6, 4:27 pm, Trish <trinhnguyen...@xxxxxxxxx> wrote:
Please help me with this hw...

You work for the emergency preparedness Center and your lastest project is to develop a system to deploy people to local hospitals in the event of a volcanic explosion at Mount Rain. The main task in such an emergency situation is that ambulances will be deployed to pick up injured people and deliver them to nearby hospitals. There are k hospitals in the region and n injured people. For medical reasons you have determined that a person must be taken to a hospital that is within a 15 minute drive from where they were picked up. Also, you don;t want to overload any one hospital so you want to take at most n/k patients to each hospital.
Give a polynomial time algorithm that takes the given information about the injured people's locations and the locations of the hospitals and determines whether there is a way to distribute the patients to the area hospitals so that no single hospital is overloaded.

Let's see what you have tried so far.
Sounds like a linear programming problem to me.

.