Using a Lagrangian Heuristic for a Combinatorial Auction Problem

• Main Authors: GUO, Yunsong, LIM, Andrew, RODRIGUES, Brian, TANG, Jiqing
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2006
• Subjects: Combinatorial auction; Langrange relaxation; heuristic; Operations and Supply Chain Management
• Online Access: https://ink.library.smu.edu.sg/lkcsb_research/558; https://doi.org/10.1142/S0218213006002771
• Institution: 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...