This is a homework problem, so I don't want the solution. I need a hint which problem to reduce to the following and/or how to start on it. We were thinking of TSP or independent set but couldn't come up with a solution.

We have $i\ldots j$ stores and $i\ldots n$ possible places to build a new warehouse. Costs to build a new warehouse are $c_j$. Between each store and warehouse is a path of cost $d_{i,j}$. Every store needs to be connected to at least one warehouse.

The decision problem is: is there a set of warehouses and paths so that the sum is smaller than a given number $k$.


This is a classic facility location problem. That Wikipedia article suggests that NP-hardness can be proven by reduction from set cover.

Since the asker has now stated to have found a solution by reducing from vertex cover, I will go ahead and reveal the reduction from set cover:

For each value, create a store; for each set, create a warehouse. Assign the cost of each warehouse to be 1. Assign the cost of the route from a warehouse to a store to be an arbitrarily small value if that warehouse's set contains that store's value, or an arbitrarily large value otherwise. Then the minimum cost solution to the facility problem builds precisely the set of warehouses corresponding to the minimum set cover in the original problem.

The $k$ value is used to turn the optimization problem (minimize sets/cost) into a decision problem (is there a solution with no more than $k$ sets/cost?). The $k$ from the set cover instance will be the same as the $k$ in the facility problem instance if you are allowed to set the "arbitrarily small" values to exactly 0 - otherwise you might have to fudge the value by some amount, but less than 1 as long as you pick the "arbitrarily small" weights to be small enough. You just need the total of every "arbitrarily small" cost to be less than 1, and every "arbitrarily large" cost to be greater than the sum of the costs of all the warehouses and all the "arbitrarily small" routes.

Note that, if only integer costs are allowed in the facilities problem, you can still achieve the same result by scaling all the costs by their least common multiple.

| cite | improve this answer | |
  • $\begingroup$ Thanks for the name of the problem! I tried for a while and I think vertex cover is a way easier approach tbh. $\endgroup$ – user106782 Dec 11 '19 at 15:08
  • $\begingroup$ @Marcel B See my edit for the set cover solution. $\endgroup$ – Aaron Rotenberg Dec 11 '19 at 15:44
  • $\begingroup$ Wow okay I used exactly that as my first approach, but I wasn't sure why assigning those weights would make any sense! Thanks, Aaron. $\endgroup$ – user106782 Dec 11 '19 at 15:55
  • $\begingroup$ Okay, one more questions. Looking at Set Cover I will be given a family of sets, a unity over all sets and a limit k. How does the k, which in SC case corresponds to the amount of sets (so the warehouses), translate to the cost k over my facility problem? Also I'm quite confused when it comes to translating does weights? How can I just ignore them. $\endgroup$ – user106782 Dec 11 '19 at 16:00
  • $\begingroup$ This is something Im quite unsure for my VC solution as well. Most trouble for me $\endgroup$ – user106782 Dec 11 '19 at 16:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy