Backbones in Optimization and Approximation
Date
2001
Authors
Slaney, John K
Walsh, Toby
Journal Title
Journal ISSN
Volume Title
Publisher
Morgan Kauffman Publishers
Abstract
We study the impact of backbones in optimization and approximation problems. We show that some optimization problems like graph coloring resemble decision problems, with problem hardness positively correlated with backbone size. For other optimization pro
Description
Keywords
Keywords: Approximate solution; Approximation problems; Decision problems; Graph colorings; Number partitioning; Optimization problems; Problem hardness; Traveling salesperson problem; Artificial intelligence; Hardness; Optimization
Citation
Collections
Source
IJCAI-01: Proceedings of the 17th International Joint Conference on Artificial Intelligence
Type
Conference paper