Mhammad1's blog

An Interesting Problem!
By Mhammad1, history, 8 years ago, In English

I have that problem in my mind and cannot figure out how to solve it, the problem as follow:

Given n clients (1 - n) , m shops and every shop can serve a set of clients (this set is given in the input), so maybe the client can be served by more than one shop, what is the minimum number of shops that can cover(serve) all clients?

I thought about max flow but I failed to come up with the solution.. I know that min cost algorithm will pay for every flow a specific cost, could I modify the algorithm so every X flow will pay only (1) cost?

Any ideas?

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

»
8 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I was thinking on this problem just about 30mins ago...

I'm interested about the answer too...

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

Each shop can only serve a given subset of the clients, or it can serve any clients?

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

    I think each shop will serve a given subset and you don't have to choose just one of the clients for a shop, it can serve all of the clients at once...

    Actually we have a bipartite graph and we want to choose minimum number of vertices from part A such that each vertex in part B would be adjacent to at least one of the chosen vertices...(If I understood his problem correctly)

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

    Edited!

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

Auto comment: topic has been updated by Mhammad1 (previous revision, new revision, compare).

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

Isn't it NP-hard?

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

If I understood your problem correctly, it is the same as the Set cover problem. It is NP-complete.

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

    Actually yes you're correct, the problem is NP-complete, thanks for your help :D

    But one more thing, can I modify the min-cost algorithm to pay (1) cost for each (X) flow?

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

      isn't this a special case of set cover but not exactly set cover so this might be solvable right

      → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

A variation of Algorithm X will do this for you — just keep the columns of the matrix untouched when processing/backtracking guesses. The DLX implementation can solve this quite efficiently despite its NPC nature.

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

    Algorithm X find any solution but not the minimum solution .

    → Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

if n is less than 20 you can solve it with dp+bitmask

→ Reply