Quick approximation to matrices and applications. (English) Zbl 0933.68061

Summary: We give algorithms to find the following simply described approximation to a given matrix. Given an \(m\times n\) matrix \({\mathbf A}\) with entries between say \(-1\) and 1, and an error parameter \(\varepsilon\) between 0 and 1, we find a matrix \({\mathbf D}\) (implicitly) which is the sum of \(O(1/\varepsilon^2)\) simple rank 1 matrices so that the sum of entries of any submatrix (among the \(2^{m+n})\) of \(({\mathbf A}-{\mathbf D})\) is at most \(\varepsilon m n\) in absolute value. Our algorithm takes time dependent only on \(\varepsilon\) and the allowed probability of failure (not on \(m\), \(n\)).
We draw on two lines of research to develop the algorithms: one is bulit around the fundamental regularity lemma of Szemerédi in graph theory and the constructive version of N. Alon, R. A. Duke, H. Leffman, V. Rödl and R. Yuster [J. Algorithms 16, 80-109 (1994; Zbl 0794.05119)]. The second one is from the papers of Arora, Karger and Karpinski [Proc. 27th Ann. ACM Symp. on Theory of Computing, 284-293 (1995)], W. Fernandez de la Vega [Random Struct. Algorithms 8, 187-198 (1996; Zbl 0848.90120)] and most directly Goldwasser, Goldreich and Ron [Proc. 37th Ann. IEEE Symp. on Fund. Comp. Sci. 339-348 (1996)] who develop approximation algorithms for a set of graph problems, typical of which is the maximum cut problem.
From our matrix approximation, the above graph algorithms and the regularity lemma and several other results follow in a simple way.
We generalize our approximations to multi-dimensional arrays and from that derive approximation algorithms for all dense max-SNP problems.


68Q25 Analysis of algorithms and problem complexity
68R05 Combinatorics in computer science
Full Text: DOI