EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

487. Partial Scenario Set Cover and its Application to Emergency Planning

Invited abstract in session MD-53: Disaster & Emergency Management, stream Sustainable and Resilient Systems.

Monday, 14:30-16:00
Room: 8007 (building: 202)

Authors (first author is the speaker)

1. Shai Dimant
Department Mathematics, AG OPT, RPTU Kaiserslautern
2. Sven Krumke
Mathematics, University of Kaiserslautern

Abstract

In the classical Set Cover problem, one is 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 the goal is to choose a minimum-cost sub-collection of S whose union covers the entire ground set Q. The Set Cover problem assumes that every element of the ground set is always present. In practice, however, this may not always be the case. In the context of locating emergency facilities, the ground set corresponds to (not precisely known) emergencies. The regions in which emergencies can occur are modeled as the elements. The subset of regions in which an emergency occurs is uncertain and modeled as a scenario from the uncertainty set. For each facility, there is a set of regions that can be reached within a guaranteed response time. Following a robust optimization approach, we consider a second collection U of subsets of Q. Each set in U represents a possible scenario of the emergencies. The goal now is to choose a minimum-cost sub-collection of S such that at least a certain number of scenarios from U are covered. This leads to the Partial Scenario Set Cover problem (PSSC) which generalizes the Partial Set Cover problem, which is itself a generalization of the classical Set Cover problem. We study the complexity of PSSC, provide approximation algorithms based on LP-rounding and generalizations of the classical greedy algorithm for Set Cover.

Keywords

Status: accepted

Back to the list of papers