Parameterized approximation algorithms for Partial Covering and Satisfiability with budget constraints [HBNI Th 285]

Abstract

This thesis studies parameterized approximation algorithms for partial covering problems through a unified framework centered around Maximum Coverage and CCMaxSat. We investigate two complementary optimization objectives: maximizing the number of satisfied constraints using a bounded number of selected objects, and minimizing the number of selected objects required to satisfy a prescribed number of constraints. We further extend these problems by incorporating fairness constraints on the constraints to be satisfied and matroid constraints on the selected objects, yielding a broad family of generalized optimization problems.