askhelper's blog

Quarantine problem: Social distancing (NP?)
By askhelper, 5 years ago, In English

You are given an $$$N$$$x$$$N$$$ grid and $$$K$$$ people. Put all people in the grid such that the minimum manhattan distance between any two is maximized. What's the best solution for this problem? Is it NP?

  • Vote: I like it
  • +34
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
5 years ago, # |
  Vote: I like it -21 Vote: I do not like it

use binary search

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it manhattan or euclid distance?

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -10 Vote: I do not like it

Deleted

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

man if only someone could solve this

my first impression would be to fill in all 4 corners, then the middle, then the middle of each 4 resulting squares, then the 4 midpoints of each square, and keep on subdividing it until minimum

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What if N = 4, and K = 16? Seems like greedy / binSearch solution would not be optimal here.

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

NP contains decision problems. So you should also be given a value V and check if you can put the people in the grid so as their distances to satisfy the value V.

Now this problem is in NP because given a certificate (a placement of people) you can decide if this is a legal certificate or no in polynomial time. But this is easy.

Your actual question is if it is NP-complete, meaning if it has a polynomial time algorithm.

→ Reply