SETH-Based Lower Bounds for Subset Sum and Bicriteria Path.
Amir AbboudKarl BringmannDanny HermelinDvir ShabtayPublished in: SODA (2019)
Keyphrases
- bicriteria
- lower bound
- shortest path problem
- efficient solutions
- shortest path
- objective function
- upper bound
- completion times
- integer linear programming
- knapsack problem
- min sum
- optimal solution
- branch and bound
- np hard
- branch and bound algorithm
- weighted sum
- manufacturing cell
- flowshop
- combinatorial optimization problems
- lagrangian relaxation
- simulated annealing
- cutting plane
- worst case
- greedy algorithm
- processing times
- tabu search
- scheduling problem