{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:15:53Z","timestamp":1750306553871,"version":"3.41.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"2-3","license":[{"start":{"date-parts":[[2014,10,28]],"date-time":"2014-10-28T00:00:00Z","timestamp":1414454400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"UMIC Research Centre at RWTH Aachen University"},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["Ho 3831\/3-1"],"award-info":[{"award-number":["Ho 3831\/3-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Cluster of Excellence MMCI at Saarland University"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Internet Technol."],"published-print":{"date-parts":[[2014,10,28]]},"abstract":"<jats:p>\n            We study combinatorial auctions for secondary spectrum markets, where short-term communication licenses are sold to wireless nodes. Channels can be assigned to multiple bidders according to interference constraints captured by a conflict graph. We suggest a novel approach to such combinatorial auctions using a graph parameter called inductive independence number. We achieve good approximation results by showing that interference constraints for wireless networks imply a bounded inductive independence number. For example, in the physical model the factor becomes\n            <jats:italic>O<\/jats:italic>\n            (\u221a\n            <jats:italic>k<\/jats:italic>\n            log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) for\n            <jats:italic>n<\/jats:italic>\n            bidders and\n            <jats:italic>k<\/jats:italic>\n            channels. Our algorithms can be turned into incentive-compatible mechanisms for bidders with arbitrary valuations.\n          <\/jats:p>","DOI":"10.1145\/2663496","type":"journal-article","created":{"date-parts":[[2014,10,28]],"date-time":"2014-10-28T12:40:29Z","timestamp":1414500029000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["Approximation Algorithms for Secondary Spectrum Auctions"],"prefix":"10.1145","volume":"14","author":[{"given":"Martin","family":"Hoefer","sequence":"first","affiliation":[{"name":"Max-Planck-Institut f\u00fcr Informatik and Saarland University, Saarbrucken, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Kesselheim","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Berthold","family":"V\u00f6cking","sequence":"additional","affiliation":[{"name":"RWTH Aachen University, Aachen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,10,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2006.05.001"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2006.881641"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2004.830909"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/PERCOMW.2006.129"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/WOWMOM.2005.36"},{"volume-title":"Proceedings of the 6th International Workshop on Internet and Network Economics (WINE'10)","author":"Christodoulou G.","key":"e_1_2_1_6_1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"P. Cramton Y. Shoham and R. Steinberg. Eds. 2006. Combinatorial Auctions. MIT Press.   P. Cramton Y. Shoham and R. Steinberg. Eds. 2006. Combinatorial Auctions. MIT Press.","DOI":"10.7551\/mitpress\/9780262033428.001.0001"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.02.010"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-011-0227-z"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1582716.1582752"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.05.004"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.14"},{"volume-title":"Proceedings of the 1st International Workshop on Approximation and Online Algorithms (WAOA'03)","year":"2003","author":"Fishkin A. V.","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2007.11.003"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/964723.383068"},{"volume-title":"Proceedings of the 28th IEEE Conference on Computer Communications (INFOCOM'09). 1872","year":"1880","author":"Goussevskaia O.","key":"e_1_2_1_16_1"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009196"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.825799"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2390176.2390183"},{"volume-title":"Proceedings of the 24th Symposium on Discrete Algorithms (SODA'13)","author":"Halldorsson M.","key":"e_1_2_1_20_1"},{"volume-title":"Proceedings of the 22nd Symposium on Discrete Algorithms (SODA'11)","author":"Halldorsson M.","key":"e_1_2_1_21_1"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392825"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(83)90080-X"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229062"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2486159.2486163"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989493.1989520"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492002.2482548"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0899-8256(03)00184-2"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2008.080117"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.08.027"},{"volume-title":"Proceedings of the 6th Workshop on the Economics of Networks, Systems, and Computation (NetEcon'11)","author":"Kash I.","key":"e_1_2_1_31_1"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133156"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33090-2_57"},{"volume-title":"Proceedings of the 24th International Symposium on Distributed Computing (DISC'10)","author":"Kesselheim T.","key":"e_1_2_1_34_1"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1012311216333"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049697.2049699"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"N. Nisan E. Tardos T. Roughgarden and V. Vazirani. Eds. 2007. Algorithmic Game Theory. Cambridge University Press.   N. Nisan E. Tardos T. Roughgarden and V. Vazirani. Eds. 2007. Algorithmic Game Theory. Cambridge University Press.","DOI":"10.1017\/CBO9780511800481"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380839"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374389"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1530748.1530761"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2151171.2151177"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1409944.1409947"},{"volume-title":"Proceedings of the 28th IEEE Conference on Computer Communications (INFOCOM'09)","author":"Zhou X.","key":"e_1_2_1_43_1"},{"volume-title":"Proceedings of the 31st IEEE Conference on Computer Communications (INFOCOM'12)","author":"Zhu Y.","key":"e_1_2_1_44_1"}],"container-title":["ACM Transactions on Internet Technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2663496","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2663496","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:12:48Z","timestamp":1750227168000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2663496"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10,28]]},"references-count":44,"journal-issue":{"issue":"2-3","published-print":{"date-parts":[[2014,10,28]]}},"alternative-id":["10.1145\/2663496"],"URL":"https:\/\/doi.org\/10.1145\/2663496","relation":{},"ISSN":["1533-5399","1557-6051"],"issn-type":[{"type":"print","value":"1533-5399"},{"type":"electronic","value":"1557-6051"}],"subject":[],"published":{"date-parts":[[2014,10,28]]},"assertion":[{"value":"2013-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-10-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}