Selection and Ordering Policies for Hiring Pipelines via Linear Programming.

This article focuses on developing and analyzing linear programming-based approximation algorithms for three hiring pipeline problems faced by firms with limited time and capacity: sequential interviewing (ProbeTop-k), parallel offering, and simultaneous offering. For the ProbeTop-k problem, where a firm sequentially interviews candidates and must decide whom to hire immediately or after all interviews, the authors present a nonadaptive, committed algorithm achieving an approximation factor of at least 1−1/e (≈63.2%) relative to the optimal adaptive, noncommitted policy, improving previous bounds and enabling a polynomial-time approximation scheme (PTAS). In the Parallel Offering model, where offers are sent in parallel to candidates for heterogeneous positions, they provide a nonadaptive algorithm with a (1−1/e)-approximation guarantee, generalizing and strengthening earlier results. For the Simultaneous Offering problem, where all offers are sent at once and overbooking incurs linear penalties, the authors analyze value-ordered policies under the assumption that candidate values are bounded below by a positive parameter τ, deriving nearly tight approximation bounds that improve as the number of positions grows. The paper also includes numerical comparisons of the three offering modes and discusses open questions related to combining models and robustness to parameter uncertainty.