On Constrained Minimum Weight Edge Covers With Applications to Emergency Planning

In this paper we present a new covering problem, called Min Cost q-Single Location Cover, where we are given a fixed positive integer q, a finite ground set J, an integral positive demand dj$ for each element j is an element of J, a collection J of subsets of J, an integral positive cost cS and an integral positive capacity value qS <= q for each subset S is an element of J. The task is to choose sets from J, with multiple choices being allowed, such that each element j is an element of J is covered at least dj times. However, if a given subset is chosen to cover an element, it must already cover the entire demand of the element. Moreover, each subset S is an element of J may only cover up to qS of its elements, where again multiple choices are allowed. Our problem is motivated by a healthcare application for placing emergency doctors into facilities such that all emergencies occurring in a shift can be handled in a satisfactory manner. We show that Min Cost q-Single Location Cover can be solved in polynomial time for q=1,2, but is strongly NP-complete for q >= 3. To handle the case where q equals two, we introduce a new constrained b-edge cover problem in an edge-colored graph, called Minimum Weight b-Edge Cover with Colors. We analyze the complexity of this problem for general graphs as well as for the special instances resulting from an instance of q-Single Location Cover.