Approximation Algorithms for Submodular Data Summarization with a Knapsack Constraint.
Kai HanShuang CuiTianshuai ZhuEnpei ZhangBenwei WuZhizhuo YinTong XuShaojie TangHe HuangPublished in: SIGMETRICS (Abstracts) (2021)
Keyphrases
- approximation algorithms
- data summarization
- np hard
- special case
- worst case
- data mining
- knapsack problem
- data analysis
- multidimensional data
- greedy algorithm
- vertex cover
- set cover
- network design problem
- minimum cost
- dynamic programming
- facility location problem
- approximation ratio
- stream processing
- upper bound
- objective function
- primal dual
- optimal solution
- randomized algorithms
- constant factor
- energy minimization
- open shop
- approximation guarantees
- constant factor approximation
- real world
- lower bound
- greedy heuristic
- combinatorial auctions
- similarity search
- nearest neighbor
- disjoint paths
- databases