Facility Locations

The HDWBP Inc. has $n$ clients and needs to service these clients by opening $k$ facilities. Each opened facility can serve any number of clients and each client must be served by an open facility. There are $m$ potential locations for these $k$ facilities. The cost of serving client $j$ at potential location $i$ is a non-negative integer c_{ij}. These costs satisfy a locality property: for two clients $j$ and j_0 and two facilities $i$ and i_0, we have c_{ij} \leq c_{i_0 j} + c_{i_0 j_0} + c_{i j_0}. Given the costs, the CEO of HDWBP Inc. ultimately wants to know the cheapest way to open $k$ facilities and assign clients to these open facilities. For now, he needs your help to determine if it is possible to do this task without any cost (i.e. with cost zero).