{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:39:37Z","timestamp":1787337577979,"version":"build-2736575974"},"reference-count":20,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2000,1]]},"abstract":"<jats:p>The World Wide Web provides access to vast amounts of information, but content providers are considering charging for the information and services they supply. Thus the consumer may face the problem of balancing the benefit of asking for information against the cost (in terms of both money and time) of acquiring it. We study information-gathering strategies that maximize the expected value to the consumer. In our model there is a single information request, which has a known benefit to the consumer. To satisfy the request, queries can be sent simultaneously or in sequence to any of a finite set of independent information sources. For each source we know the monetary cost of making the query, the amount of time it will take, and the probability that the source will be able to provide the requested information. A policy specifies which sources to contact at which times, and the expected value of the policy can be defined as some function of the likelihood that the policy will yield an answer, the expected benefit, and the monetary cost and time delay associated with executing the policy. The problem is to find an expected-value-maximizing policy.<\/jats:p>\n                  <jats:p>\n                    We explore four variants of the objective function V: (i) V consists only of the benefit term subject to threshold constraints on both total cost and total elapsed time, (ii) V is linear in the expected total cost of the policy subject to the constraint that the total elapsed time never exceeds somedeadline, (iii) V is linear in the expected total elapsed time subject to the constraint that the total cost never exceeds some threshold, and (iv) V is linear in the expected total monetary cost and the expected time delay of the policy. The problems of devising an optimal querying policy for all four variants and approximating an optimal querying policy for variants (iii) and (iv) are shown to be NP-hard. For (i), and with a mild simplifying assumption for (iii), we give a fully polynomial time approximation scheme. For (ii), we consider batched querying policies, and design an O(n\n                    <jats:sup>2<\/jats:sup>\n                    ) time approximation algorithm with ratio $\\frac{1}{2}$ and a polynomial time approximation scheme for optimal single-batch policies, and an O(kn\n                    <jats:sup>2<\/jats:sup>\n                    ) time approximation algorithm with ratio $\\frac{1}{5}$ for optimal k-batch policies.\n                  <\/jats:p>","DOI":"10.1137\/s0097539797314465","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1596-1620","source":"Crossref","is-referenced-by-count":2,"title":["Optimal Information Gathering on the Internet with Time and Cost Constraints"],"prefix":"10.1137","volume":"29","author":[{"given":"Oren","family":"Etzioni","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Steve","family":"Hanks","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tao","family":"Jiang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Omid","family":"Madani","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,27]]},"reference":[{"key":"R1","unstructured":"O. Etzioni, S. Hanks, T. Jiang, R. Karp, O. Madani, O. Waarts, Efficient information gathering on the internet (extended abstract), IEEE Comput. Soc. Press, Los Alamitos, CA, 1996, 234\u20132431450621"},{"key":"R2","unstructured":"O. Etzioni, R. M. Karp, and O. Waarts,\n                      Efficient Access to Information Sources on the Internet\n                      , manuscript, 1996."},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800290109"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(73)90113-1"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1002\/1520-6750(199002)37:1<99::AID-NAV3220370106>3.0.CO;2-5"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1145\/321906.321909"},{"key":"R7","unstructured":"The LEXIS\u2010NEXIS Corporation, 1997;"},{"key":"R7","unstructured":"available online at http:\/\/www.lexis\u2010nexis.com\/lncc\/."},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(69)90140-1"},{"key":"R9","unstructured":"B. Krulwich,\n                      The Bargain Finder agent: Comparison price shopping on the Internet\n                      , in Bots and Other Internet Beasties, SAMS.NET, Indianapolis, IN, 1996."},{"key":"R10","unstructured":"O. Madani,\n                      Serializing an Irreducible Schedule at most Triples the Value\n                      , manuscript, 1996."},{"key":"R11","unstructured":"The Knowledge Finder Corporation, providing access to MEDLINE, 1997;"},{"key":"R11","unstructured":"available online at http:\/\/www.kfinder.com."},{"key":"R12","first-page":"17","volume":"11","author":"Mitten L.","year":"1960","journal-title":"J. Indust. Eng."},{"key":"R13","unstructured":"M. Porat,\n                      The Information Economy\n                      , U.S. Office of Telecommunications, Dept. of Commerce, Washington, D. C., 1977."},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1145\/321864.321873"},{"key":"R15","unstructured":"Secure Transaction Technology\n                      , available online at http:\/\/www.visa.com\/cgi\u2010bin\/vee\/sf\/set\/intro.html."},{"key":"R16","unstructured":"E. Selberg and O. Etzioni,\n                      Multi\u2010service search and comparison using the MetaCrawler\n                      , in Proceedings of the 4th World Wide Web Conference, Boston, MA, Elsevier, New York, 1995, pp. 195\u2013208."},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(75)90002-8"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1109\/98.403456"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539797314465","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:18:42Z","timestamp":1787336322000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539797314465"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,1]]},"references-count":20,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2000,1]]}},"alternative-id":["10.1137\/S0097539797314465"],"URL":"https:\/\/doi.org\/10.1137\/s0097539797314465","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2000,1]]}}}