Backbones in Optimization and Approximation

Slaney, John K; Walsh, Toby

Backbones in Optimization and Approximation

Date

2001

Authors

Slaney, John K

Walsh, Toby

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

Keywords

Keywords: Approximate solution; Approximation problems; Decision problems; Graph colorings; Number partitioning; Optimization problems; Problem hardness; Traveling salesperson problem; Artificial intelligence; Hardness; Optimization

URI

http://hdl.handle.net/1885/66932

Collections

ANU Research Publications

Source

IJCAI-01: Proceedings of the 17th International Joint Conference on Artificial Intelligence

Type

Conference paper

Full item page

Backbones in Optimization and Approximation

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

Keywords

Citation

URI

Collections

Source

Type

Book Title

Entity type

Access Statement

License Rights

DOI

Restricted until