# zbMATH — the first resource for mathematics

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.

##### MSC:
 68Q25 Analysis of algorithms and problem complexity 68R05 Combinatorics in computer science
##### Keywords:
approximation to matrices
Full Text: