ABSTRAKSI: Combinatorial auction adalah metode lelang yang sangat cocok digunakan untuk melelang item yang saling komplemen. Keunggulan combinatorial auction yang memudahkan dan memberikan jaminan bidder memperoleh hanya kelompok item yang dinginkannya membuat combinatorial auction ini terus menjadi bahan kajian yang menarik di kalangan ahli ekonomi. Hanya saja combinatorial auction memiliki kekurangan dengan sulitnya menentukan pemenang. Dalam dunia pemrograman komputer masalah ini termasuk ke dalam masalah NP-complete, artinya belum ada algoritma yang mampu menyelesaikan dalam waktu polinomial. Oleh karena itu digunakan dynamic programming yang memungkinkan dibangunnya algoritma alternatif yang akurat dan kompleksitas yang tidak telalu tinggi. Hasilnya, kasus combinatorial auction ini berhasil diselesaikan dengan akurasi 100% dan waktu komputasi yang cukup baik walaupun masih besar kemungkinan menjadi eksponensial tergantung pada kondisi bid yang masuk. Selain itu algoritma ini masih terkendala dengan masalah penggunaan memori yang cukup besar.
Kata Kunci : combinatorial auction, dynamic programming, algoritma, penentuan pemenang.ABSTRACT: Combinatorial auction is an auction method that is suitable for auctioning items which complement each other. Combinatorial auction advantages that guarantees the bidder to get only the combinations of item which they want, making this auction became an important and interesting topics in economist research. But, there is a lack of combinatorial auctions because the dificult of winner determination. In the world of computer programming, this problem is included in the NP-complete problem, meaning there is no algorithm that can solve this problem in polynomial time. Therefore, we use dynamic programming to develop an accurate alternative algorithm with good time complexity. The result, this algorithm can solve the combinatorial auction problem with 100% accuracy and computing time are quite good although it is still likely to be exponentially dependent on the conditions of entry bid. Also this algorithm is still have a problem with the need of large memori.
Keyword: combinatorial auction, dynamic programming, algorithm, winner determination.