In this paper we completely solve the problem of finding the upper approximation order with respect to the Kolmogorov, Gelfand, and linear widths for the embedding of the Sobolev spaces \(W^{\alpha ,p}\) and \(W^{\alpha ,p}_{0}\) into the Lebesgue space \(L^{q}_{\nu }\) . Here, \(\nu \) is a Borel probability measure with support contained in the open unit cube of the m-dimensional Euclidean space, and we cover the entire range of parameters \(1\le p,q\le \infty \) . We determine the exact values of the approximation orders solely in terms of the \(L^{q}\) -spectrum of \(\nu \) . For the lower approximation order, we generally obtain only bounds; however, in the case \(q=\infty \) we identify the lower order exactly in terms of the lower Minkowski dimension. We also provide sufficient regularity conditions on the \(L^{q}\) -spectrum that ensure the upper and lower approximation orders coincide. Finally, we clarify intrinsic links between approximation orders and the fractal-geometric notions of the upper and lower Minkowski dimensions of the support of \(\nu \) .
