A Faster FPTAS for Knapsack Problem with Cardinality Constraint.
Wenxin LiJoohyun LeeNess B. ShroffPublished in: WAOA (2020)
Keyphrases
- knapsack problem
- cardinality constraints
- lp relaxation
- dynamic programming
- optimization problems
- optimal solution
- np hard
- approximation algorithms
- functional dependencies
- exact algorithms
- greedy algorithm
- integrity constraints
- deductive databases
- implicit enumeration
- entity relationship
- database
- database schema
- cutting plane
- closed sets
- linear programming