Abstract | ||
---|---|---|
In this paper, a combinatorial auction problem is modeled as a NP-complete set packing problem and a Lagrangian relaxation based heuristic algorithm is proposed. Extensive experiments are conducted using benchmark CATS test sets and more complex test sets. The algorithm provides optimal solutions for most test sets and is always 1% from the optimal solutions for all CATS test sets. Comparisons with CPLEX 8.0 are also provided, which show that the algorithm provides good solutions. |
Year | DOI | Venue |
---|---|---|
2005 | 10.1109/ICTAI.2005.126 | International Journal on Artificial Intelligence Tools |
Keywords | Field | DocType |
lagrangian heuristic,combinatorial auction problem,optimal solution,good solution,complex test set,benchmark cats test set,heuristic.,langrange relaxation,test set,combinatorial auction,heuristic algorithm,cats test set,extensive experiment,lagrangian relaxation,bin packing,commerce,relaxation methods,business,computational complexity | Mathematical optimization,Heuristic (computer science),Combinatorial auction,Computer science,Relaxation (iterative method),Set packing,Lagrangian relaxation,Auction algorithm,Bin packing problem,Computational complexity theory | Conference |
Volume | Issue | ISSN |
15 | 3 | 1082-3409 |
ISBN | Citations | PageRank |
0-7695-2488-5 | 13 | 0.60 |
References | Authors | |
11 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Yunsong Guo | 1 | 13 | 0.60 |
A. Lim | 2 | 479 | 31.72 |
Brian Rodrigues | 3 | 78 | 8.07 |
Jiqing Tang | 4 | 13 | 0.60 |