{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:34:12Z","timestamp":1763458452561,"version":"3.45.0"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,4,25]],"date-time":"2017-04-25T00:00:00Z","timestamp":1493078400000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000774","name":"Defense Threat Reduction Agency","doi-asserted-by":"publisher","award":["HDTRA1-11-1-0016, HDTRA1-11-D-0016-0010"],"award-info":[{"award-number":["HDTRA1-11-1-0016, HDTRA1-11-D-0016-0010"]}],"id":[{"id":"10.13039\/100000774","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2016,6,15]]},"abstract":"<jats:p>\n                    Packet scheduling is a particular challenge in wireless networks due to interference from nearby transmissions. A\n                    <jats:italic toggle=\"yes\">distance-2 interference model<\/jats:italic>\n                    serves as a useful abstraction here, and we study packet routing and scheduling under this model of interference. The main focus of our work is the development of fully distributed (decentralized) protocols. We present polylogarithmic\/constant factor approximation algorithms for various families of disk graphs (which capture the geometric nature of wireless-signal propagation), as well as near-optimal approximation algorithms for general graphs. A basic distributed coloring procedure, originally due to Luby [1993] (\n                    <jats:italic toggle=\"yes\">Journal of Computer and System Sciences<\/jats:italic>\n                    , 47:250--286, 1993), underlies many of our algorithms. The work of Finocchi et al. [2002] (\n                    <jats:italic toggle=\"yes\">Proc. ACM-SIAM Symposium on Discrete Algorithms<\/jats:italic>\n                    , 2002) showed that a natural modification of this algorithm leads to improved performance. A rigorous explanation of this was left as an open question, and we prove that the modified algorithm is indeed provably better in the worst case.\n                  <\/jats:p>","DOI":"10.1145\/2812811","type":"journal-article","created":{"date-parts":[[2016,4,25]],"date-time":"2016-04-25T15:51:13Z","timestamp":1461599473000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Distributed Algorithms for End-to-End Packet Scheduling in Wireless Ad Hoc Networks"],"prefix":"10.1145","volume":"12","author":[{"given":"V. S. Anil","family":"Kumar","sequence":"first","affiliation":[{"name":"Virginia Tech, Blacksburg, VA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Madhav V.","family":"Marathe","sequence":"additional","affiliation":[{"name":"Virginia Tech, Blacksburg, VA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Srinivasan","family":"Parthasarathy","sequence":"additional","affiliation":[{"name":"IBM T. J. Watson Research Center, Yorktown Heights, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aravind","family":"Srinivasan","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, MD"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,4,25]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1137\/S0895480192236628"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1109\/INFCOM.2000.832234"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1109\/SFCS.1997.646118"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1007\/s00224-004-1124-z"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1007\/3-540-59042-0_81"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1002\/rsa.3240050305"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1109\/SFCS.1989.63504"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1137\/0405013"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1109\/JSAC.2004.830909"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1145\/1978782.1978788"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1145\/1288107.1288123"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1214\/aoms\/1177729330"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1145\/2312005.2312061"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.5555\/1833515.1833717"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1016\/j.jcss.2005.04.002"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1007\/978-3-642-02930-1_37"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.5555\/545381.545461"},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.1006\/jagm.2000.1097"},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_1","DOI":"10.5555\/2027223.2027287"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1145\/2746539.2746585"},{"doi-asserted-by":"publisher","unstructured":"M. M. Halld\u00f3rsson and R. Wattenhofer. 2009. Wireless communication is in APX. In International Colloquium on Automata Languages and Programming (ICALP\u201909). 525--536. 10.1007\/978-3-642-02927-1_44","key":"e_1_2_1_21_1","DOI":"10.1007\/978-3-642-02927-1_44"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.1080\/01621459.1963.10500830"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1007\/978-3-642-33090-2_57"},{"doi-asserted-by":"publisher","key":"e_1_2_1_24_1","DOI":"10.1023\/A:1012311216333"},{"unstructured":"V. S. Anil Kumar M. Marathe and S. Parthasarathy. 2008. Cross-layer capacity estimation and throughput maximization in wireless networks. Handbook on Algorithms for Next Generation Networks (2008).","key":"e_1_2_1_25_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.5555\/982792.982945"},{"doi-asserted-by":"publisher","key":"e_1_2_1_27_1","DOI":"10.1145\/1064212.1064228"},{"doi-asserted-by":"publisher","key":"e_1_2_1_28_1","DOI":"10.1007\/s004930050061"},{"doi-asserted-by":"publisher","key":"e_1_2_1_29_1","DOI":"10.1007\/BF01215349"},{"doi-asserted-by":"publisher","key":"e_1_2_1_30_1","DOI":"10.1137\/0221015"},{"doi-asserted-by":"publisher","key":"e_1_2_1_31_1","DOI":"10.1007\/BF01303516"},{"doi-asserted-by":"publisher","unstructured":"Z. Lotker and D. Peleg. 2010. Structure and algorithms in the SINR wireless model. ACM SIGACT News (2010). 10.1145\/1814370.1814391","key":"e_1_2_1_32_1","DOI":"10.1145\/1814370.1814391"},{"doi-asserted-by":"publisher","key":"e_1_2_1_33_1","DOI":"10.1016\/0022-0000(93)90033-S"},{"doi-asserted-by":"publisher","key":"e_1_2_1_34_1","DOI":"10.1145\/258533.258659"},{"doi-asserted-by":"publisher","key":"e_1_2_1_35_1","DOI":"10.1006\/jagm.1996.0017"},{"doi-asserted-by":"publisher","key":"e_1_2_1_36_1","DOI":"10.1007\/978-3-642-33651-5_31"},{"doi-asserted-by":"publisher","key":"e_1_2_1_37_1","DOI":"10.5555\/320320"},{"doi-asserted-by":"publisher","key":"e_1_2_1_38_1","DOI":"10.5555\/170269"},{"doi-asserted-by":"publisher","key":"e_1_2_1_39_1","DOI":"10.1023\/A:1019126406181"},{"doi-asserted-by":"publisher","key":"e_1_2_1_40_1","DOI":"10.1145\/153377.153379"},{"doi-asserted-by":"publisher","key":"e_1_2_1_41_1","DOI":"10.5555\/838237.838387"},{"doi-asserted-by":"publisher","key":"e_1_2_1_42_1","DOI":"10.5555\/552515"},{"doi-asserted-by":"publisher","key":"e_1_2_1_43_1","DOI":"10.1137\/S0097539798335596"},{"doi-asserted-by":"publisher","key":"e_1_2_1_44_1","DOI":"10.1007\/978-3-642-03417-6_17"},{"doi-asserted-by":"publisher","key":"e_1_2_1_45_1","DOI":"10.4086\/toc.2007.v003a006"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2812811","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2812811","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2812811","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:23:57Z","timestamp":1763457837000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2812811"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,4,25]]},"references-count":45,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,6,15]]}},"alternative-id":["10.1145\/2812811"],"URL":"https:\/\/doi.org\/10.1145\/2812811","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2016,4,25]]},"assertion":[{"value":"2012-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-08-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-04-25","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}