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.

The Partial Scenario Set Cover problem (PSSC) generalizes the Partial Set Cover problem, which is itself a generalization of the classical Set Cover problem. We are given a finite ground set Q , a collection S of subsets of Q to choose from, each of which is associated with a nonnegative cost, and a second collection U of subsets of Q of which a given number l must be covered. The task is to choose a minimum cost sub-collection from S that covers at least l sets from U . PSSC is motivated by an application for locating emergency doctors. We present two approximation approaches. The first one combines LP-based rounding with a greedy consideration of the scenarios. The other is a variant of the greedy set cover algorithm, and in each iteration tries to minimize the ratio of cost to number of newly covered scenarios. We show that this subproblem, which we call Dense Scenario Set Cover (DSSC), is itself as hard to approximate as Set Cover and NP-hard, even when there is only a single scenario and all sets contain at most three elements. Furthermore, we consider a special case of DSSC where the sets are pairwise disjoint and show that in this case DSSC can be solved in polynomial time. We also provide an approximation for the general case, which we use as a subroutine in the greedy algorithm to obtain an approximation for PSSC.