Using a Lagrangian Heuristic for a Combinatorial Auction Problem

• المؤلفون الرئيسيون: 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

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...