Martin Knaack
Research assistant
Fakultät II - Mathematik und Naturwissenschaften
Institut für Mathematik
Technische Universität Berlin
Straße des 17. Juni 136
10623 Berlin
Office: MA 514
Telephone: +49 30 314 78657
Email: (lastname)@math.tu-berlin.de
Teaching
Publications
2022
- Maximizing a Submodular Function with Bounded Curvature Under an Unknown Knapsack Constraint (Max Klimm and Martin Knaack)
APPROX 2022 – Proc. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems.
@inproceedings{KlimmKnaack2022,
author = {Max Klimm and Martin Knaack},
title = {Maximizing a Submodular Function with Bounded Curvature Under an Unknown Knapsack Constraint},
booktitle = {APPROX 2022 – Proc. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems},
year = {2022},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.49},
accepted = {22.06.2022},
}
This paper studies the problem of maximizing a monotone submodular function under an unknown knapsack constraint. A solution to this problem is a policy that decides which item to pack next based on the past packing history. The robustness factor of a policy is the worst case ratio of the solution obtained by following the policy and an optimal solution that knows the knapsack capacity. We develop an algorithm with a robustness factor that is decreasing in the curvature $c$ of the submodular function. For the extreme cases $c = 0$ corresponding to a modular objective, it matches a previously known and best possible robustness factor of $1/2$. For the other extreme case of $c = 1$ it yields a robustness factor of $\approx 0.35$ improving over the best previously known robustness factor of $\approx 0.06$.
