By Mhammad1, history, 7 years ago,

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?

• +19

 » 7 years ago, # |   +8 I was thinking on this problem just about 30mins ago...I'm interested about the answer too...
 » 7 years ago, # |   0 Each shop can only serve a given subset of the clients, or it can serve any clients?
•  » » 7 years ago, # ^ |   0 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)
•  » » 7 years ago, # ^ |   0 Edited!
 » 7 years ago, # |   0 Auto comment: topic has been updated by Mhammad1 (previous revision, new revision, compare).
 » 7 years ago, # |   0 Isn't it NP-hard?
 » 7 years ago, # | ← Rev. 3 →   +8 If I understood your problem correctly, it is the same as the Set cover problem. It is NP-complete.
•  » » 7 years ago, # ^ |   0 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?
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 isn't this a special case of set cover but not exactly set cover so this might be solvable right
•  » » » » 7 years ago, # ^ |   +6 How is it a special case?
 » 7 years ago, # | ← Rev. 2 →   0 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.
•  » » 7 years ago, # ^ |   0 Algorithm X find any solution but not the minimum solution .
 » 7 years ago, # |   +3 if n is less than 20 you can solve it with dp+bitmask