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

Minimum number of players
Автор gXa, история, 7 лет назад, По-английски

Give N=no. of players

K=No. of fans

likeMatrix=It is a sting array of size K where each element of array have size N.

(contains 0 and 1 only) where if a[i][j] ==1 represents fan(i) likes player(j)

Ex. N=5

K=3

like={ "10101","00001","01011","...","...." }

Count min. no. of players required to put in team such that each fan likes atleast one player.

I think it is minimum bipartite matching(just opposite to maximum bipartite matching). So, can anybody tell me how to solve it?
  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

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

What about using a greedy solution.
1. Pick the player with maximum number of fans.
2. Then remove all those fans.
Repeat this till each fan has been picked up.
UPD: Thinking more, isn't this the same as Set Cover Problem which is NP-Complete.

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

    This algo is not correct.

    Consider a case:

    1001

    1000

    0100

    0100

    0011

    0011

    Here you would choose all 4 columns, but answer is just columns: 1, 2, 3( 3 columns ).

    UPD: There was a small typo:

    The case was:

    1000

    1001

    0100

    0101

    0010

    0011

    → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
      1. The algo will not be correct as I mentioned in my updated comment that it is similar to set-cover problem.
      2. In above case, the greedy sol selects column 4, column 2, and column 1. So it works in this case. In fact, the greedy soluton has approximation ratio  <  = ln(n) + 1
      → Ответить
»
7 лет назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

More formal :

Minimize number of Xi = 1

(XA11 or XA12 or ... or XA1K1) and ... and (XAi1 or XAi2 or ... or XAiKi) and ... and (XAn1 or XAn2 or ... or XAnKn)  = 1

and it look like "The Minimum Assignment Problem" link , "It is shown that the Minimum Assignment Problem is NP-complete for 2-CNF and Horn CNF formulae".

→ Ответить