Résumé : Variable selection in high-dimensional spaces is a pervasive challenge in contemporary scientific exploration and decision-making. However, existing approaches that are known to enjoy strong statistical guarantees often struggle to cope with the computational demands arising from the high dimensionality. To address this issue, we propose a novel Laplace approximation method based on Le Cam's one-step procedure (\textsf{OLAP}), designed to effectively tackles the computational burden. Under some classical high-dimensional assumptions we show that \textsf{OLAP} is a statistically consistent variable selection procedure. Furthermore, we show that the approach produces a posterior distribution that can be explored in polynomial time using a simple Gibbs sampling algorithm. Toward that polynomial complexity result, we also made some general, noteworthy contributions to the mixing time analysis of Markov chains. We illustrate the method using logistic and Poisson regression models applied to simulated and real data examples.