---
title: "Backbones in Optimization and Approximation"
authors:
  - "John K. Slaney"
  - "Toby Walsh"
doi: ""
url: "https://ijcai.org/proceedings/2001/36"
pdf: "https://ijcai.org/proceedings/2001/0036.pdf"
venue: "Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence"
year: 2001
pages: "254-258"
track: ""
keywords:
---

# Backbones in Optimization and Approximation

John K. Slaney, Toby Walsh

*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.