Using a Lagrangian Heuristic for a Combinatorial Auction Problem

• Main Authors: GUO, Yunsong, LIM, Andrew, RODRIGUES, Brian, TANG, Jiqing
• 格式: text
• 語言: English
• 出版: Institutional Knowledge at Singapore Management University 2006
• 主題: Combinatorial auction; Langrange relaxation; heuristic; Operations and Supply Chain Management
• 在線閱讀: https://ink.library.smu.edu.sg/lkcsb_research/558; https://doi.org/10.1142/S0218213006002771
• 機構: Singapore Management University

Combinatorial auctions allow bidders to bid for items leading to more efficient allocations, but determining winners in auctions is $\mathcal{NP}$-complete. In this work, a simple yet effective Lagrangian relaxation based heuristic algorithm is presented. Extensive computational experiments using st...