{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:27:48Z","timestamp":1750307268536,"version":"3.41.0"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2011,5,1]],"date-time":"2011-05-01T00:00:00Z","timestamp":1304208000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["305783\/2009-2476791\/2009-0"],"award-info":[{"award-number":["305783\/2009-2476791\/2009-0"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004586","name":"Funda\u00e7\u00e3o Carlos Chagas Filho de Amparo \u00e0 Pesquisa do Estado do Rio de Janeiro","doi-asserted-by":"publisher","award":["E-26\/102.192\/2009"],"award-info":[{"award-number":["E-26\/102.192\/2009"]}],"id":[{"id":"10.13039\/501100004586","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2011,5]]},"abstract":"<jats:p>\n            Let\n            <jats:italic>f<\/jats:italic>\n            be a function on a set of variables\n            <jats:italic>V<\/jats:italic>\n            . For each\n            <jats:italic>x<\/jats:italic>\n            \u2208\n            <jats:italic>V<\/jats:italic>\n            , let\n            <jats:italic>c(x)<\/jats:italic>\n            be the cost of reading the value of\n            <jats:italic>x<\/jats:italic>\n            . An algorithm for evaluating\n            <jats:italic>f<\/jats:italic>\n            is a strategy for adaptively identifying and reading a set of variables\n            <jats:italic>U<\/jats:italic>\n            \u2286\n            <jats:italic>V<\/jats:italic>\n            whose values uniquely determine the value of\n            <jats:italic>f<\/jats:italic>\n            . We are interested in finding algorithms which minimize the cost incurred to evaluate\n            <jats:italic>f<\/jats:italic>\n            in the above sense. Competitive analysis is employed to measure the performance of the algorithms. We address two variants of the above problem. We consider the basic model in which the evaluation algorithm knows the cost\n            <jats:italic>c(x)<\/jats:italic>\n            , for each\n            <jats:italic>x<\/jats:italic>\n            \u2208\n            <jats:italic>V<\/jats:italic>\n            . We also study a novel model where the costs of the variables are not known in advance and some\n            <jats:italic>preemption<\/jats:italic>\n            is allowed in the reading operations. This model has applications, for example, when reading a variable coincides with obtaining the output of a job on a CPU and the cost is the CPU time.\n          <\/jats:p>\n          <jats:p>\n            For the model where the costs of the variables are known, we present a\n            <jats:italic>polynomial time<\/jats:italic>\n            algorithm with the best possible competitive ratio \u03b3\n            <jats:sub>\n              <jats:italic>c<\/jats:italic>\n            <\/jats:sub>\n            <jats:sup>\n              <jats:italic>f<\/jats:italic>\n            <\/jats:sup>\n            for each function\n            <jats:italic>f<\/jats:italic>\n            that is representable by a threshold tree and for each fixed cost function\n            <jats:italic>c<\/jats:italic>\n            (\u22c5). Remarkably, the best-known result for the same class of functions is a\n            <jats:italic>pseudo-polynomial<\/jats:italic>\n            algorithm with competitiveness 2 \u03b3\n            <jats:sub>\n              <jats:italic>c<\/jats:italic>\n            <\/jats:sub>\n            <jats:sup>\n              <jats:italic>f<\/jats:italic>\n            <\/jats:sup>\n            . Still in the same model, we introduce the Linear Programming Approach (\n            <jats:italic>LPA<\/jats:italic>\n            ), a framework that allows the design of efficient algorithms for evaluating functions. We show that different implementations of this approach lead in general to the best algorithms known so far\u2014and in many cases to optimal algorithms\u2014for different classes of functions considered before in the literature.\n          <\/jats:p>\n          <jats:p>\n            Via the\n            <jats:italic>LPA<\/jats:italic>\n            , we are able to determine exactly the optimal extremal competitiveness of monotone Boolean functions. Remarkably, the upper bound which leads to this result, holds for a much broader class of functions, which also includes the whole set of Boolean functions.\n          <\/jats:p>\n          <jats:p>\n            We also show how to extend the\n            <jats:italic>LPA<\/jats:italic>\n            (together with these results) to the model where the costs of the variables are not known beforehand. In particular, we show how to employ the extended\n            <jats:italic>LPA<\/jats:italic>\n            to design a polynomial-time optimal (with respect to competitiveness) algorithm for the class of monotone Boolean functions representable by threshold trees.\n          <\/jats:p>","DOI":"10.1145\/1970392.1970393","type":"journal-article","created":{"date-parts":[[2011,6,6]],"date-time":"2011-06-06T11:51:38Z","timestamp":1307361098000},"page":"1-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["On the competitive ratio of evaluating priced functions"],"prefix":"10.1145","volume":"58","author":[{"given":"Ferdinando","family":"Cicalese","sequence":"first","affiliation":[{"name":"University of Salerno, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eduardo Sany","family":"Laber","sequence":"additional","affiliation":[{"name":"PUC-Rio, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,6,9]]},"reference":[{"key":"e_1_2_1_1_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 8th Latin American Symposium on Theoretical Informatics","author":"Angelov S.","unstructured":"Angelov , S. , Kunal , K. , and McGregor , A. 2008. Sorting and selection with random costs . In Proceedings of the 8th Latin American Symposium on Theoretical Informatics . Lecture Notes in Computer Science , vol. 4957 . Springer , 48--59. Angelov, S., Kunal, K., and McGregor, A. 2008. Sorting and selection with random costs. In Proceedings of the 8th Latin American Symposium on Theoretical Informatics. Lecture Notes in Computer Science, vol. 4957. Springer, 48--59."},{"doi-asserted-by":"crossref","unstructured":"Ausiello G. Protasi M. Marchetti-Spaccamela A. Gambosi G. Crescenzi P. and Kann V. 1999. Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer-Verlag.   Ausiello G. Protasi M. Marchetti-Spaccamela A. Gambosi G. Crescenzi P. and Kann V. 1999. Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer-Verlag.","key":"e_1_2_1_2_1","DOI":"10.1007\/978-3-642-58412-1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1016\/S0304-3975(01)00144-X"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1006\/jcss.2002.1828"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1145\/1060590.1060691"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1007\/11561071_59"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.5555\/1109557.1109661"},{"key":"e_1_2_1_8_1","volume-title":"Eds","author":"Graham R. L.","year":"1996","unstructured":"Graham , R. L. , Gr\u00f6tschel , M. , and Lov\u00e1sz , L. , Eds . 1996 . Handbook of Combinatorics. The MIT Press - North-Holland . Graham, R. L., Gr\u00f6tschel, M., and Lov\u00e1sz, L., Eds. 1996. Handbook of Combinatorics. The MIT Press - North-Holland."},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1016\/j.artint.2005.09.002"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1007\/BF02579273"},{"volume-title":"Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science. IEEE Computer Society, 416--425","author":"Gupta A.","unstructured":"Gupta , A. , and Kumar , A . 2001. Sorting and selection with structured costs . In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science. IEEE Computer Society, 416--425 . Gupta, A., and Kumar, A. 2001. Sorting and selection with structured costs. In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science. IEEE Computer Society, 416--425.","key":"e_1_2_1_11_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1007\/11538462_7"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1007\/BF01212962"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1145\/292481.277627"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1145\/780542.780640"},{"volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM\/SIAM, 10--17","author":"Kannan S.","unstructured":"Kannan , S. , and Khanna , S . 2003. Selection with monotone comparison cost . In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM\/SIAM, 10--17 . Kannan, S., and Khanna, S. 2003. Selection with monotone comparison cost. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM\/SIAM, 10--17.","key":"e_1_2_1_16_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1145\/1060590.1060644"},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.1145\/375551.375577"},{"key":"e_1_2_1_19_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 21st Annual Symposium on Theoretical Aspects of Computer Science","author":"Laber E. S.","unstructured":"Laber , E. S. 2004. A randomized competitive algorithm for evaluating priced and\/or trees . In Proceedings of the 21st Annual Symposium on Theoretical Aspects of Computer Science . Lecture Notes in Computer Science , vol. 2996 . Springer , 501--512. Laber, E. S. 2004. A randomized competitive algorithm for evaluating priced and\/or trees. In Proceedings of the 21st Annual Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 2996. Springer, 501--512."},{"key":"e_1_2_1_20_1","volume-title":"Proceeding of the 14th International Symposium on Algorithms and Computation. Lecture Notes in Computer Science","volume":"2906","author":"Maheshwari A.","unstructured":"Maheshwari , A. , and Smid , M. H. M. 2003. A dynamic dictionary for priced information with application . In Proceeding of the 14th International Symposium on Algorithms and Computation. Lecture Notes in Computer Science , vol. 2906 . Springer, 16--25. Maheshwari, A., and Smid, M. H. M. 2003. A dynamic dictionary for priced information with application. In Proceeding of the 14th International Symposium on Algorithms and Computation. Lecture Notes in Computer Science, vol. 2906. Springer, 16--25."},{"key":"e_1_2_1_21_1","volume-title":"Artificial Intelligence: A Modern Approach","author":"Russell S.","year":"1995","unstructured":"Russell , S. , and Norvig , P . 1995 . Artificial Intelligence: A Modern Approach . Prentice-Hall . Russell, S., and Norvig, P. 1995. Artificial Intelligence: A Modern Approach. Prentice-Hall."},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.1109\/SFCS.1986.44"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1016\/0304-3975(85)90210-5"},{"doi-asserted-by":"publisher","key":"e_1_2_1_24_1","DOI":"10.1145\/2402.322383"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1970392.1970393","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1970392.1970393","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:52:53Z","timestamp":1750243973000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1970392.1970393"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,5]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,5]]}},"alternative-id":["10.1145\/1970392.1970393"],"URL":"https:\/\/doi.org\/10.1145\/1970392.1970393","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2011,5]]},"assertion":[{"value":"2008-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-06-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}