Dominance Certificates for Combinatorial Optimization Problems

Daniel Berend (), Steven S. Skiena () and Yochai Twitto ()
Additional contact information
Daniel Berend: Ben-Gurion University
Steven S. Skiena: Stony Brook University
Yochai Twitto: Ben-Gurion University

A chapter in Optimization Problems in Graph Theory, 2018, pp 107-122 from Springer

Abstract: 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.

Date: 2018
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-3-319-94830-0_6

Ordering information: This item can be ordered from
http://www.springer.com/9783319948300

DOI: 10.1007/978-3-319-94830-0_6

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().