Name
Abstract | ||
|---|---|---|
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.
|
Year | DOI | Venue |
|---|---|---|
2019 | 10.1145/3292500.3330911 | KDD |
Keywords | Field | DocType |
distributed algorithms, streaming algorithms, submodular maximization | Mathematical optimization,Streaming algorithm,Computer science,Submodular maximization,Distributed algorithm,Artificial intelligence,Knapsack problem,Machine learning | Journal |
Volume | ISBN | Citations |
abs/1905.02367 | 978-1-4503-6201-6 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dmitry Avdyukhin | 1 | 2 | 2.08 |
| Slobodan Mitrović | 2 | 30 | 7.68 |
| Grigory Yaroslavtsev | 3 | 209 | 17.36 |
| Samson Zhou | 4 | 25 | 16.01 |