2026-08-13T18:49:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21173 2024-09-23T09:13:18Z ddc:004 open_access

SubModST: A Fast Generic Solver for Submodular Maximization with Size Constraints Woydt, Henning Martin Komusiewicz, Christian Sommer, Frank Branch-and-Cut Lazy Evaluations Facility Location Group Closeness Centrality Partial Dominating Set In the Cardinality-Constrained Maximization (Minimization) problem the input is a universe 𝒰, a function f: 2^{{𝒰}} → ℝ, and an integer k, and the task is to find a set S ⊆ 𝒰 with |S| ≤ k that maximizes (minimizes) f(S). Many well-studied problems such as Facility Location, Partial Dominating Set, Group Closeness Centrality and Euclidean k-Medoid Clustering are special cases of Cardinality-Constrained Maximization (Minimization). All the above-mentioned problems have the diminishing return property, that is, the improvement of adding an element e ∈ 𝒰 to a set S is at least as large as adding e to any superset of S. This property is called submodularity for maximization problems and supermodularity for minimization problems. In this work we develop a new exact branch-and-cut algorithm SubModST for the generic Submodular Cardinality-Constrained Maximization and Supermodular Cardinality-Constrained Minimization. We develop several speed-ups for SubModST and we show their effectiveness on six example problems. We show that SubModST outperforms the state-of-the-art solvers developed by Csókás and Vinkó [J. Glob. Optim. '24] and Uematsu et al. [J. Oper. Res. Soc. Japan '20] for Submodular Cardinality-Constrained Maximization by orders of magnitudes. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Henning Martin Woydt and Christian Komusiewicz and Frank Sommer 2024 Is Part Of LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2024.102 urn:nbn:de:0030-drops-211730 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.102 eng https://creativecommons.org/licenses/by/4.0/legalcode