Arrêt de service programmé du vendredi 10 juin 16h jusqu’au lundi 13 juin 9h. Pour en savoir plus
Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

Solving the winner determination problem via a weighted maximum clique heuristic

Abstract :

Combinatorial auctions (CAs) where bidders can bid on combinations of items is an important model in many application areas. CAs attract more and more attention in recent years due to its relevance to fast growing electronic business applications. In this paper, we study the winner determination problem (WDP) in CAs which is known to be NP-hard and thus computationally difficult in the general case. We develop a solution approach for the WDP by recasting the WDP into the maximum weight clique problem (MWCP) and solving the transformed problem with a recent heuristic dedicated to the MWCP. The computational experiments on a large range of 530 benchmark instances show that the clique-based approach for the WDP not only outperforms the current best performing WDP heuristics in the literature both in terms of solution quality and computation efficiency, but also competes very favorably with the powerful CPLEX solver.

Type de document :
Article dans une revue
Liste complète des métadonnées
Contributeur : Okina Univ Angers Connectez-vous pour contacter le contributeur
Soumis le : lundi 1 juin 2020 - 16:53:27
Dernière modification le : mercredi 20 octobre 2021 - 03:19:08




Qinghua Wu, Jin-Kao Hao. Solving the winner determination problem via a weighted maximum clique heuristic. Expert Systems with Applications, Elsevier, 2015, 42 (1), pp.355-365. ⟨10.1016/j.eswa.2014.07.027⟩. ⟨hal-02709495⟩



Consultations de la notice