Approximation Algorithms for Submodular Data Summarization with a Knapsack Constraint.
Kai HanShuang CuiTianshuai ZhuEnpei ZhangBenwei WuZhizhuo YinTong XuShaojie TangHe HuangPublished in: Proc. ACM Meas. Anal. Comput. Syst. (2021)
Keyphrases
- approximation algorithms
- data summarization
- np hard
- worst case
- data analysis
- special case
- greedy algorithm
- data mining
- knapsack problem
- multidimensional data
- minimum cost
- vertex cover
- facility location problem
- primal dual
- approximation ratio
- upper bound
- randomized algorithms
- network design problem
- stream processing
- open shop
- dynamic programming
- objective function
- set cover
- scheduling problem
- optimal solution
- real world
- energy minimization
- lower bound
- optimization problems
- polynomial time approximation
- machine learning
- disjoint paths
- constant factor approximation