Maximizing a Submodular Function with Bounded Curvature under an Unknown Knapsack Constraint
| Autor: | Klimm, Max, Knaack, Martin |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: |
FOS: Computer and information sciences
knapsack Mathematics of computing → Submodular optimization and polymatroids Discrete Mathematics (cs.DM) Computer Science - Data Structures and Algorithms robust optimization Data Structures and Algorithms (cs.DS) Theory of computation → Online algorithms submodular function approximation algorithm Theory of computation → Packing and covering problems Computer Science - Discrete Mathematics |
| Popis: | 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 ≈ 0.35 improving over the best previously known robustness factor of ≈ 0.06. LIPIcs, Vol. 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022), pages 49:1-49:19 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|