gXa's blog

Minimum number of players
By gXa, history, 8 years ago, In English

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?
  • Vote: I like it
  • +6
  • Vote: I do not like it

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

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.

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

    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

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it
      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
      → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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".

→ Reply