Collapsing binary data for algebraic multidimensional representation

DOI10.1016/0022-2496(86)90012-XMaRDI QIDQ1081564zbMATH OpenOpenAlexFDO

Authors Charles Chubb

Publication date 1986

Published in Journal of Mathematical Psychology (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0022-2496(86)90012-x

zbMATH Keywords

algebraic representationbinary relationcollapsing methodsmultidimensional scaling techniquesNP-hardpolynomially efficient procedurepolynomially reducible

Mathematics Subject Classification ID

Other classical set theory (including functions, relations, and set algebra) (03E20) Analysis of algorithms and problem complexity (68Q25) Mathematical psychology (91E99) Other natural sciences (mathematical treatment) (92F05)

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.

Recommendations

• Compact binary relation representations with rich functionality
• Compact rich-functional binary relation representations
• Relational and Kleene-Algebraic Methods in Computer Science
• scientific article; zbMATH DE number 1923135
• scientific article; zbMATH DE number 1953899

Cites work

• A note on an alternative proof of the representation theorem for bi- semiorder
• Axiomatic thermodynamics and extensive measurement
• Composite measurement
• Difference measurement and simple scalability with restricted solvability
• Ferrers digraphs and threshold graphs
• scientific article; zbMATH DE number 3654150 (Why is no real title available?)
• scientific article; zbMATH DE number 3564982 (Why is no real title available?)
• scientific article; zbMATH DE number 3619929 (Why is no real title available?)
• scientific article; zbMATH DE number 3064989 (Why is no real title available?)
• Intransitive indifference with unequal indifference intervals
• Matching relations and the dimensional structure of social choices
• On realizable biorders and the biorder dimension of a relation
• On the Ferrers dimension of a digraph

Cited in

(8)

• On finding the bidimension of a relation
• A generic disjunctive/conjunctive decomposition model for n-ary relations
• Surmise relations between tests -- mathematical considerations.
• A binding procedure for distributed binary data representations
• Compact rich-functional binary relation representations
• Compact binary relation representations with rich functionality
• Algebraic structures and social processes
• Ear decomposition for pair comparison data

This page was built for publication: Collapsing binary data for algebraic multidimensional representation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1081564)