Maximum Coverage with Cluster Constraints: An LP-Based Approximation Technique

G. Schäfer, B.G. Zweers

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

© 2021, Springer Nature Switzerland AG.Packing problems constitute an important class of optimization problems. However, despite the large number of variants that have been studied in the literature, most packing problems encompass a single tier of capacity restrictions only. For example, in the Multiple Knapsack Problem, we want to assign a selection of items to multiple knapsacks such that their capacities are not exceeded. But what if these knapsacks are partitioned into clusters, each imposing an additional (aggregated) capacity restriction on the knapsacks contained in that cluster? In this paper, we study the Maximum Coverage Problem with Cluster Constraints (MCPC), which generalizes the Maximum Coverage Problem with Knapsack Constraints (MCPK) by incorporating such cluster constraints. Our main contribution is a general LP-based technique to derive approximation algorithms for such cluster capacitated problems. Our technique basically allows us to reduce the cluster capacitated problem to the respective original packing problem. By using an LP-based approximation algorithm for the original problem, we can then obtain an effective rounding scheme for the problem, which only loses a small fraction in the approximation guarantee. We apply our technique to derive approximation algorithms for MCPC. To this aim, we develop an LP-based 12(1-1e) -approximation algorithm for MCPK by adapting the pipage rounding technique. Combined with our reduction technique, we obtain a 13(1-1e) -approximation algorithm for MCPC. We also derive improved results for a special case of MCPC, the Multiple Knapsack Problem with Cluster Constraints (MKPC). Based on a simple greedy algorithm, our approach yields a 13 -approximation algorithm. By combining our technique with a more sophisticated iterative rounding approach, we obtain a 12 -approximation algorithm for certain special cases of MKPC.
Original languageEnglish
Title of host publicationApproximation and Online Algorithms - 18th International Workshop, WAOA 2020, Revised Selected Papers
EditorsC. Kaklamanis, A. Levin
PublisherSpringer Science and Business Media Deutschland GmbH
Pages63-80
ISBN (Print)9783030808785
DOIs
Publication statusPublished - 2021
Event18th International Workshop on Approximation and Online Algorithms, WAOA 2019 - Virtual, Online
Duration: 9 Sept 202010 Sept 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference18th International Workshop on Approximation and Online Algorithms, WAOA 2019
CityVirtual, Online
Period9/09/2010/09/20

Fingerprint

Dive into the research topics of 'Maximum Coverage with Cluster Constraints: An LP-Based Approximation Technique'. Together they form a unique fingerprint.

Cite this