{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,16]],"date-time":"2026-10-16T16:31:17Z","timestamp":1792168277482,"version":"4.4.0"},"reference-count":34,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2013,1]]},"abstract":"<jats:p>Let $\\mathcal{F}$ be a set system over an underlying finite set $X$, and let $\\mu$ be a nonnegative measure over $X$; i.e., for every $S \\subseteq X$, $\\mu(S)=\\sum_{x\\in S} \\mu(x)$. A measure $\\mu^*$ on $X$ is called a multiplicative ${\\lambda}$-approximation of $\\mu$ on $(\\mathcal{F},X)$ if for every $S\\in \\mathcal{F}$ it holds that $a\\mu(S) \\leq \\mu^*(S) \\leq b \\mu(S)$, and $b\/a = \\lambda \\geq 1$. The central question raised and partially answered in the present paper is about the existence of meaningful structural properties of $\\mathcal{F}$ implying that for any $\\mu$ on $X$ there exists an ${{1+\\epsilon} \\over {1-\\epsilon}}$-approximation $\\mu^*$ supported on a small subset of $X$. It turns out that the parameter that governs the support size of a multiplicative approximation is the triangular rank of $\\mathcal{F}$, ${\\rm trk}(\\mathcal{F})$. It is defined as the maximal length of a sequence of sets $\\{S_i\\}_{i=1}^t $ in $\\mathcal{F}$ such that for all $1&lt;i\\leq t$, $S_i \\not\\subseteq \\cup_{j&lt;i}\\,S_j$. We show that for any $\\mu$ on $X$ and $0&lt;\\epsilon&lt;1$, there is measure $\\mu^*$ that ${{1+\\epsilon} \\over {1-\\epsilon}}$-approximates $\\mu$ on $(X,\\mathcal{F})$, and has support of size $~\\widetilde{O}({\\rm trk}(\\mathcal{F}) \\cdot {\\rm VCdim}(\\mathcal{F})\/ \\epsilon^2)$, where ${\\rm VCdim}(\\mathcal{F})$, bounded from above by ${\\rm trk}(\\mathcal{F})$, is the VC-dimension of $\\mathcal{F}$. We also present some alternative constructions which in some cases improve upon this bound. Conversely, we show that for any $0 \\leq \\epsilon&lt;1$ there exists a $\\mu$ on $X$ that cannot be ${{1+\\epsilon}\\over {1-\\epsilon}}$-approximated on $(\\mathcal{F},X)$ by any $\\mu^*$ with support of size $&lt; {\\rm trk}(\\mathcal{F})$. For special families $\\mathcal{F}$ this bound is improved to $\\;\\Omega({\\rm trk}(\\mathcal{F})\/\\epsilon)$. As an application we show a new dimension-reduction result for $\\ell_1$ metrics: Any $\\ell_1$-metric on $n$ points can be (efficiently) embedded with ${{1+\\epsilon}\\over {1-\\epsilon}}$-distortion into $\\mathbb{R}^{O(n\/\\epsilon^2)}$ equipped with the $\\ell_1$ norm. This improves over the best previously known bound of Schechtman, showing that the dimension is bounded by $O(n \\log n \/{\\rm poly}(\\epsilon))$. We obtain also some new results on efficient sampling of Euclidean volumes. In order to make the general framework applicable to this setting, we develop the basic theory of finite volumes, analogous to the theory of finite metrics, and get results of independent interest in this direction. To do so, we use basic combinatorial\/topological facts about simplicial complexes, and study the naturally arising questions.<\/jats:p>","DOI":"10.1137\/100801809","type":"journal-article","created":{"date-parts":[[2013,5,16]],"date-time":"2013-05-16T12:27:45Z","timestamp":1368707265000},"page":"855-883","source":"Crossref","is-referenced-by-count":13,"title":["On Multiplicative $\\lambda$-Approximations and Some Geometric Applications"],"prefix":"10.1137","volume":"42","author":[{"given":"Ilan","family":"Newman","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuri","family":"Rabinovich","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2013,5,16]]},"reference":[{"key":"atypb1","unstructured":"N. Alon and J. Spencer,\n                      The Probabilistic Method\n                      , John Wiley, New York, 1992."},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02189308"},{"key":"atypb3","first-page":"315","author":"Andoni A.","year":"2011","journal-title":"NJ"},{"key":"atypb4","unstructured":"E. Babson, C. Hoffman, and M. Kahle,\n                      The Fundamental Group of Random $2$-Complexes\n                      , preprint, arXiv0711.2704, 2008."},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(13)80131-X"},{"key":"atypb6","first-page":"296","author":"Barhum K.","year":"2007","journal-title":"Berlin"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"J.D. Batson, D.A. Spielman, and N. Srivastava,\n                      Twice-Ramanujan sparsifiers\n                      , in STOC'09, 2009, ACM, New York, pp. 255-262.","DOI":"10.1145\/1536414.1536451"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1093"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1007\/BF02776078"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1145\/1089023.1089026"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1682"},{"key":"atypb12","first-page":"569","author":"Feldman D.","year":"2011","journal-title":"New York"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(84)90058-X"},{"key":"atypb14","first-page":"71","author":"Fung W.S.","year":"2011","journal-title":"New York"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-004-0015-x"},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"S. Har Peled,\n                      Geometric approximation algorithms\n                      , Mathematical Surveys and Monographs 173, AMS, Providence, RI, 2011.","DOI":"10.1090\/surv\/173"},{"key":"atypb17","first-page":"428","author":"Indyk P.","year":"1999","journal-title":"New York"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-004-0473-8"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1741"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-006-0027-9"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1112\/blms\/bdm003"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85363-3_41"},{"key":"atypb23","unstructured":"W.S. Massey,\n                      Algebraic Topology: An Introduction\n                      , Springer Verlag, New York, 1990."},{"key":"atypb24","unstructured":"J. Matousek,\n                      Geometric Discrepancy\n                      , 2nd ed., Berlin, Springer, 2009."},{"key":"atypb25","first-page":"855","author":"Matousek J.","year":"2009","journal-title":"ACM-SIAM"},{"key":"atypb26","unstructured":"J. Matousek and U. Wagner,\n                      On Gromov's Method of Selecting Heavily Covered Points\n                      , preprint, arXiv:1102.3515, 2011."},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20238"},{"key":"atypb28","unstructured":"J.R. Munkres,\n                      Elements of Algebraic Topology\n                      , Addison-Wesley, Reading, MA, 1984."},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20080"},{"key":"atypb30","first-page":"159","volume":"61","author":"Schechtman G.","year":"1987","journal-title":"Compositio Math."},{"key":"atypb31","first-page":"481","author":"Seidel J.J.","year":"1976","journal-title":"Rome"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176988847"},{"key":"atypb33","first-page":"363","volume":"108","author":"Talagrand M.","year":"1990","journal-title":"Proc. Amer. Math. Soc."},{"key":"atypb34","first-page":"351","author":"Wagner U.","year":"2011","journal-title":"New York"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/100801809","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:30:46Z","timestamp":1787337046000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/100801809"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["10.1137\/100801809"],"URL":"https:\/\/doi.org\/10.1137\/100801809","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1]]}}}