  In the Bidder Selection Problem (BSP) there is a large pool of $n$ potential
advertisers competing for ad slots on the user's web page. Due to strict
computational restrictions, the advertising platform can run a proper auction
only for a fraction $k<n$ of advertisers. We consider the basic optimization
problem underlying BSP: given $n$ independent prior distributions, how to
efficiently find a subset of $k$ with the objective of either maximizing
expected social welfare or revenue of the platform. We study BSP in the classic
multi-winner model of position auctions for welfare and revenue objectives
using the optimal (respectively, VCG mechanism, or Myerson's auction) format
for the selected set of bidders. Previous PTAS results for BSP optimization
were only known for single-item auctions and in case of [Segev and Singla 2021]
for $l$-unit auctions. More importantly, all of these PTASes were computational
complexity results with impractically large running times, which defeats the
purpose of using these algorithms under severe computational constraints.
  We propose a novel Poisson relaxation of BSP for position auctions that
immediately implies that 1) BSP is polynomial-time solvable up to a vanishingly
small error as the problem size $k$ grows; 2) there is a PTAS for position
auctions after combining our relaxation with the trivial brute force algorithm.
Unlike all previous PTASes, we implemented our algorithm and did extensive
numerical experiments on practically relevant input sizes. First, our
experiments corroborate the previous experimental findings of Mehta et al. that
a few simple heuristics used in practice perform surprisingly well in terms of
approximation factor. Furthermore, our algorithm outperforms Greedy both in
running time and approximation on medium and large-sized instances.
