Cardinality-Constrained Continuous Knapsack Problem with Concave Piecewise-Linear Utilities
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911771182235648 |
|---|---|
| author | Bai, Miao Cardonha, Carlos |
| author_facet | Bai, Miao Cardonha, Carlos |
| contents | We study an extension of the cardinality-constrained knapsack problem wherein each item has a concave piecewise linear utility structure (CCKP), which is motivated by applications such as resource management problems in monitoring and surveillance tasks. Our main contributions are combinatorial algorithms for the offline CCKP and an online version of the CCKP. For the offline problem, we present a fully polynomial-time approximation scheme and show that it can be cast as the maximization of a submodular function with cardinality constraints; the latter property allows us to derive a greedy $(1 - \frac{1}{e})$-approximation algorithm. For the online CCKP in the random order model, we derive a $\frac{10.427}α$-competitive algorithm based on $α$-approximation algorithms for the offline CCKP; moreover, we derive stronger guarantees for the cases wherein the cardinality capacity is very small or relatively large. Finally, we investigate the empirical performance of the proposed algorithms in numerical experiments. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_03781 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Cardinality-Constrained Continuous Knapsack Problem with Concave Piecewise-Linear Utilities Bai, Miao Cardonha, Carlos Data Structures and Algorithms 68W25 We study an extension of the cardinality-constrained knapsack problem wherein each item has a concave piecewise linear utility structure (CCKP), which is motivated by applications such as resource management problems in monitoring and surveillance tasks. Our main contributions are combinatorial algorithms for the offline CCKP and an online version of the CCKP. For the offline problem, we present a fully polynomial-time approximation scheme and show that it can be cast as the maximization of a submodular function with cardinality constraints; the latter property allows us to derive a greedy $(1 - \frac{1}{e})$-approximation algorithm. For the online CCKP in the random order model, we derive a $\frac{10.427}α$-competitive algorithm based on $α$-approximation algorithms for the offline CCKP; moreover, we derive stronger guarantees for the cases wherein the cardinality capacity is very small or relatively large. Finally, we investigate the empirical performance of the proposed algorithms in numerical experiments. |
| title | Cardinality-Constrained Continuous Knapsack Problem with Concave Piecewise-Linear Utilities |
| topic | Data Structures and Algorithms 68W25 |
| url | https://arxiv.org/abs/2302.03781 |