Collapsing binary data for algebraic multidimensional representation (Q1081564)

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.