{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:24:31Z","timestamp":1750220671843,"version":"3.41.0"},"reference-count":13,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2020,12,14]],"date-time":"2020-12-14T00:00:00Z","timestamp":1607904000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Queue"],"published-print":{"date-parts":[[2020,12,14]]},"abstract":"<jats:p>\n            Expectations run high for software that makes real-world decisions, particularly when money hangs in the balance. This third episode of the\n            <jats:italic>Drill Bits<\/jats:italic>\n            column shows how well-designed software can effectively\n            <jats:italic>create wealth<\/jats:italic>\n            by optimizing gains from trade in combinatorial auctions. We'll unveil a deep connection between auctions and a classic textbook problem, we'll see that clearing an auction resembles a high-stakes mutant Tetris, we'll learn to stop worrying and love an NP-hard problem that's far from intractable in practice, and we'll contrast the deliberative business of combinatorial auctions with the near-real-time hustle of high-frequency trading. The example software that accompanies this installment of\n            <jats:italic>Drill Bits<\/jats:italic>\n            implements two algorithms that clear combinatorial auctions.\n          <\/jats:p>","DOI":"10.1145\/3442632.3448307","type":"journal-article","created":{"date-parts":[[2021,1,27]],"date-time":"2021-01-27T23:04:40Z","timestamp":1611788680000},"page":"37-51","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Offline Algorithms in Low-Frequency Trading"],"prefix":"10.1145","volume":"18","author":[{"given":"Terence","family":"Kelly","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,1,27]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICMAS.2000.858429"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02158-9_8;"},{"volume-title":"Knapsack Problems","author":"Kellerer H.","key":"e_1_2_1_3_1","unstructured":"Kellerer, H., Pferschy, U., Pisinger, D. 2004. Knapsack Problems. Springer."},{"key":"e_1_2_1_4_1","volume-title":"Self-Managing Systems (June)","author":"Kelly T.","year":"2003","unstructured":"Kelly, T. 2003. Utility-directed allocation. In Self-Managing Systems (June); https:\/\/www.hpl.hp.com\/techreports\/2003\/HPL-2003-115.pdf. Also U.S. Patent #7,844,967."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/11575726_6;"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Kelly T. 2020. Efficient graph search. acmqueue 18(4); https:\/\/queue.acm.org\/detail.cfm?id=3424304","DOI":"10.1145\/3424302.3424304"},{"key":"e_1_2_1_7_1","series-title":"August 2","volume-title":"Rewarding bad actors. New York Times","author":"Krugman P.","year":"2009","unstructured":"Krugman, P. 2009. Rewarding bad actors. New York Times (August 2); https:\/\/www.nytimes.com\/2009\/08\/03\/opinion\/03krugman.html"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Loveless J. Stoikov S. Waeber R. 2013. Online algorithms in high-frequency trading. acmqueue 11(8); https:\/\/dl.acm.org\/doi\/10.1145\/2523426.2534976","DOI":"10.1145\/2523426.2534976"},{"key":"e_1_2_1_10_1","volume-title":"Combinatorial Optimization: Algorithms and Complexity, 388","author":"Papadimitriou C. H.","year":"1998","unstructured":"Papadimitriou, C. H., Steiglitz, K. 1998. Combinatorial Optimization: Algorithms and Complexity, 388. Dover."},{"key":"e_1_2_1_11_1","volume-title":"Algorithms","author":"Sedgewick R.","unstructured":"Sedgewick, R., Wayne, K. 2011. Algorithms, 4th edition, 679. Addison-Wesley.","edition":"4"},{"key":"e_1_2_1_12_1","volume-title":"Federal Reserve Bank Atlanta Financial Markets Conference (April); https:\/\/www.frbatlanta.org\/-\/media\/Documents\/news\/conferences\/2014\/fmc\/Stiglitz.pdf","author":"Stiglitz J. E.","year":"2014","unstructured":"Stiglitz, J. E. 2014. Tapping the brakes. In Federal Reserve Bank Atlanta Financial Markets Conference (April); https:\/\/www.frbatlanta.org\/-\/media\/Documents\/news\/conferences\/2014\/fmc\/Stiglitz.pdf"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","unstructured":"Treleaven P. Galas M. Lalchand V. 2013. Algorithmic trading review. Communications of the ACM 56(11) 76?85; https:\/\/doi.org\/10.1145\/2500117","DOI":"10.1145\/2500117"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1378704.1378708"}],"container-title":["Queue"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3442632.3448307","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3442632.3448307","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:03:03Z","timestamp":1750197783000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3442632.3448307"}},"subtitle":["Clearing Combinatorial Auctions"],"short-title":[],"issued":{"date-parts":[[2020,12,14]]},"references-count":13,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,12,14]]}},"alternative-id":["10.1145\/3442632.3448307"],"URL":"https:\/\/doi.org\/10.1145\/3442632.3448307","relation":{},"ISSN":["1542-7730","1542-7749"],"issn-type":[{"type":"print","value":"1542-7730"},{"type":"electronic","value":"1542-7749"}],"subject":[],"published":{"date-parts":[[2020,12,14]]},"assertion":[{"value":"2021-01-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}