@article{,
    author = {Brieden, Andreas; Cokus, Shawn},
    title = {On the hardness of efficiently computing maximal non-L submatrices},
    editor = {},
    booktitle = {},
    series = {},
    journal = {Linear Algebra and its Applications},
    address = {},
    publisher = {},
    edition = {},
    year = {2004},
    isbn = {},
    volume = {377},
    number =  {},
    pages = {195-205},
    url = {},
    doi = {10.1016/j.laa.2003.08.014},
    keywords = {L-matrix ; Inapproximability ; Approximation-preserving reductions ; 2-Sat Satisfiability ; Complexity ; Sign-solvability ; Qualitative linear algebra},
    abstract = {The sign pattern of a real matrix A is the matrix obtained by replacing each entry of A by its sign. A real matrix A is an L-matrix if every real matrix with the same sign pattern as A has linearly independent columns. L-matrices arise naturally in and are essential to the study of sign-solvability and related notions. In special cases, the L-matrix property has connections to the even dicycle problem, Pfaffian orientations, and Pólya’s permanent problem. Unfortunately, the problem of recognizing L-matrices is known to be co--complete in general. We elaborate in this vein by showing a polynomial-time inapproximability result for Max-not-L-rows, a particular optimization version of L-matrix recognition, by means of an approximation-preserving reduction from the previously studied problem Max-not-equal-2-Sat.},
    note = {},
    
    
    
}