Greedy algorithms with imprecise oracles for submodular knapsack problems
Mathematical Methods of Operations Research · 05.11.2026
DOI: 10.1007/s00186-026-00947-1 ↗Kurz gefasst
Fachartikel in der Zeitschrift Mathematical Methods of Operations Research, online erschienen am 05.11.2026. Verfasst von Sabine Münch und 1 weiteren Autor:innen. Die Arbeit nennt 22 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Universität Trier.
Abstract (Originalsprache)
We consider the problem of maximizing a monotone increasing, normalized, and submodular function defined over a set of elements with associated weights under a knapsack constraint. A well-known greedy algorithm, analyzed by Wolsey (1982), achieves an approximation factor of $$\varvec{0.357}$$ 0.357 for this problem. This greedy algorithm starts with an empty solution set and iteratively adds elements with maximum relative marginal gain to the current solution, stopping when adding the next element would violate the knapsack constraint. Then it compares the objective value of the current solution set to that of the element that exceeded the knapsack constraint and returns the one with the greater objective value. Therefore, this algorithm relies on the existence of an exact incremental oracle that identifies, in each iteration, an element with maximum relative marginal gain to the current solution. We generalize the known approximation result for this greedy algorithm to the presence of only an approximate incremental oracle that identifies in iteration $$\varvec{i}$$ i of the greedy algorithm an element whose relative marginal gain is at least a $$\varvec{\frac{1}{\alpha _i}}$$ 1 α i -fraction, with $$\varvec{\alpha _i \ge 1}$$ α i ≥ 1 , of the maximum relative marginal gain. Furthermore, we present an approximation result for a variant of the greedy algorithm in which an approximate incremental oracle is used in the first iteration of the greedy algorithm, and an exact incremental oracle is used in all subsequent iterations.
Förderung
- Universität Trier
Zitieren
APA
Münch, S., & Raach, S. (2026). Greedy algorithms with imprecise oracles for submodular knapsack problems. Mathematical Methods of Operations Research. https://doi.org/10.1007/s00186-026-00947-1
Vancouver
Münch S, Raach S. Greedy algorithms with imprecise oracles for submodular knapsack problems. Mathematical Methods of Operations Research. 2026. doi:10.1007/s00186-026-00947-1
BibTeX
@article{Mnch2026,
author = {Münch, Sabine and Raach, Stephen},
title = {Greedy algorithms with imprecise oracles for submodular knapsack problems},
journal = {Mathematical Methods of Operations Research},
year = {2026},
doi = {10.1007/s00186-026-00947-1}
}
EUVIMED