Daniel Berend

Heuristic algorithms, such as simulated annealing, are widely used in practice to solve combinatorial optimization problems. However, they offer no guarantees regarding the quality of the provided solution. An f(I) combinatorial dominance guarantee is a certificate that a solution is not worse than at least f(I) solutions for a particular problem instance I. In this paper, we introduce simple but general techniques for awarding combinatorial dominance certificates to arbitrary solutions of various optimization problems. We demonstrate these techniques by applying them to the Traveling Salesman and Maximum Satisfiability problems, and briefly experiment their usability.