Lower Bounds on Dynamic Programming for Maximum Weight Independent Set.
Tuukka KorhonenPublished in: ICALP (2021)
Keyphrases
- independent set
- lower bound
- maximum weight
- dynamic programming
- np hard
- upper bound
- minimum weight
- bipartite graph
- objective function
- weighted graph
- partial order
- maximum independent set
- randomized algorithm
- single machine
- worst case
- state space
- greedy algorithm
- optimal solution
- knapsack problem
- vc dimension
- scheduling problem
- greedy heuristic
- special case