  The Bayesian online selection problem aims to design a pricing scheme for a
sequence of arriving buyers that maximizes the expected social welfare (or
revenue) subject to different structural constraints. Inspired by applications
with a hierarchy of service, this paper focuses on the cases where a laminar
matroid characterizes the set of served buyers. We give the first
Polynomial-Time Approximation Scheme (PTAS) for the problem when the laminar
matroid has constant depth. Our approach is based on rounding the solution of a
hierarchy of linear programming relaxations that approximate the optimum online
solution with any degree of accuracy, plus a concentration argument showing
that rounding incurs a small loss. We also study another variation, which we
call the production-constrained problem. The allowable set of served buyers is
characterized by a collection of production and shipping constraints that form
a particular example of a laminar matroid. Using a similar LP-based approach,
we design a PTAS for this problem, although in this special case the depth of
the underlying laminar matroid is not necessarily a constant. The analysis
exploits the negative dependency of the optimum selection rule in the lower
levels of the laminar family. Finally, to demonstrate the generality of our
technique, we employ the linear programming-based approach employed in the
paper to re-derive some of the classic prophet inequalities known in the
literature -- as a side result.
