EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Greedy algorithms with imprecise oracles for submodular knapsack problems

Sabine Münch, Stephen Raach

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →