Sources of complexity in subset choice

Subset choice denotes the task of choosing a subset of items from among a set of available items. Because the number of possible choice options in subset choice grows exponentially with the size of the choice set, subset choice tasks can be computationally challenging. This paper discusses how the c...

Full description

Saved in:
Bibliographic Details
Published in:Journal of mathematical psychology 2005-04, Vol.49 (2), p.160-187
Main Authors: van Rooij, Iris, Stege, Ulrike, Kadlec, Helena
Format: Article
Language:English
Subjects:
Algorithms
Computational complexity
Decision-making
Fixed-parameter tractable
Intractability
NP-completeness
Subset choice
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Subset choice denotes the task of choosing a subset of items from among a set of available items. Because the number of possible choice options in subset choice grows exponentially with the size of the choice set, subset choice tasks can be computationally challenging. This paper discusses how the computational complexity of subset choice under different models can be utilized in the quest for descriptive models of subset choice. We consider several models of subset choice (including the additive model, the binary-interaction model and the h-ary interaction model) and show how the theory of computational complexity (including the theory of NP-completeness and fixed-parameter tractability) can be used to evaluate the psychological plausibility of such models under different assumptions of processing speed, parallelism and size of problem parameters.
ISSN:0022-2496
1096-0880
DOI:10.1016/j.jmp.2005.01.002