×

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

Summary: 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-NP-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.

MSC:

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

References:

[1] Bassett, L.; Maybee, J.; Quirk, J., Qualitative economics and the scope of the correspondence principle, Econometrica, 36, 544-563 (1968) · Zbl 0217.26802
[2] Bellare, M.; Goldreich, O.; Sudan, M., Free bits, PCPs, and nonapproximability-towards tight results, SIAM J. Comput., 27, 3, 804-915 (1998), (electronic) · Zbl 0912.68041
[3] Brualdi, R.; Chavey, K.; Shader, B., Conditional sign-solvability, Math. Comput. Modelling, 17, 1, 141-148 (1993) · Zbl 0768.90051
[4] Brualdi, R.; Shader, B., Matrices of Sign-Solvable Linear Systems, (Cambridge Tracts in Mathematics, vol. 116 (1995), Cambridge University Press: Cambridge University Press Cambridge) · Zbl 1165.15003
[5] Cokus, S.; Klee, V., Decomposition theorems for conditional sign-solvability and sign-solvability of general systems, SIAM J. Matrix Anal. Appl., 21, 3, 978-988 (2000), (electronic) · Zbl 0958.15005
[6] Crescenzi, P.; Silvestri, R.; Trevisan, L., To weight or not to weight: Where is the question?, (in: Israel Symp. on Theory of Computing and Systems (Jerusalem, 1996) (1996), IEEE Comput. Soc. Press: IEEE Comput. Soc. Press Los Alamitos, CA), 68-77
[7] Garey, M.; Johnson, D., Computers and Intractability. A Guide to the Theory of NP-completeness (1979), W.H. Freeman and Co: W.H. Freeman and Co San Francisco, CA · Zbl 0411.68039
[8] Goemans, M.; Williamson, D., Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. Assoc. Comput. Mach., 42, 6, 1115-1145 (1995) · Zbl 0885.68088
[9] V. Guruswami, Inapproximability results for set splitting and satisfiability problems with no mixed clauses, in: Proc. APPROX, 2000, pp. 155-166; V. Guruswami, Inapproximability results for set splitting and satisfiability problems with no mixed clauses, in: Proc. APPROX, 2000, pp. 155-166 · Zbl 0976.68075
[10] Håstad, J., Some optimal inapproximability results, (in: STOC ’97 (El Paso, TX) (1999), ACM: ACM New York), 1-10, (electronic) · Zbl 0963.68193
[11] Kann, V.; Lagergren, J.; Panconesi, A., Approximability of maximum splitting of \(k\)-sets and some other APX-complete problems, Inform. Process. Lett., 58, 3, 105-110 (1996) · Zbl 0998.90525
[12] Kasteleyn, P., Dimer statistics and phase transitions, J. Math. Phys., 4, 287-293 (1963)
[13] Klee, V.; Ladner, R.; Manber, R., Signsolvability revisited, Linear Algebra Appl., 59, 131-157 (1984) · Zbl 0543.15016
[14] Mahajan, S.; Ramesh, H., Derandomizing semidefinite programming based approximation algorithms, (in: 36th Annual Symposium on Foundations of Computer Science (Milwaukee, WI, 1995) (1995), IEEE Comput. Soc. Press: IEEE Comput. Soc. Press Los Alamitos, CA), 162-169 · Zbl 0938.68915
[15] Manber, R., Graph-theoretical approach to qualitative solvability of linear systems, Linear Algebra Appl., 48, 457-470 (1982) · Zbl 0511.15008
[16] Maybee, J., Sign solvability, (Greenberg, H.; Maybee, J., Computer-Assisted Analysis and Model Simplification (1981), Academic Press, Inc., Harcourt Brace Jovanovich, Publishers: Academic Press, Inc., Harcourt Brace Jovanovich, Publishers New York, London), 201-257
[17] McCuaig, W., Even dicycles, J. Graph Theory, 35, 1, 46-68 (2000) · Zbl 0958.05070
[18] Papadimitriou, C.; Steiglitz, K., Combinatorial Optimization: Algorithms and Complexity (1982), Prentice-Hall Inc: Prentice-Hall Inc Englewood Cliffs, NJ · Zbl 0503.90060
[19] Robertson, N.; Seymour, P.; Thomas, R., Permanents, Pfaffian orientations, and even directed circuits, Ann. of Math. (2), 150, 3, 929-975 (1999) · Zbl 0947.05066
[20] Samuelson, P., Foundations of Economic Analysis, (Harvard Economic Studies, vol. 80 (1947), Harvard University Press: Harvard University Press Cambridge, MA) · Zbl 0031.17401
[21] Trevisan, L.; Sorkin, G.; Sudan, M.; Williamson, D., Gadgets, approximation, and linear programming, SIAM J. Comput., 29, 6, 2074-2097 (2000), (electronic) · Zbl 0957.68048
[22] Zwick, U., Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint, (in: Proc. of the Ninth Ann. ACM-SIAM Symp. on Disc. Algorithms (1998), ACM: ACM New York), 201-210 · Zbl 0930.68142
[23] Zwick, U., Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to MAX CUT and other problems, (in: Proc. of the 31st Annual ACM Symp. on Theory of Computing (STOC ’99) (1999), ACM: ACM New York), 679-687 · Zbl 1345.90064
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.