2026-08-25T17:34:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27270 2026-08-25T13:18:20Z ddc:004 open_access

Incremental Submodular Maximization: Better Than Greedy Bienkowski, Marcin Blikstad, Joakim Byrka, Jarosław Costa, Martín Disser, Yann Lutz, Annette Submodular maximization incremental optimization competitive analysis We consider submodular maximization under increasing cardinality constraint and ask for a good incremental solution, i.e., an ordering of the ground set such that each prefix of the ordering yields a good solution for its respective cardinality. A classical result in this setting is that the greedy algorithm achieves a competitive ratio, i.e., an approximation guarantee across all cardinalities, of e/(e-1) ≈ 1.582. No better general guarantee was previously known. We present an adaptive scaling algorithm achieving a competitive ratio of 1.373. We complement our result by a lower bound of 1.25 on the best possible deterministic competitive ratio for incremental submodular maximization. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Marcin Bienkowski and Joakim Blikstad and Jarosław Byrka and Martín Costa and Yann Disser and Annette Lutz 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.134 urn:nbn:de:0030-drops-272702 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.134 eng https://creativecommons.org/licenses/by/4.0/legalcode