Backbones in Optimization and Approximation
Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence. Pages 254-258.
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 problems like blocks world planning and traveling salesperson problems, problem hardness is weakly and negatively correlated with backbone size, while the cost of finding optimal and approximate solutions is positively correlated with backbone size. A third class of optimization problems like number partitioning have regions of both types of behavior. We find that to observe the impact of backbone size on problem hardness, it is necessary to eliminate some symmetries, perform trivial reductions and factor out the effective problem size.
@inproceedings{ijcai2001p36,
title = {Backbones in Optimization and Approximation},
author = {Slaney, John K. and Walsh, Toby},
booktitle = {Proceedings of the Seventeenth International Joint Conference on
Artificial Intelligence, {IJCAI-01}},
publisher = {International Joint Conferences on Artificial Intelligence},
pages = {254--258},
year = {2001},
url = {https://ijcai.org/proceedings/2001/36},
}
TY - CPAPER TI - Backbones in Optimization and Approximation AU - Slaney, John K. AU - Walsh, Toby T2 - Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, IJCAI-01 PB - International Joint Conferences on Artificial Intelligence PY - 2001 SP - 254 EP - 258 UR - https://ijcai.org/proceedings/2001/36 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
