Faculties
DE / EN

## 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

### Publications

• Maximizing a Submodular Function with Bounded Curvature Under an Unknown Knapsack Constraint ( and )
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$.