Everyone is welcome to attend the on-line lecture of Bernard Zweers (CWI) entitled: Maximum Coverage with Cluster Constraints: An LP-Based Approximation Technique.
The meeting will take place on zoom:
https://us02web.zoom.us/j/89018344147
Abstract:
Many optimization problems encountered in real-life can be modeled as a packing, where a set of various items need to be packed into a limited number of bins such that certain feasibility constraints are satisfied. Given their high practical relevance, there is a large variety of packing problems that have been studied in the literature, for example, the Multiple Knapsack Problem or the Maximum Coverage Problem with Knapsack constraint. We study these two problems with a new additional feature, namely the knapsacks are partitioned into clusters, and each cluster has an associated capacity. In this talk, we will give an LP-based approximation algorithm for the Multiple Knapsacks with Cluster constraints. The approximation ratio of this algorithm is 1/3. However, we will also show that by applying iterative rounding, this ratio can be improved to 1/2 for instances that satisfy a specific property. Finally, we will show that this approach, in combination with pipage rounding, results in a 1/3(1-1/e)-approximation algorithm for the Maximum Coverage Problem with Cluster constraints.
