Linear Programming and the Worst-Case Analysis of Greedy Algorithms on Cubic Graphs.
William DuckworthNicholas C. WormaldPublished in: Electron. J. Comb. (2010)
Keyphrases
- greedy algorithms
- worst case analysis
- linear programming
- greedy algorithm
- worst case
- linear programming relaxation
- greedy heuristic
- average case
- np hard
- objective function
- linear program
- dynamic programming
- knapsack problem
- np hardness
- feasible solution
- optimal solution
- integer programming
- column generation
- network flow
- search algorithm
- constraint propagation
- mathematical model
- lower bound