{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:10:10Z","timestamp":1750194610006,"version":"3.41.0"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T00:00:00Z","timestamp":1675123200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Foundation des Sciences Mathematiques de Paris"},{"DOI":"10.13039\/501100001738","name":"Ministry of Science Technology and Space, Israel","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001738","id-type":"DOI","asserted-by":"crossref"}]},{"name":"French-Israeli Laboratory FILOFOCS","award":["FA9550-13-1-0042 and FA9550-14-1-0403"],"award-info":[{"award-number":["FA9550-13-1-0042 and FA9550-14-1-0403"]}]},{"name":"NSF","award":["0939370-CCF, CCF-1217506, and CCF-AF-0937274"],"award-info":[{"award-number":["0939370-CCF, CCF-1217506, and CCF-AF-0937274"]}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["894\/09"],"award-info":[{"award-number":["894\/09"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001742","name":"United States-Israel Binational Science Foundation","doi-asserted-by":"crossref","award":["2008348"],"award-info":[{"award-number":["2008348"]}],"id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Israel Ministry of Science and Technology"},{"DOI":"10.13039\/100006461","name":"Citi Foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100006461","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2023,1,31]]},"abstract":"<jats:p>\n            Theoretical study of optimization problems in wireless communication often deals with tasks that concern a single point. For example, the\n            <jats:italic>power control<\/jats:italic>\n            problem requires computing a power assignment guaranteeing that each transmitting station\n            <jats:italic>\n              s\n              <jats:sub>i<\/jats:sub>\n            <\/jats:italic>\n            is successfully received at a\n            <jats:italic>single receiver point<\/jats:italic>\n            <jats:italic>\n              r\n              <jats:sub>i<\/jats:sub>\n            <\/jats:italic>\n            . This paper aims at addressing communication applications that require handling two-dimensional tasks (e.g., guaranteeing successful transmission in entire\n            <jats:italic>regions<\/jats:italic>\n            rather than at specific points).\n          <\/jats:p>\n          <jats:p>\n            The natural approach to two-dimensional optimization tasks is to\n            <jats:italic>discretize<\/jats:italic>\n            the optimization domain, e.g., by sampling points within the domain. The straightforward implementation of the discretization approach, however, might incur high time and memory requirements, and moreover, it cannot guarantee exact solutions.\n          <\/jats:p>\n          <jats:p>\n            The alternative proposed and explored in this paper is based on establishing the\n            <jats:italic>minimum principle<\/jats:italic>\n            <jats:xref ref-type=\"fn\">\n              <jats:sup>1<\/jats:sup>\n            <\/jats:xref>\n            for the\n            <jats:italic>\n              <jats:bold>signal to interference and noise ratio (SINR)<\/jats:bold>\n            <\/jats:italic>\n            function with free space path loss (i.e., when the signal decays in proportion to the square of the distance between the transmitter and receiver). Essentially, the minimum principle allows us to reduce the dimension of the optimization domain\n            <jats:italic>without<\/jats:italic>\n            losing anything in the accuracy or quality of the solution. More specifically, when the two-dimensional optimization domain is bounded and free from any interfering station, the minimum principle implies that it is sufficient to optimize the SINR function over the\n            <jats:italic>boundary<\/jats:italic>\n            of the domain, as the \u201chardest\u201d points to be satisfied reside on the boundary and not in the interior.\n          <\/jats:p>\n          <jats:p>We then utilize the minimum principle as the basis for an improved discretization technique for solving two-dimensional problems in the SINR model. This approach is shown to be useful for handling optimization problems over two dimensions (e.g., power control, energy minimization); in providing tight bounds on the number of null cells in the reception map; and in approximating geometric and topological properties of the wireless reception map (e.g., maximum inscribed sphere).<\/jats:p>\n          <jats:p>The minimum principle, as well as the interplay between continuous and discrete analysis presented in this paper, are expected to pave the way to future study of algorithmic SINR in higher dimensions.<\/jats:p>","DOI":"10.1145\/3477144","type":"journal-article","created":{"date-parts":[[2022,2,23]],"date-time":"2022-02-23T21:33:50Z","timestamp":1645652030000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["The Minimum Principle of SINR: A Useful Discretization Tool for Wireless Communication"],"prefix":"10.1145","volume":"19","author":[{"given":"Erez","family":"Kantor","sequence":"first","affiliation":[{"name":"MIT, Cambridge, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zvi","family":"Lotker","sequence":"additional","affiliation":[{"name":"Ben Gurion University, Beer Sheva, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Merav","family":"Parter","sequence":"additional","affiliation":[{"name":"Weizmann Institute of Science, Rehovot, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Peleg","sequence":"additional","affiliation":[{"name":"Weizmann Institute of Science, Rehovot, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,3,9]]},"reference":[{"key":"e_1_3_4_2_2","unstructured":"Alfred V. Aho John E. Hopcroft and Jeffrey D. Ullman. 1976. The design and analysis of computer algorithms. (1976)."},{"key":"e_1_3_4_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3209678"},{"key":"e_1_3_4_4_2","doi-asserted-by":"crossref","DOI":"10.1145\/2339123.2339125","article-title":"SINR diagrams: Convexity and its applications in wireless networks","volume":"59","author":"Avin C.","year":"2012","unstructured":"C. Avin, Y. Emek, E. Kantor, Z. Lotker, D. Peleg, and L. Roditty. 2012. SINR diagrams: Convexity and its applications in wireless networks. J. ACM 59(4) (2012).","journal-title":"J. ACM"},{"key":"e_1_3_4_5_2","volume-title":"Algorithms in Real Algebraic Geometry","author":"Basu Saugata","year":"2007","unstructured":"Saugata Basu, Richard Pollack, and Marie-Fran\u00e7oise Coste-Roy. 2007. Algorithms in Real Algebraic Geometry. Vol. 10. Springer Science & Business Media."},{"key":"e_1_3_4_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.883617"},{"key":"e_1_3_4_7_2","doi-asserted-by":"publisher","DOI":"10.1561\/1300000009"},{"key":"e_1_3_4_8_2","volume-title":"Proc. INFOCOM","author":"Cruz R. L.","year":"2003","unstructured":"R. L. Cruz and A. V. Santhanam. 2003. Optimal routing, link scheduling and power control in multi-hop wireless networks. In Proc. INFOCOM."},{"key":"e_1_3_4_9_2","first-page":"34 (5), 254\u2013256","volume-title":"Proc. IRE","author":"Friis H. T.","year":"1946","unstructured":"H. T. Friis. 1946. A note on a simple transmission formula. In Proc. IRE. 34 (5), 254\u2013256."},{"key":"e_1_3_4_10_2","volume-title":"Proc. SODA","author":"Halldorsson M. M.","year":"2011","unstructured":"M. M. Halldorsson and P. Mitra. 2011. Wireless capacity with oblivious power in general metrics. In Proc. SODA."},{"key":"e_1_3_4_11_2","volume-title":"Proc. STOC","author":"Kantor E.","year":"2011","unstructured":"E. Kantor, Z. Lotker, M. Parter, and D. Peleg. 2011. The topology of wireless communication. In Proc. STOC."},{"key":"e_1_3_4_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/2807693"},{"key":"e_1_3_4_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.10.002"},{"key":"e_1_3_4_14_2","volume-title":"Maximum Principles in Differential Equations","author":"Kaplan W.","year":"1984","unstructured":"W. Kaplan. 1984. Maximum Principles in Differential Equations. Addison-Wesley."},{"key":"e_1_3_4_15_2","volume-title":"Advanced Calculus","author":"Kaplan W.","year":"2002","unstructured":"W. Kaplan. 2002. Advanced Calculus. Addison-Wesley."},{"key":"e_1_3_4_16_2","volume-title":"Proc. SODA","author":"Kesselheim T.","year":"2011","unstructured":"T. Kesselheim. 2011. A constant-factor approximation for wireless capacity maximization with power control in the SINR model. In Proc. SODA."},{"key":"e_1_3_4_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/25.350273"},{"key":"e_1_3_4_18_2","volume-title":"Proc. INFOCOM","author":"Moscibroda T.","year":"2006","unstructured":"T. Moscibroda and R. Wattenhofer. 2006. The complexity of connectivity in wireless networks. In Proc. INFOCOM."},{"key":"e_1_3_4_19_2","doi-asserted-by":"publisher","DOI":"10.5555\/4333"},{"key":"e_1_3_4_20_2","volume-title":"Planning, Geometry, and Complexity of Robot Motion.","author":"Schwartz J. T.","year":"1987","unstructured":"J. T. Schwartz, M. Sharir, and J. E. Hopcroft.1987. Planning, Geometry, and Complexity of Robot Motion.Intellect Books."},{"key":"e_1_3_4_21_2","volume-title":"Multivariable Calculus: Concepts and Contexts","author":"Stewart J.","year":"2009","unstructured":"J. Stewart. 2009. Multivariable Calculus: Concepts and Contexts. Cengage Learning."},{"key":"e_1_3_4_22_2","volume-title":"Computing Handbook, Third Edition: Computer Science and Software Engineering","author":"Herrera A. Tucker T. Gonzalez, and J. D.","year":"2014","unstructured":"A. Tucker T. Gonzalez, and J. D. Herrera. 2014. Computing Handbook, Third Edition: Computer Science and Software Engineering. Hall\/CRC."},{"key":"e_1_3_4_23_2","doi-asserted-by":"crossref","DOI":"10.1145\/2160158.2160160","article-title":"The notion of a rational convex program, and an algorithm for the Arrow-Debreu Nash bargaining game","volume":"59","author":"Vazirani V.","year":"2012","unstructured":"V. Vazirani. 2012. The notion of a rational convex program, and an algorithm for the Arrow-Debreu Nash bargaining game. J. ACM 59 (2) (2012).","journal-title":"J. ACM"},{"key":"e_1_3_4_24_2","article-title":"A joint solution to scheduling and power control for multicasting in wireless ad hoc networks","volume":"2","author":"Wang K.","year":"2005","unstructured":"K. Wang, C. Chiasserini, R. Rao, and J. Proakis. 2005. A joint solution to scheduling and power control for multicasting in wireless ad hoc networks. J. Applied Signal Processing 2 (2005).","journal-title":"J. Applied Signal Processing"},{"key":"e_1_3_4_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/25.120145"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3477144","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3477144","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3477144","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:49:03Z","timestamp":1750193343000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3477144"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,31]]},"references-count":24,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1,31]]}},"alternative-id":["10.1145\/3477144"],"URL":"https:\/\/doi.org\/10.1145\/3477144","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2023,1,31]]},"assertion":[{"value":"2019-11-12","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-07-20","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-03-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}