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.
Original language | English |
---|---|
Pages (from-to) | 254-259 |
Number of pages | 6 |
Journal | IJCAI International Joint Conference on Artificial Intelligence |
Publication status | Published - 2001 |
Event | 17th International Joint Conference on Artificial Intelligence, IJCAI 2001 - Seattle, WA, United States Duration: 4 Aug 2001 → 10 Aug 2001 |