Name
Abstract | ||
|---|---|---|
In this paper, we consider the problem of maximizing a monotone submodular function subject to a cardinality constraint, with two added twists: The computation is distributed across a number of machines, and we require the solution to be robust against adversarial removals. We provide two versions of a partitioned robust algorithm for this problem, with the difference amounting to whether or not the centralized machine is informed (only in the final stage of the algorithm) which elements will be removed. In both of these cases, we provide a novel constant-factor approximation guarantee with respect to the optimal algorithm. Finally, we validate our algorithms via numerical experiments on real-world data sets in influence maximization and data summarization. |
Year | Venue | Field |
|---|---|---|
2017 | 2017 IEEE 7TH INTERNATIONAL WORKSHOP ON COMPUTATIONAL ADVANCES IN MULTI-SENSOR ADAPTIVE PROCESSING (CAMSAP) | Automatic summarization,Approximation algorithm,Mathematical optimization,Computer science,Cardinality,Submodular set function,Robustness (computer science),Distributed algorithm,Monotone polygon,Maximization |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ilija Bogunovic | 1 | 29 | 7.33 |
| Slobodan Mitrović | 2 | 30 | 7.68 |
| Jonathan Scarlett | 3 | 163 | 31.49 |
| Volkan Cevher | 4 | 1860 | 141.56 |