{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T22:33:50Z","timestamp":1772490830024,"version":"3.50.1"},"publisher-location":"Cham","reference-count":17,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030808785","type":"print"},{"value":"9783030808792","type":"electronic"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,7,6]],"date-time":"2021-07-06T00:00:00Z","timestamp":1625529600000},"content-version":"vor","delay-in-days":186,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The problem of scheduling with testing in the framework of explorable uncertainty models environments where some preliminary action can influence the duration of a task. In the model, each job has an unknown processing time that can be revealed by running a test. Alternatively, jobs may be run untested for the duration of a given upper limit. Recently, D\u00fcrr et al. [4] have studied the setting where all testing times are of unit size and have given lower and upper bounds for the objectives of minimizing the sum of completion times and the makespan on a single machine. In this paper, we extend the problem to non-uniform testing times and present the first competitive algorithms. The general setting is motivated for example by online user surveys for market prediction or querying centralized databases in distributed computing. Introducing general testing times gives the problem a new flavor and requires updated methods with new techniques in the analysis. We present constant competitive ratios for the objective of minimizing the sum of completion times in the deterministic case, both in the non-preemptive and preemptive setting. For the preemptive setting, we additionally give a first lower bound. We also present a randomized algorithm with improved competitive ratio. Furthermore, we give tight competitive ratios for the objective of minimizing the makespan, both in the deterministic and the randomized setting.<\/jats:p>","DOI":"10.1007\/978-3-030-80879-2_9","type":"book-chapter","created":{"date-parts":[[2021,7,5]],"date-time":"2021-07-05T08:10:56Z","timestamp":1625472656000},"page":"127-142","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Explorable Uncertainty in Scheduling with Non-uniform Testing Times"],"prefix":"10.1007","author":[{"given":"Susanne","family":"Albers","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"Eckl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,7,6]]},"reference":[{"key":"9_CR1","unstructured":"Albers, S., Eckl, A.: Explorable uncertainty in scheduling with non-uniform testing times (2020). https:\/\/arxiv.org\/abs\/2009.13316"},{"key":"9_CR2","doi-asserted-by":"publisher","unstructured":"Bruce, R., Hoffmann, M., Krizanc, D., Raman, R.: Efficient update strategies for geometric computing with uncertainty. Theor. Comput. Syst. 38(4), 411\u2013423 (2005). https:\/\/doi.org\/10.1007\/s00224-004-1180-4","DOI":"10.1007\/s00224-004-1180-4"},{"issue":"4","key":"9_CR3","doi-asserted-by":"publisher","first-page":"785","DOI":"10.1006\/jcss.2002.1828","volume":"64","author":"M Charikar","year":"2002","unstructured":"Charikar, M., Fagin, R., Guruswami, V., Kleinberg, J., Raghavan, P., Sahai, A.: Query strategies for priced information. J. Comput. Syst. Sci. 64(4), 785\u2013819 (2002). https:\/\/doi.org\/10.1006\/jcss.2002.1828","journal-title":"J. Comput. Syst. Sci."},{"key":"9_CR4","doi-asserted-by":"publisher","unstructured":"D\u00fcrr, C., Erlebach, T., Megow, N., Mei\u00dfner, J.: Scheduling with explorable uncertainty. In: Karlin, A.R. (ed.) 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), vol. 94, pp. 30:1\u201330:14. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2018). https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2018.30","DOI":"10.4230\/LIPIcs.ITCS.2018.30"},{"key":"9_CR5","unstructured":"Erlebach, T., Hoffmann, M.: Query-competitive algorithms for computing with uncertainty. Bull. EATCS (116), 22\u201339 (2015)"},{"key":"9_CR6","doi-asserted-by":"publisher","unstructured":"Erlebach, T., Hoffmann, M., Krizanc, D., Mihal\u2019\u00e1k, M., Raman, R.: Computing minimum spanning trees with uncertainty. In: Albers, S., Weil, P. (eds.) 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), vol. 1, pp. 277\u2013288. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2008). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2008.1358","DOI":"10.4230\/LIPIcs.STACS.2008.1358"},{"key":"9_CR7","doi-asserted-by":"publisher","unstructured":"Feder, T., Motwani, R., O\u2019Callaghan, L., Olston, C., Panigrahy, R.: Computing shortest paths with uncertainty. J. Algorithms 62(1), 1\u201318 (2007). https:\/\/doi.org\/10.1016\/j.jalgor.2004.07.005","DOI":"10.1016\/j.jalgor.2004.07.005"},{"key":"9_CR8","doi-asserted-by":"publisher","unstructured":"Feder, T., Motwani, R., Panigrahy, R., Olston, C., Widom, J.: Computing the median with uncertainty. SIAM J. Comput. 32(2), 538\u2013547 (2003). https:\/\/doi.org\/10.1137\/S0097539701395668","DOI":"10.1137\/S0097539701395668"},{"key":"9_CR9","doi-asserted-by":"publisher","unstructured":"Goerigk, M., Gupta, M., Ide, J., Sch\u00f6bel, A., Sen, S.: The robust knapsack problem with queries. Comput. Oper. Res. 55, 12\u201322 (2015). https:\/\/doi.org\/10.1016\/j.cor.2014.09.010","DOI":"10.1016\/j.cor.2014.09.010"},{"key":"9_CR10","doi-asserted-by":"publisher","unstructured":"Gupta, M., Sabharwal, Y., Sen, S.: The update complexity of selection and related problems. In: Chakraborty, S., Kumar, A. (eds.) IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011). Leibniz International Proceedings in Informatics (LIPIcs), vol. 13, pp. 325\u2013338. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2011). https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2011.325","DOI":"10.4230\/LIPIcs.FSTTCS.2011.325"},{"key":"9_CR11","doi-asserted-by":"publisher","unstructured":"Kahan, S.: A model for data in motion. In: Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing, pp. 265\u2013277. STOC 1991. Association for Computing Machinery, New York, NY, USA (1991). https:\/\/doi.org\/10.1145\/103418.103449","DOI":"10.1145\/103418.103449"},{"key":"9_CR12","doi-asserted-by":"publisher","unstructured":"Khanna, S., Tan, W.C.: On computing functions with uncertainty. In: Proceedings of the Twentieth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pp. 171\u2013182. PODS 2001. Association for Computing Machinery, New York, NY, USA (2001). https:\/\/doi.org\/10.1145\/375551.375577","DOI":"10.1145\/375551.375577"},{"key":"9_CR13","doi-asserted-by":"publisher","unstructured":"Megow, N., Mei\u00dfner, J., Skutella, M.: Randomization helps computing a minimum spanning tree under uncertainty. SIAM J. Comput. 46(4), 1217\u20131240 (2017). https:\/\/doi.org\/10.1137\/16M1088375","DOI":"10.1137\/16M1088375"},{"key":"9_CR14","unstructured":"Olston, C., Widom, J.: Offering a precision-performance tradeoff for aggregation queries over replicated data. In: 26th International Conference on Very Large Data Bases (VLDB 2000), pp. 144\u2013155. VLDB 2000. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (2000)"},{"key":"9_CR15","doi-asserted-by":"publisher","unstructured":"Pinedo, M.L.: Scheduling: Theory, Algorithms, and Systems. Springer International Publishing, 5 edn. (2016). https:\/\/doi.org\/10.1007\/978-1-4614-2361-4","DOI":"10.1007\/978-1-4614-2361-4"},{"key":"9_CR16","doi-asserted-by":"crossref","unstructured":"Singla, S.: The price of information in combinatorial optimization. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2523\u20132532. SODA 2018, Society for Industrial and Applied Mathematics, USA (2018)","DOI":"10.1137\/1.9781611975031.161"},{"key":"9_CR17","doi-asserted-by":"publisher","unstructured":"Weitzman, M.L.: Optimal search for the best alternative. Econometrica 47(3), 641\u2013654 (1979). https:\/\/doi.org\/10.2307\/1910412","DOI":"10.2307\/1910412"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-80879-2_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,1]],"date-time":"2021-12-01T22:05:13Z","timestamp":1638396313000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-80879-2_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030808785","9783030808792"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-80879-2_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"6 July 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WAOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Approximation and Online Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 September 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 September 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"waoa2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/algo2020.di.unipi.it\/WAOA2020\/index.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"40","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"15","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"38% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.125","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"5.95","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}