Top

Published in:

2021 | OriginalPaper | Chapter

Algorithms that Access the Input via Queries

Author : Thomas Erlebach

Published in: SOFSEM 2021: Theory and Practice of Computer Science

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Problems where an algorithm cannot simply access the whole input but needs to obtain information about it using queries arise naturally in many settings. We discuss different aspects of models where an algorithm needs to query the input, and of how the performance of algorithms for such models can be measured. After that, we give some concrete examples of algorithmic settings and results for scenarios where algorithms access the input via queries. Finally, we discuss recent results for the setting of computing with explorable uncertainty with parallel queries and with untrusted predictions.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

next chapter Towards Knowledge Exchange: State-of-the-Art and Open Problems

Audet, C.: A survey on direct search methods for Blackbox optimization and their applications. In: Pardalos, P.M., Rassias, T.M. (eds.) Mathematics Without Boundaries, pp. 31–56. Springer, New York (2014). https://doi.org/10.1007/978-1-4939-1124-0_2CrossRef

Beame, P., Har-Peled, S., Ramamoorthy, S.N., Rashtchian, C., Sinha, M.: Edge estimation with independent set oracles. ACM Trans. Algorithms 16(4), 52:1–52:27 (2020). https://doi.org/10.1145/3404867MathSciNetCrossRef

Beerliova, Z., et al.: Network discovery and verification. IEEE J. Sel. Areas Commun. 24(12), 2168–2181 (2006). https://doi.org/10.1109/JSAC.2006.884015CrossRef

Canonne, C.L., Gur, T.: An adaptivity hierarchy theorem for property testing. Comput. Complex. 27(4), 671–716 (2018). https://doi.org/10.1007/s00037-018-0168-4MathSciNetCrossRefMATH

Dobzinski, S., Nisan, N., Oren, S.: Economic efficiency requires interaction. Games Econ. Behav. 118, 589–608 (2019). https://doi.org/10.1016/j.geb.2018.02.010MathSciNetCrossRefMATH

Erlebach, T., Hoffmann, M.: Query-competitive algorithms for computing with uncertainty. Bulletin EATCS 116, 22–39 (2015). http://bulletin.eatcs.org/index.php/beatcs/article/view/335

Erlebach, T., Hoffmann, M., de Lima, M.S.: Round-competitive algorithms for uncertainty problems with parallel queries (2020), unpublished manuscript

Erlebach, T., Hoffmann, M., de Lima, M.S., Megow, N., Schlöter, J.: Untrusted predictions improve trustable query policies. CoRR abs/2011.07385 (2020). https://arxiv.org/abs/2011.07385

Goldreich, O.: Introduction to Property Testing. Cambridge University Press, Israel (2017). https://doi.org/10.1017/9781108135252

10.

Graur, A., Pollner, T., Ramaswamy, V., Weinberg, S.M.: New query lower bounds for submodular function minimization. In: Vidick, T. (ed.) 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). LIPIcs, vol. 151, pp. 64:1–64:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020). https://doi.org/10.4230/LIPIcs.ITCS.2020.64

11.

Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics, vol. 2. Springer, Berlin (1988). https://doi.org/10.1007/978-3-642-97881-4

12.

Halldórsson, M.M., de Lima, M.S.: Query-competitive sorting with uncertainty. In: Rossmanith, P., Heggernes, P., Katoen, J. (eds.) 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). LIPIcs, vol. 138, pp. 7:1–7:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019). https://doi.org/10.4230/LIPIcs.MFCS.2019.7

13.

Hoffmann, M., Erlebach, T., Krizanc, D., Mihalák, M., Raman, R.: Computing minimum spanning trees with uncertainty. In: Albers, S., Weil, P. (eds.) 25th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2008). LIPIcs, vol. 1, pp. 277–288. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany (2008). https://doi.org/10.4230/LIPIcs.STACS.2008.1358

14.

Jain, S., Stephan, F.: Query-based learning. In: Sammut, C., Webb, G.I. (eds.) Encyclopedia of Machine Learning and Data Mining, pp. 1044–1047. Springer, Berlin (2017). https://doi.org/10.1007/978-1-4899-7687-1_694

15.

Kahan, S.: A model for data in motion. In: Koutsougeras, C., Vitter, J.S. (eds.) 23rd Annual ACM Symposium on Theory of Computing (STOC 1991), pp. 265–277 (1991). https://doi.org/10.1145/103418.103449

16.

Kannan, S., Mathieu, C., Zhou, H.: Graph reconstruction and verification. ACM Trans. Algorithms 14(4), 40:1–40:30 (2018). https://doi.org/10.1145/3199606MathSciNetCrossRefMATH

17.

Mazzawi, H.: Optimally reconstructing weighted graphs using queries. In: Charikar, M. (ed.) 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), pp. 608–615. SIAM (2010). https://doi.org/10.1137/1.9781611973075.51

18.

Megow, N., Meißner, J., Skutella, M.: Randomization helps computing a minimum spanning tree under uncertainty. SIAM J. Comput. 46(4), 1217–1240 (2017). https://doi.org/10.1137/16M1088375MathSciNetCrossRefMATH

19.

Meißner, J.: Uncertainty Exploration: Algorithms, Competitive Analysis, and Computational Experiments. Ph.D. thesis, Technische Universität Berlin (2018). https://doi.org/10.14279/depositonce-7327

20.

Nisan, N.: The demand query model for bipartite matching. CoRR abs/1906.04213 (2019). http://arxiv.org/abs/1906.04213, to appear in SODA 2021

21.

Purohit, M., Svitkina, Z., Kumar, R.: Improving online algorithms via ML predictions. In: Bengio, S., Wallach, H.M., Larochelle, H., Grauman, K., Cesa-Bianchi, N., Garnett, R. (eds.) Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018 (NeurIPS 2018), pp. 9684–9693 (2018). http://papers.nips.cc/paper/8174-improving-online-algorithms-via-ml-predictions

22.

Rubinstein, A., Schramm, T., Weinberg, S.M.: Computing exact minimum cuts without knowing the graph. In: Karlin, A.R. (ed.) 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), LIPIcs, vol. 94, pp. 39:1–39:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018). https://doi.org/10.4230/LIPIcs.ITCS.2018.39

23.

Sen, S., Muralidhara, V.N.: The covert set-cover problem with application to network discovery. In: Rahman, M.S., Fujita, S. (eds.) WALCOM 2010. LNCS, vol. 5942, pp. 228–239. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-11440-3_21CrossRef

Title: Algorithms that Access the Input via Queries
Author: Thomas Erlebach
Publisher: Springer International Publishing
Book: SOFSEM 2021: Theory and Practice of Computer Science
Print ISBN: 978-3-030-67730-5

Electronic ISBN: 978-3-030-67731-2

Copyright Year: 2021
DOI: https://doi.org/10.1007/978-3-030-67731-2_1

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner