Result: Solving the winner determination problem via a weighted maximum clique heuristic

Title:
Solving the winner determination problem via a weighted maximum clique heuristic
Authors:
QINGHUA WU, HAO, Jin-Kao
Source:
Expert systems with applications. 42(1):355-365
Publisher Information:
Amsterdam: Elsevier, 2015.
Publication Year:
2015
Physical Description:
print, 3/4 p
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences et techniques communes, Sciences and techniques of general use, Mathematiques, Mathematics, Combinatoire. Structures ordonnées, Combinatorics. Ordered structures, Combinatoire, Combinatorics, Théorie des graphes, Graph theory, Sciences appliquees, Applied sciences, Recherche operationnelle. Gestion, Operational research. Management science, Recherche opérationnelle et modèles formalisés de gestion, Operational research and scientific management, Flots dans les réseaux. Problèmes combinatoires, Flows in networks. Combinatorial problems, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Recherche information. Graphe, Information retrieval. Graph, Clique graphe, Graph clique, Commerce électronique, Electronic trade, Comercio electronico, Efficacité, Efficiency, Eficacia, Enchère inversée, Reverse auction, Subasta inversa, Modélisation, Modeling, Modelización, Méthode heuristique, Heuristic method, Método heurístico, Optimisation combinatoire, Combinatorial optimization, Optimización combinatoria, Pertinence, Relevance, Pertinencia, Problème NP difficile, NP hard problem, Problema NP duro, Problème clique maximal, maximum clique problem, Problema clique máxima, Recherche tabou, Tabu search, Búsqueda tabú, Résolution problème, Problem solving, Resolución problema, Théorie graphe, Graph theory, Teoría grafo, Vente groupée ou liée, Bundling, Venta conjunta, Combinatorial auctions, Heuristics, Maximum clique, Winner determination
Document Type:
Academic journal Article
File Description:
text
Language:
English
Author Affiliations:
School of Management, Huazhong University of Science and Technology, No. 1037, Luoyu Road, Wuhan, China
LERIA, Université d'Angers, 2 bd Lavoisier, 49045 Angers, France
ISSN:
0957-4174
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=28843407
Rights:
Copyright 2015 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems

Mathematics

Operational research. Management
Accession Number:
edscal.28843407
Database:
PASCAL Archive

Further Information

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.