Winner determination in combinatorial auctions is a weighted set-packing problem and is NP-hard in general. This paper develops a deterministic polynomial-time sparse-pursuit framework that couples the global linear-programming relaxation with CoSaMP-type identify–merge–re-estimate–prune dynamics. The re-estimation step keeps only a logarithmic-size moving window integral while all other bid variables remain fractionally relaxed, so each partially integral global relaxation is polynomial-time solvable. Partial integrality itself is a standard optimization device, and the coordinate ranges of an LP-optimal face are established in the mixed-integer-programming literature as cloud intervals. We therefore make no novelty claim for either the intervals $[\ell_j,u_j]$ or the binary criterion $\ell_j>0$, $u_j<1$. The central contribution is instead a quantitative multi-coordinate window theorem. Let $X_{\rm LP}^\star$ be the full optimal face of the ordinary LP, let $\ell_j$ and $u_j$ be the minimum and maximum of coordinate $j$ over that face, and define the weighted cloud-interval score $\psi_j=v_j\min\{\ell_j,1-u_j\}$. A Hoffman-type polyhedral sharpness constant $\mu>0$ yields, for every exactification window $D$,
\[
U(D)\le U_{\rm LP}-\mu\sum_{j\in D}\psi_j.
\]
Consequently the identify step, which selects the largest weighted cloud-interval scores, maximizes the guaranteed amount of LP-bound tightening among all admissible windows of the same form and size; positive selected ambiguity forces strict tightening. If $V_{\rm C}$ is the returned feasible welfare, $V^\star$ is the exact WDP optimum, $U_{\rm P}$ is the best pursuit upper bound, and $U_{\rm LP}$ is the ordinary LP bound, then every instance satisfies
\[
V_{\rm C}\le V^\star\le U_{\rm P}\le U_{\rm LP}.
\]
Hence
\[
0\le \frac{V^\star-V_{\rm C}}{V^\star}
\le 1-\frac{V_{\rm C}}{U_{\rm P}}
\le 1-\frac{V_{\rm C}}{U_{\rm LP}}.
\]
In particular, $V_{\rm C}\ge0.97U_{\rm P}$ certifies an optimality gap of at most $3\%$, while $U_{\rm P}\le1.03V_{\rm C}$ certifies the strictly smaller bound $1-1/1.03<2.913\%$. A protected approximation seed may be used in parallel, yielding an adaptive ratio equal to the better of its uniform guarantee and the pursuit certificate. No planted solution, probabilistic valuation model, restricted-isometry assumption, or distributional hypothesis is used.