Research

Adversarially Robust Submodular Maximization under Knapsack Constraints

KDD

Authors

  • Dmitrii Avdiukhin
  • Slobodan Mitrović
  • Grigory Yaroslavtsev
  • Samson Zhou

Published on

08/08/2019

We propose the first adversarially robust algorithm for monotone submodular maximization under single and multiple knapsack constraints with scalable implementations in distributed and streaming settings. For a single knapsack constraint, our algorithm outputs a robust summary of almost optimal (up to polylogarithmic factors) size, from which a constant-factor approximation to the optimal solution can be constructed. For multiple knapsack constraints, our approximation is within a constant-factor of the best known non-robust solution. We evaluate the performance of our algorithms by comparison to natural robustifications of existing non-robust algorithms under two objectives: 1) dominating set for large social network graphs from Facebook and Twitter collected by the Stanford Network Analysis Project (SNAP), 2) movie recommendations on a dataset from MovieLens. Experimental results show that our algorithms give the best objective for a majority of the inputs and show strong performance even compared to offline algorithms that are given the set of removals in advance.

Please cite our work using the BibTeX below.

@inproceedings{10.1145/3292500.3330911,
author = {Avdiukhin, Dmitrii and Mitrovi\'{c}, Slobodan and Yaroslavtsev, Grigory and Zhou, Samson},
title = {Adversarially Robust Submodular Maximization under Knapsack Constraints},
year = {2019},
isbn = {9781450362016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi-org.libproxy.mit.edu/10.1145/3292500.3330911},
doi = {10.1145/3292500.3330911},
booktitle = {Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining},
pages = {148–156},
numpages = {9},
keywords = {streaming algorithms, submodular maximization, distributed algorithms},
location = {Anchorage, AK, USA},
series = {KDD '19}
}
Close Modal