EURO 2025 Leeds
Abstract Submission

2898. On Generalizations of Partial Scenario Set Cover

Invited abstract in session WC-20: Topics in Combinatorial Optimization 2, stream Combinatorial Optimization.

Wednesday, 12:30-14:00
Room: Esther Simpson 2.11

Authors (first author is the speaker)

1. Shai Dimant
Department Mathematics, AG OPT, RPTU Kaiserslautern

Abstract

In the Partial Scenario Set Cover problem (PSSC), given a finite ground set Q, a collection S of subsets of Q with associated nonnegative costs, and a second collection U of subsets of Q, the goal is to select a minimum-cost sub-collection of S that covers at least l sets from U. PSSC is motivated by an application for locating emergency doctors, which is driven by robust optimization, where the collection U corresponds to an uncertainty set and its elements to scenarios. Here, the aim is to cover at least a certain number l of scenarios by a minimum cost choice of locations.

Here, we consider the following natural generalization of PSSC, called Partial PSSC (PPSSC). Each scenario has a demand that specifies the number of elements that must be covered. The task is to find a minimum-cost sub-collection of S that satisfies the demand of at least l scenarios. PSSC and PPSSC are at least as hard to approximate as the Minimum k-Union problem, which is believed not to admit a subpolynomial approximation ratio. Our contributions include an approximation algorithm for general instances of PPSSC and polynomial-time algorithms for interesting graph-theoretic versions of the problem.

Keywords

Status: accepted

Back to the list of papers