Computation and Complexity of Preference Inference Based on Hierarchical Models
Authors: Nic Wilson, Anne-Marie George, Barry O'Sullivan
IJCAI 2015 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We show that this problem is co NP-complete, even if one restricts the cardinality of the equal-importance sets to have at most two elements, and one only considers non-strict preferences. However, it is polynomial if it is assumed that the user s ordering of criteria is a total ordering; it is also polynomial if the sets of equally important criteria are all equivalence classes of a given fixed equivalence relation. We give an efficient polynomial algorithm for these cases, which also throws light on the structure of the inference. |
| Researcher Affiliation | Academia | Nic Wilson, Anne-Marie George and Barry O Sullivan Insight Centre for Data Analytics, School of Computer Science and IT University College Cork, Ireland {nic.wilson, annemarie.george, barry.osullivan}@insight-centre.org, |
| Pseudocode | Yes | Function Cons-check(Γ, C) H () for k = 1, . . . , |C| do if c C σ(H) such that Opp(c) Supp(H) then choose some such c; H H + c else stop end for return H |
| Open Source Code | No | The paper does not provide CONCRETE ACCESS TO SOURCE CODE (specific repository link, explicit code release statement, or code in supplementary materials) for the methodology described in this paper. |
| Open Datasets | No | The paper does not provide CONCRETE ACCESS INFORMATION (specific link, DOI, repository name, formal citation with authors/year, or reference to established benchmark datasets) for a publicly available or open dataset. |
| Dataset Splits | No | The paper does not provide SPECIFIC DATASET SPLIT INFORMATION (exact percentages, sample counts, citations to predefined splits, or detailed splitting methodology) needed to reproduce the data partitioning, as it does not describe empirical experiments on a dataset. |
| Hardware Specification | No | The paper does not provide SPECIFIC HARDWARE DETAILS (exact GPU/CPU models, processor types with speeds, memory amounts, or detailed computer specifications) used for running its experiments. |
| Software Dependencies | No | The paper does not provide SPECIFIC ANCILLARY SOFTWARE DETAILS (e.g., library or solver names with version numbers like Python 3.8, CPLEX 12.4) needed to replicate the experiment. |
| Experiment Setup | No | The paper does not contain SPECIFIC EXPERIMENTAL SETUP DETAILS (concrete hyperparameter values, training configurations, or system-level settings) in the main text. |