Блог пользователя askhelper

Quarantine problem: Social distancing (NP?)
Автор askhelper, 5 лет назад, По-английски

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?

  • Проголосовать: нравится
  • +34
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится -21 Проголосовать: не нравится

use binary search

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is it manhattan or euclid distance?

→ Ответить
»
5 лет назад, # |
← Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится

Deleted

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
»
5 лет назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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.

→ Ответить