On Constrained Minimum Weight Edge Covers With Applications to Emergency Planning

ABSTRACT In this paper we present a new covering problem, called Min Cost ‐Single Location Cover , where we are given a fixed positive integer , a finite ground set , an integral positive demand for each element , a collection of subsets of , an integral positive cost and an integral positive capacity value for each subset . The task is to choose sets from , with multiple choices being allowed, such that each element is covered at least 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 may only cover up to 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 ‐Single Location Cover can be solved in polynomial time for , but is strongly NP‐complete for . To handle the case where equals two, we introduce a new constrained ‐edge cover problem in an edge‐colored graph, called Minimum Weight ‐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 ‐Single Location Cover.