An improved algorithm on the content of realizable fuzzy matrices (Q416271)

From MaRDI portal
scientific article
Language Label Description Also known as
English
An improved algorithm on the content of realizable fuzzy matrices
scientific article

    Statements

    An improved algorithm on the content of realizable fuzzy matrices (English)
    0 references
    0 references
    0 references
    10 May 2012
    0 references
    Let \(L=[0,1]\) and let \(\odot\) denote the max-min composition of fuzzy matrices over \(L\), i.e., \(E=C\odot D\) when \(E_{ij}=\max_k(\min(C_{ik},D_{kj}))\). A matrix \(A\in L^{n\times n}\) is realizable if there is a matrix \(B\in L^{n\times t}\) such that \(A=B\odot B^T\). The content of \(A\) is defined as \(r(A)=\min\{t:A=B\odot B^T, B\in L^{n\times t}\}\). Computing \(r(A)\) is an NP-complete problem [\textit{X. Wang} and \textit{Y. Yang}, ``On the computational complexity of the Schein rank of fuzzy matrices'', Math. Numer. Sin. 29, No.\ 3, 273--284 (2007; Zbl 1140.65328)]. The first author has proposed an algorithm to compute \(B\) and \(r(A)\) in \(O([r(A)]^{n^2})\) steps [\textit{X. Wang}, ``How to calculate the content for a given realizable fuzzy matrix'', Chin.\ Ann.\ Math., Ser.\ A 20, No.~6, 701--706 (1999; Zbl 0939.03510)]. In the current paper the symmetry of the problem is used to simplify the algorithm and reduce the complexity to \(O([r(A)]^{n(n+1)/2})\) steps.
    0 references
    realizable fuzzy matrix
    0 references
    matrix content
    0 references
    min-max composition
    0 references
    algorithm
    0 references
    computational complexity
    0 references
    Schein rank
    0 references

    Identifiers