Approximation algorithms for energy, reliability and makespan optimization problems
Guillaume AupyAnne BenoitPublished in: CoRR (2012)
Keyphrases
- approximation algorithms
- optimization problems
- open shop
- np hard
- strongly np hard
- evolutionary algorithm
- scheduling problem
- special case
- vertex cover
- metaheuristic
- energy minimization
- network design problem
- lower bound
- worst case
- cost function
- objective function
- set cover
- optimal solution
- randomized algorithms
- facility location problem
- approximation ratio
- minimum cost
- primal dual
- knapsack problem
- traveling salesman problem
- precedence constraints
- combinatorial optimization
- np hardness
- integer programming
- job shop
- disjoint paths
- approximation schemes
- simulated annealing
- polynomial time approximation
- undirected graph
- constant factor
- convex hull
- computational complexity
- search algorithm
- linear program
- constant factor approximation