On the hardness of efficiently approximating maximal non-\(L\) submatrices.

DOI10.1016/j.laa.2003.08.014zbMath1041.68044OpenAlexW1976590285MaRDI QIDQ1418978

Shawn Cokus, Andreas Brieden

Publication date: 14 January 2004

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.laa.2003.08.014

zbMATH Keywords

ComplexitySatisfiability\(L\)-matrixInapproximability2-SATSign-solvabilityApproximation-preserving reductionsQualitative linear algebra

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40) Vector spaces, linear dependence, rank, lineability (15A03)

Uses Software

• Outward rotations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Signsolvability revisited
• Approximability of maximum splitting of k-sets and some other Apx-complete problems
• Conditional sign-solvability
• Graph-theoretical approach to qualitative solvability of linear systems
• Permanents, Pfaffian orientations, and even directed circuits
• Outward rotations
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• Gadgets, Approximation, and Linear Programming
• Even dicycles
• Decomposition Theorems for Conditional Sign-Solvability and Sign-Solvability of General Systems
• Qualitative Economics and the Scope of the Correspondence Principle