{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T15:11:43Z","timestamp":1743001903398,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540228943"},{"type":"electronic","value":"9783540278214"}],"license":[{"start":{"date-parts":[[2004,1,1]],"date-time":"2004-01-01T00:00:00Z","timestamp":1072915200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2004,1,1]],"date-time":"2004-01-01T00:00:00Z","timestamp":1072915200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27821-4_10","type":"book-chapter","created":{"date-parts":[[2010,9,14]],"date-time":"2010-09-14T18:54:06Z","timestamp":1284490446000},"page":"105-116","source":"Crossref","is-referenced-by-count":13,"title":["Polylogarithmic Inapproximability of the Radio Broadcast Problem"],"prefix":"10.1007","author":[{"given":"Michael","family":"Elkin","sequence":"first","affiliation":[]},{"given":"Guy","family":"Kortsarz","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"10_CR1","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Berger, B., Cowen, L., Peleg, D.: Fast network decomposition. In: Proc. 11th ACM Symp. on Principles of Distr. Comp. August 1992, pp. 161\u2013173 (1992)","DOI":"10.1145\/135419.135456"},{"key":"10_CR2","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1016\/0022-0000(91)90015-W","volume":"43","author":"N. Alon","year":"1991","unstructured":"Alon, N., Bar-Noy, A., Linial, N., Peleg, D.: A lower bound for radio broadcast. Journal of Computer and System Sciences\u00a043, 290\u2013298 (1991)","journal-title":"Journal of Computer and System Sciences"},{"key":"10_CR3","doi-asserted-by":"crossref","unstructured":"Arora, S., Babai, L., Stern, J., Swedyk, Z.: The hardness of approximate optima in lattices, codes and linear equations. In: Proc. 34th IEEE Symp. on Foundations of Computer Science, pp. 724\u2013733 (1993)","DOI":"10.1109\/SFCS.1993.366815"},{"key":"10_CR4","unstructured":"Arora, S., Lund, K.: In: Hochbaum, D. (ed.) Approximation Algorithms for NP-hard Problems, PWS Publishing (1996)"},{"key":"10_CR5","volume-title":"The Probabilistic Method","author":"N. Alon","year":"1992","unstructured":"Alon, N., Spencer, J.: The Probabilistic Method. Wiley, Chichester (1992)"},{"key":"10_CR6","unstructured":"Bar-Yehuda, R.: Private communication"},{"issue":"2","key":"10_CR7","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/BF02259748","volume":"5","author":"R. Bar-Yehuda","year":"1991","unstructured":"Bar-Yehuda, R., Goldreich, R.O., Itai, A.: Efficient emulation of singlehop radio network with collision detection on multi-hop radio network with no collision detection. Distributed Computing\u00a05(2), 67\u201372 (1991)","journal-title":"Distributed Computing"},{"key":"10_CR8","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1214\/aoms\/1177729330","volume":"23","author":"H. Chernoff","year":"1952","unstructured":"Chernoff, H.: A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Annals of Mathematical Statistics\u00a023, 493\u2013509 (1952)","journal-title":"Annals of Mathematical Statistics"},{"issue":"1","key":"10_CR9","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/s446-002-8028-1","volume":"15","author":"B.S. Chlebus","year":"2002","unstructured":"Chlebus, B.S., Gasieniec, L., Gibbons, A., Pelc, A., Rytter, W.: Deterministic broadcasting in ad hoc radio networks. Distributed Computing\u00a015(1), 27\u201338 (2002)","journal-title":"Distributed Computing"},{"key":"10_CR10","doi-asserted-by":"crossref","unstructured":"Chrobak, M., Gasieniec, L., Rytter, W.: Fast Broadcasting and Gossiping in Radio Networks. In: FOCS, pp. 575\u2013581 (2000)","DOI":"10.1109\/SFCS.2000.892325"},{"key":"10_CR11","unstructured":"Chlamtac, I., Kutten, S.: A spatial-reuse TDMA\/FDMA for mobile multihop radio networks. In: Proceedings IEEE INFOCOM, pp. 389\u2013394 (1985)"},{"issue":"302","key":"10_CR12","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/S0304-3975(02)00851-4","volume":"3","author":"A.F. Clementi","year":"2003","unstructured":"Clementi, A.F., Monti, A., Silvestri, R.: Distributed broadcast in radio networks of unknown topology. TCS 1\u00a03(302), 337\u2013364 (2003)","journal-title":"TCS 1"},{"key":"10_CR13","doi-asserted-by":"crossref","unstructured":"Czumaj, A., Rytter, W.: Broadcasting Algorithms in Radio Networks with Unknown Topology. In: FOCS, pp. 492\u2013501 (2003)","DOI":"10.1109\/SFCS.2003.1238222"},{"key":"10_CR14","doi-asserted-by":"crossref","unstructured":"Chlamtac, Weinstein: The wave expansion approach to broadcasting in multihop radio networks. INFOCOM (1987)","DOI":"10.1109\/MILCOM.1987.4795327"},{"key":"10_CR15","doi-asserted-by":"crossref","unstructured":"Dinur, I., Guruswami, V., Khot, S., Regev, O.: A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover. In: Dinur, I., GuruswamiIn, V. (eds.) Proc. of 34th Symp. on Theory of Computing (2003)","DOI":"10.1145\/780542.780629"},{"key":"10_CR16","unstructured":"Elkin, M., Kortsarz, G.: A logarithmic lower bound for radio broadcast. J. Algorithms (to appear)"},{"key":"10_CR17","unstructured":"Elkin, M., Kortsarz, G.: Improved broadcast in radio networks (2004) (manuscript)"},{"issue":"1","key":"10_CR18","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1137\/S0097539700380754","volume":"32","author":"U. Feige","year":"2002","unstructured":"Feige, U., Halldo\u2019rsson, M., Kortsarz, G., Srinivasan, A.: Approximating the domatic number. Siam journal on computing\u00a032(1), 172\u2013195 (2002)","journal-title":"Siam journal on computing"},{"issue":"3","key":"10_CR19","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1006\/jagm.1994.1042","volume":"17","author":"M. Fu\u201drer","year":"1994","unstructured":"Fu\u201drer, M., Raghavachari, B.: Approximating the Minimum-Degree Steiner Tree to within One of Optimal. J. Algorithms\u00a017(3), 409\u2013423 (1994)","journal-title":"J. Algorithms"},{"issue":"1","key":"10_CR20","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1006\/jagm.2000.1096","volume":"37","author":"N. Garg","year":"2000","unstructured":"Garg, N., Konjevod, G., Ravi, R.: A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem. J. Algorithms\u00a037(1), 66\u201384 (2000)","journal-title":"J. Algorithms"},{"key":"10_CR21","unstructured":"Gaber, I., Mansour, Y.: Broadcast in radio networks. In: the 6th ACM-Siam Symposium on Discrete Algorithms, pp. 577\u2013585 (1995)"},{"key":"10_CR22","doi-asserted-by":"crossref","unstructured":"Halperin, E., Krauthgamer, R.: Polylogarithmic inapproximability. In: (to appear in) 35th Symposium on Theory of Computing, STOC 2003 (2003)","DOI":"10.1145\/780542.780628"},{"key":"10_CR23","unstructured":"Halperin, E., Kortsarz, G., Krauthgamer, R., Srinivasan, A., Wang, N.: Integrality ratio for Group Steiner Trees and Directed Steiner Trees. In: SODA, pp. 275\u2013284 (2003)"},{"key":"10_CR24","unstructured":"Indyk, P.: Explicit constructions of selectors and related combinatorial structures, with applications. In: SODA, pp. 697\u2013704 (2002)"},{"key":"10_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/BFb0053970","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"G. Kortsarz","year":"1998","unstructured":"Kortsarz, G.: On the hardness of approximating spanners. In: Jansen, K., Rolim, J.D.P. (eds.) APPROX 1998. LNCS, vol.\u00a01444, pp. 135\u2013146. Springer, Heidelberg (1998)"},{"key":"10_CR26","unstructured":"Kushilevitz, Mansour: Computation in Noisy Radio Networks Symposium on Discrete Algorithms (1988)"},{"key":"10_CR27","doi-asserted-by":"crossref","unstructured":"Gandhi, R., Parthasarathy, S., Mishra, A.: Minimizing Broadcast Latency and Redundancy in Ad Hoc Networks. In: To appear in The Proc. of the Fourth ACM International Symposium on Mobile Ad Hoc Networking and Computing, MOBIHOC 2003 (June 2003)","DOI":"10.1145\/778415.778442"},{"key":"10_CR28","doi-asserted-by":"crossref","unstructured":"Kowalski, D., Pelc, A.: Deterministic broadcasting time in radio networks of unknown topology. In: Proc. 43rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2002, pp. 63\u201372 (2002)","DOI":"10.1109\/SFCS.2002.1181883"},{"key":"10_CR29","doi-asserted-by":"crossref","unstructured":"Kowalski, D., Pelc, A.: Broadcasting in undirected ad hoc radio networks. In: Symposium on Principles of distributed computing PODC, pp. 73\u201382 (2003)","DOI":"10.1145\/872035.872045"},{"key":"10_CR30","unstructured":"Linial, N., Saks, M.: Decomposing graphs into regions of small diameter. In: Proc. of the 2nd ACM-SIAM Symp. on Discr. Alg, pp. 320\u2013330 (1991)"},{"issue":"5","key":"10_CR31","doi-asserted-by":"crossref","first-page":"960","DOI":"10.1145\/185675.306789","volume":"41","author":"C. Lund","year":"1994","unstructured":"Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. J. Assoc. Comput. Mach.\u00a041(5), 960\u2013981 (1994)","journal-title":"J. Assoc. Comput. Mach."},{"key":"10_CR32","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)"},{"issue":"3","key":"10_CR33","doi-asserted-by":"publisher","first-page":"763","DOI":"10.1137\/S0097539795280895","volume":"27","author":"R. Raz","year":"1998","unstructured":"Raz, R.: A Parallel Repetition Theorem. SIAM Journal of computing\u00a027(3), 763\u2013803 (1998)","journal-title":"SIAM Journal of computing"},{"key":"10_CR34","unstructured":"Raz, R., Safra, S.: A Sub-Constant Error-Probability Low-Degree Test, and a Sub-Constant Error-Probability PCP Characterization of NP. In: STOC, pp. 575\u2013584"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27821-4_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,25]],"date-time":"2025-02-25T20:41:30Z","timestamp":1740516090000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-27821-4_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540228943","9783540278214"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27821-4_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}