Priority algorithms for the subset-sum problem.
Published: 2006
Language: eng
Number of pages: 60
ISBN-13: 9780494210710
Description: Priority algorithms capture the key notion of "greediness'' in the sense that they process the "best" data item one at a time, depending on the current knowledge of the input, while keeping a feasible solution for the output. Although priority algorithms are often simple to state, their relative power is not completely understood. In this thesis, we study priority algorithms for the Subset-Sum Problem. In particular, several variants of priority algorithms: revocable versus irrevocable, fixed versus adaptive, non-increasing order versus non-decreasing order; are analyzed and corresponding lower bounds are provided.
Notes: Source: Masters Abstracts International, Volume: 45-03, page: 1545.

Advisor: Allan Borodin.

Thesis (M.Sc.)--University of Toronto, 2006.

Electronic version licensed for access by U. of T. users.

ROBARTS MICROTEXT copy on microfiche.