Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness.
Wojciech NadaraMarcin PilipczukRoman RabinovichFelix ReidlSebastian SiebertzPublished in: SEA (2018)
Keyphrases
- empirical evaluation
- approximation algorithms
- graph coloring
- np hard
- combinatorial problems
- job shop scheduling
- special case
- constraint satisfaction problems
- vertex cover
- worst case
- phase transition
- scheduling problem
- approximation ratio
- max sat
- constraint programming
- constant factor
- randomized algorithms
- hyper heuristics
- greedy algorithm
- cost function