  One of the main signatures of primordial non-Gaussianity of the local type is
a scale-dependent correction to the bias of large-scale structure tracers such
as galaxies or clusters, whose amplitude depends on the bias of the tracers
itself. The dominant source of noise in the power spectrum of the tracers is
caused by sampling variance on large scales (where the non-Gaussian signal is
strongest) and shot noise arising from their discrete nature. Recent work has
argued that one can avoid sampling variance by comparing multiple tracers of
different bias, and suppress shot noise by optimally weighting halos of
different mass. Here we combine these ideas and investigate how well the
signatures of non-Gaussian fluctuations in the primordial potential can be
extracted from the two-point correlations of halos and dark matter. On the
basis of large $N$-body simulations with local non-Gaussian initial conditions
and their halo catalogs we perform a Fisher matrix analysis of the two-point
statistics. Compared to the standard analysis, optimal weighting- and
multiple-tracer techniques applied to halos can yield up to one order of
magnitude improvements in $\fnl$-constraints, even if the underlying dark
matter density field is not known. We compare our numerical results to the halo
model and find satisfactory agreement. Forecasting the optimal
$\fnl$-constraints that can be achieved with our methods when applied to
existing and future survey data, we find that a survey of
$50h^{-1}\mathrm{Gpc}^3$ volume resolving all halos down to $10^{11}\hMsun$ at
$z=1$ will be able to obtain $\sigma_{\fnl}\sim1$ (68% cl), a factor of
$\sim20$ improvement over the current limits. Decreasing the minimum mass of
resolved halos, increasing the survey volume or obtaining the dark matter maps
can further improve these limits, potentially reaching the level of
$\sigma_{\fnl}\sim0.1$. (abridged)
