A Nearly Quadratic-Time FPTAS for Knapsack.
Lin ChenJiayi LianYuchen MaoGuochuan ZhangPublished in: STOC (2024)
Keyphrases
- knapsack problem
- dynamic programming
- computational complexity
- approximation algorithms
- objective function
- packing problem
- pairwise
- timed automata
- upper bound
- special case
- optimal solution
- penalty functions
- feasible solution
- face recognition
- database systems
- three dimensional
- multiple choice
- quadratic program
- e learning