@inbook{30c46039a30b4a51adbe41c02702d73a,
title = "Dominance certificates for combinatorial optimization problems",
abstract = "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.",
author = "Daniel Berend and Skiena, \{Steven S.\} and Yochai Twitto",
note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG, part of Springer Nature 2018.",
year = "2018",
doi = "10.1007/978-3-319-94830-0\_6",
language = "English",
series = "Springer Optimization and Its Applications",
publisher = "Springer International Publishing",
pages = "107--122",
booktitle = "Springer Optimization and Its Applications",
}