{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,2,19]],"date-time":"2023-02-19T23:27:53Z","timestamp":1676849273764},"reference-count":5,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Artif. Intell. Tools"],"published-print":{"date-parts":[[2006,6]]},"abstract":"<jats:p> Combinatorial auctions allow bidders to bid for items leading to more efficient allocations, but determining winners in auctions is [Formula: see text]-complete. In this work, a simple yet effective Lagrangian relaxation based heuristic algorithm is presented. Extensive computational experiments using standard benchmark data (CATS) as well as newly generated more realistic test sets were conducted which showed the heuristic was able to provide optimal solutions for most test cases and is within 1% from the optimums for the rest within very short times. Experiements comparing CPLEX 8.0, the fastest current algorithm, showed the heuristic was able to provide equally godd or better solutions often requring less than 1% of the time required by CPLEX 8.0. <\/jats:p>","DOI":"10.1142\/s0218213006002771","type":"journal-article","created":{"date-parts":[[2006,5,26]],"date-time":"2006-05-26T06:43:59Z","timestamp":1148625839000},"page":"481-489","source":"Crossref","is-referenced-by-count":2,"title":["USING A LAGRANGIAN HEURISTIC FOR A COMBINATORIAL AUCTION PROBLEM"],"prefix":"10.1142","volume":"15","author":[{"given":"YUNSONG","family":"GUO","sequence":"first","affiliation":[{"name":"School of Computing, National University of Singapore, 3, Science Drive 2, Singapore 117543, Singapore"}]},{"given":"ANDREW","family":"LIM","sequence":"additional","affiliation":[{"name":"Department of IELM, Hong Kong University of Science and Technology, Clear Water Bay, Hong Kong, China"}]},{"given":"BRIAN","family":"RODRIGUES","sequence":"additional","affiliation":[{"name":"School of Business, Singapore Management University, Singapore 259756, Singapore"}]},{"given":"JIQING","family":"TANG","sequence":"additional","affiliation":[{"name":"Department of IELM, Hong Kong University of Science and Technology, Clear Water Bay, Hong Kong, China"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"reference":[{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.47.5.730"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.15.3.284.16077"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.27.1.1"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(01)00159-X"}],"container-title":["International Journal on Artificial Intelligence Tools"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218213006002771","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T12:54:05Z","timestamp":1565182445000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218213006002771"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,6]]},"references-count":5,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[2006,6]]}},"alternative-id":["10.1142\/S0218213006002771"],"URL":"https:\/\/doi.org\/10.1142\/s0218213006002771","relation":{},"ISSN":["0218-2130","1793-6349"],"issn-type":[{"value":"0218-2130","type":"print"},{"value":"1793-6349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,6]]}}}