1
$\begingroup$

This is the initial setting:

A museum hire guards to check on the art pieces in a hallway. Each guard has a range of 10 meters. (5 on the right side and 5 on the left. The guard is in the middle) Each art piece has a position that is specified beforehand. The goal is to place as few guards as possible to cover all the art pieces.

Example: I have {1,2,3} the first art piece is 1 meter from the entrance, the second art piece is 2 meters from the entrance etc...

Now we have this Greedy Algorithm given to solve this problem:

Select a range of 10 meters that covers the most art-pieces. The guard's position will be in the middle of this range. Remove the points that correspond to the positions of the art pieces covered by the range. Re-do the same process with the remaining art pieces.

I'm asked to find a set of art-pieces positions i.e: {1,2,3} that will make it impossible to find an optimal solution using that Algorithm.

I thought that putting each pair of art-pieces at a 10 meter distance from each other would cause the Algorithm to not find an optimal solution.

$\endgroup$
1
  • $\begingroup$ How long is the hallway, and how many guards are there? Also, 10 meters is not enough, they should probably be $10+\varepsilon$ meters apart if you want each guard to be able to cover only one piece. $\endgroup$ Commented Feb 6, 2020 at 18:38

1 Answer 1

Reset to default
5
$\begingroup$

Put art works at $-10$ and $10$, and at $-5,-4,-3,-2,-1,0,1,2,3,4,5$.

The greedy algorithm will tell you to place a guard at $0$ to cover $11$ pieces at once.

Then one would need two more guards to cover $-10$ and $10$.

However, if we put two guards at $-5$ and at $5$ we can cover all the pieces. Each of them cover only $7$ pieces.

$\endgroup$
1
  • $\begingroup$ I would be nice if you could tell me how you found that solution. What was your thought process and how to come up with stuff like that with other algorithms. Thank You! $\endgroup$ Commented Feb 6, 2020 at 20:35

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.