2021-07-01-amanatidis21a.md

title	abstract	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	address	container-title	volume	genre	issued	pdf	extras
Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity	The growing need to deal with massive instances motivates the design of algorithms balancing the quality of the solution with applicability. For the latter, an important measure is the \emph{adaptive complexity}, capturing the number of sequential rounds of parallel computation needed. In this work we obtain the first \emph{constant factor} approximation algorithm for non-monotone submodular maximization subject to a knapsack constraint with \emph{near-optimal} $O(\log n)$ adaptive complexity. Low adaptivity by itself, however, is not enough: one needs to account for the total number of function evaluations (or value queries) as well. Our algorithm asks $\tilde{O}(n^2)$ value queries, but can be modified to run with only $\tilde{O}(n)$ instead, while retaining a low adaptive complexity of $O(\log^2n)$. Besides the above improvement in adaptivity, this is also the first \emph{combinatorial} approach with sublinear adaptive complexity for the problem and yields algorithms comparable to the state-of-the-art even for the special cases of cardinality constraints or monotone objectives. Finally, we showcase our algorithms’ applicability on real-world datasets.	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	amanatidis21a	0	Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity	231	242	231-242	231	false	Amanatidis, Georgios and Fusco, Federico and Lazos, Philip and Leonardi, Stefano and Marchetti-Spaccamela, Alberto and Reiffenh{\"a}user, Rebecca	given family Georgios Amanatidis given family Federico Fusco given family Philip Lazos given family Stefano Leonardi given family Alberto Marchetti-Spaccamela given family Rebecca Reiffenhäuser	2021-07-01		Proceedings of the 38th International Conference on Machine Learning	139	inproceedings	date-parts 2021 7 1	http://proceedings.mlr.press/v139/amanatidis21a/amanatidis21a.pdf	label link Supplementary PDF http://proceedings.mlr.press/v139/amanatidis21a/amanatidis21a-supp.pdf