Collapsing binary data for algebraic multidimensional representation
type: Item
instance of: scholarly article
title: Collapsing binary data for algebraic multidimensional representation
zbMATH Open document ID: 0601.92030
DOI: 10.1016/0022-2496(86)90012-X
author: Charles Chubb
published in: Journal of Mathematical Psychology
publication date: 1986-01-01T00:00:00Z
review text: Let (R, \(A\times M)\) be a binary relation. The problem of algebraic representation consists in obtaining a family \(\Gamma\) of relations such that for some specified family \(\Phi\) of relations in \(A\times M\) with properties \[ \Gamma \subseteq \Phi,\quad R=\cap \Gamma,\quad (R=\cup \Gamma), \] and for any family of relations \(\Gamma\) ' satisfying the previous conditions, holds \(| \Gamma | \leq | \Gamma '|\). The task can be identified as NP-hard. The main purpose of the paper is to present a polynomially efficient procedure for extracting from an arbitrary R a distinguished restriction \(C=(\alpha \times \mu)\cap R\) such that in practical applications it frequently turns out that \(| C|\) is substantially smaller than \(| R|\), and for an important subclass of scaling techniques, the representation problem for R is polynomially reducible to the same problem for C.
Mathematics Subject Classification ID: 91E99
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 92F05
Mathematics Subject Classification ID: 03E20
zbMATH DE Number: 3970597
zbMATH Keywords: collapsing methods
zbMATH Keywords: multidimensional scaling techniques
zbMATH Keywords: binary relation
zbMATH Keywords: algebraic representation
zbMATH Keywords: NP-hard
zbMATH Keywords: polynomially efficient procedure
zbMATH Keywords: polynomially reducible
MaRDI profile type: Publication
cites work: Q4137174
cites work: Q4182539
cites work: Q3853647
cites work: Ferrers digraphs and threshold graphs
cites work: On the Ferrers dimension of a digraph
cites work: On realizable biorders and the biorder dimension of a relation
cites work: Difference measurement and simple scalability with restricted solvability
cites work: Matching relations and the dimensional structure of social choices
cites work: A note on an alternative proof of the representation theorem for bi- semiorder
cites work: Composite measurement
cites work: Intransitive indifference with unequal indifference intervals
cites work: Q5804173
cites work: Axiomatic thermodynamics and extensive measurement
full work available at URL: 0022-2496(86)90012-x
OpenAlex ID: W2037994918
description: scientific article; zbMATH DE number 3970597