Sources of complexity in subset choice

I. Rooij, van, U. Stege, H. Kadlec

Research output: Contribution to journalArticleAcademicpeer-review

12 Citations (Scopus)
3 Downloads (Pure)

Abstract

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.
Original languageEnglish
Pages (from-to)160-187
JournalJournal of Mathematical Psychology
Volume49
Issue number2
DOIs
Publication statusPublished - 2005

Fingerprint

Dive into the research topics of 'Sources of complexity in subset choice'. Together they form a unique fingerprint.

Cite this