Abstract: We examine a novel class of procurement auctions for single-minded bidders, in which the auctioneer must select a subset of bids to be accepted subject to complicated feasibility constraints, possibly including a constraint on the total payment. (This setting is inspired by the Federal Communication Commission's problem of buying out a subset broadcast TV licenses to clear some spectrum for broadband uses while retuning the remaining TV stations into the remaining TV spectrum subject to interference constraints.) Complexity of the constraints may preclude an optimization-based approach to winner selection. Instead, we propose a class of computationally feasible "heuristic" auctions that calculate both a feasible set of winning bidders and "threshold" payments to those bidders that induce strategy-proof bidding. The calculation iteratively rejects the "highest-scoring" bid that could still be feasibly rejected, with the scores based on bid values and other criteria (including previously rejected bids). We show that such heuristic auctions can be characterized by their equivalence to clock auctions with descending bidder-specific prices in which bidders can quit any time their prices are decremented. Furthermore, we establish full-information "payoff equivalence" between "threshold" (or "clock") auctions and their paid-as-bid counterparts with the same allocation: A paid-as-bid heuristic auction has a Nash equilibrium with the same outcome as its threshold-auction counterpart, and a unique Nash equilibrium in weakly undominated strategies and an essentially unique outcome surviving iterated deletion of weakly dominated strategies. Bio: Ilya R. Segal is the Roy and Betty Anderson Professor of Economics at Stanford University. His research examines the design of contracts and market mechanisms, considering both incentives and computational constraints (bounded rationality). His awards include a Guggenheim Fellowship, a Sloan Foundation Research Fellowship, and a Compass-Lexecon Prize for "the most significant contribution to the understanding and implementation of competition policy". He has served on the editorial boards of American Economic Review, Review of Economic Studies, and RAND Journal of Economics, and was a Founding Editor of the B.E. Journals in Theoretical Economics. He is a Fellow of the Econometric Society and a member of the Toulouse Network for Information Technology.