TY - GEN
T1 - Maximum Coverage with Cluster Constraints
T2 - 18th International Workshop on Approximation and Online Algorithms, WAOA 2019
AU - Schäfer, G.
AU - Zweers, B.G.
PY - 2021
Y1 - 2021
N2 - © 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.
AB - © 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.
U2 - 10.1007/978-3-030-80879-2_5
DO - 10.1007/978-3-030-80879-2_5
M3 - Conference contribution
SN - 9783030808785
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 63
EP - 80
BT - Approximation and Online Algorithms - 18th International Workshop, WAOA 2020, Revised Selected Papers
A2 - Kaklamanis, C.
A2 - Levin, A.
PB - Springer Science and Business Media Deutschland GmbH
Y2 - 9 September 2020 through 10 September 2020
ER -