ISBN 9783843958226

978-3-8439-5822-6, Reihe Mathematik

Shai Michael Dimant
On Partial Scenario Set Cover and Beyond

225 Seiten, Dissertation Rheinland-Pfälzische Technische Universität Kaiserslautern-Landau (2026), Hardcover, A5

Zusammenfassung / Abstract

This thesis studies partial scenario covering problems. A classical and well-studied covering problem is Set Cover. In this problem, one is given a finite ground set of elements together with a collection of its subsets and a cost for each subset. The task is to choose a minimum-cost sub-collection of subsets such that every element is contained in at least one chosen set.

This problem can be generalized in two steps to obtain the corresponding partial scenario version. First, the covering constraint can be relaxed: instead of covering all elements, one may require only a specified number of elements to be covered. This yields the Partial Set Cover problem. Second, uncertainty can be introduced by considering a collection of scenarios, each specifying a subset of elements that would have to be covered if that scenario occurred. We may then ask for a minimum-cost sub-collection that fully covers a specified number of scenarios. This yields the Partial Scenario Set Cover problem (PSSC).

Since many classical covering problems, including Set Cover, are NP-hard, their partial scenario variants are generally not expected to admit exact polynomial-time algorithms. We therefore study them from the perspective of approximation algorithms, hardness of approximation, and structural tractability. We derive approximation and hardness results for PSSC and for partial scenario versions of several classical covering and network design problems. Moreover, we develop approximation algorithms for generalizations of PSSC. For many of the studied problems, we obtain the first non-trivial single-criterion approximation algorithms. In addition, we study graph-based partial scenario covering problems and obtain polynomial-time exact algorithms for special cases with restricted graph and scenario structure.