Adversarially Robust Submodular Maximization under Knapsack Constraints
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Beyond Pointwise Submodularity: Non-Monotone Adaptive Submodular Maximization subject to Knapsack and $k$-System Constraints
In this paper, we study the non-monotone adaptive submodular maximization problem subject to a knapsack and a $k$-system constraints. The input of our problem is a set of items, where each item has a particular state dra…
2kSubmodular Maximization under the Intersection of Matroid and Knapsack Constraints
Submodular maximization arises in many applications, and has attracted a lot of research attentions from various areas such as artificial intelligence, finance and operations research. Previous studies mainly consider on…
Movie RecommendationDistributed Submodular Maximization
Many large-scale machine learning problems--clustering, non-parametric learning, kernel machines, etc.--require selecting a small yet representative subset from a large dataset. Such problems can often be reduced to maxi…
ClusteringA Unified Framework of Constrained Robust Submodular Optimization with Applications
Robust optimization is becoming increasingly important in machine learning applications. In this paper, we study a unified framework of robust submodular optimization. We study this problem both from a minimization and m…
BIG-bench Machine Learningspeech-recognitionSpeech RecognitionRanking with submodular functions on a budget
Submodular maximization has been the backbone of many important machine-learning problems, and has applications to viral marketing, diversification, sensor placement, and more. However, the study of maximizing submodular…
Marketing