Document Open Access Logo

Constant-Factor Approximation Algorithm for Binary Search in Trees with Monotonic Query Times

Authors Dariusz Dereniowski , Izajasz Wrosz

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2022.42.pdf
  • Filesize: 0.69 MB
  • 15 pages

Document Identifiers

Author Details

Dariusz Dereniowski
  • Faculty of Electronics, Telecommunications and Informatics, Gdańsk University of Technology, Poland
Izajasz Wrosz
  • Faculty of Electronics, Telecommunications and Informatics, Gdańsk University of Technology, Poland
  • Intel, Gdańsk, Poland

Funding

Work partially supported by National Science Centre (Poland) grant number 2018/31/B/ ST6/00820.

Cite As Get BibTex

Dariusz Dereniowski and Izajasz Wrosz. Constant-Factor Approximation Algorithm for Binary Search in Trees with Monotonic Query Times. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 42:1-42:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.MFCS.2022.42

Abstract

We consider a generalization of binary search in linear orders to the domain of weighted trees. The goal is to design an adaptive search strategy whose aim is to locate an unknown target vertex of a given tree. Each query to a vertex v incurs a non-negative cost ω(v) (that can be interpreted as the duration of the query) and returns a feedback that either v is the target or the edge incident to v is given that is on the path towards the target. The goal of the algorithm is to find a strategy that minimizes the worst-case total cost. We propose a constant-factor approximation algorithm for trees with a monotonic cost function. Such function is defined as follows: there exists a vertex r such that for any two vertices u,v on any path connecting r with a leaf it holds that if u is closer to r than v, then ω(u) ≥ ω(v). The best known approximation algorithm for general weight functions has the ratio of O{√{log n}} [Dereniowski et al. ICALP 2017] and it remains as a challenging open question whether constant-factor approximation is achievable in such case. This gives our first motivation towards considering monotonic cost functions and the second one lies in the potential applications.

Subject Classification

ACM Subject Classification
  • Theory of computation
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Graph algorithms analysis
Keywords
  • binary search
  • graph search
  • approximation algorithm
  • query complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Alok Aggarwal, Bowen Alpern, Ashok K. Chandra, and Marc Snir. A model for hierarchical memory. In Alfred V. Aho, editor, STOC 1987, pages 305-314. ACM, 1987. URL: https://doi.org/10.1145/28395.28428.
  2. Haris Angelidakis. Shortest path queries, graph partitioning and covering problems in worst and beyond worst case settings. CoRR, abs/1807.09389, 2018. URL: http://arxiv.org/abs/1807.09389.
  3. Yosi Ben-Asher, Eitan Farchi, and Ilan Newman. Optimal search in trees. SIAM J. Comput., 28(6):2090-2102, 1999. URL: https://doi.org/10.1137/S009753979731858X.
  4. Piotr Borowiecki, Dariusz Dereniowski, and Dorota Osula. The complexity of bicriteria tree-depth. In Evripidis Bampis and Aris Pagourtzis, editors, FCT 2021, volume 12867 of Lecture Notes in Computer Science, pages 100-113. Springer, 2021. URL: https://doi.org/10.1007/978-3-030-86593-1_7.
  5. Ferdinando Cicalese, Tobias Jacobs, Eduardo Sany Laber, and Caio Dias Valentim. Binary identification problems for weighted trees. In Frank Dehne, John Iacono, and Jörg-Rüdiger Sack, editors, WADS 2011, volume 6844 of Lecture Notes in Computer Science, pages 255-266. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-22300-6_22.
  6. Ferdinando Cicalese, Balázs Keszegh, Bernard Lidický, Dömötör Pálvölgyi, and Tomás Valla. On the tree search problem with non-uniform costs. Theor. Comput. Sci., 647:22-32, 2016. URL: https://doi.org/10.1016/j.tcs.2016.07.019.
  7. Dariusz Dereniowski. Edge ranking of weighted trees. Discret. Appl. Math., 154(8):1198-1209, 2006. URL: https://doi.org/10.1016/j.dam.2005.11.005.
  8. Dariusz Dereniowski, Adrian Kosowski, Przemyslaw Uznanski, and Mengchuan Zou. Approximation strategies for generalized binary search in weighted trees. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, ICALP 2017, volume 80 of LIPIcs, pages 84:1-84:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.ICALP.2017.84.
  9. Dariusz Dereniowski and Marek Kubale. Cholesky factorization of matrices in parallel and ranking of graphs. In Roman Wyrzykowski, Jack J. Dongarra, Marcin Paprzycki, and Jerzy Wasniewski, editors, PPAM 2003, volume 3019 of Lecture Notes in Computer Science, pages 985-992. Springer, 2003. URL: https://doi.org/10.1007/978-3-540-24669-5_127.
  10. Dariusz Dereniowski and Marek Kubale. Efficient parallel query processing by graph ranking. Fundam. Informaticae, 69(3):273-285, 2006. Google Scholar
  11. Dariusz Dereniowski, Aleksander Lukasiewicz, and Przemyslaw Uznanski. An efficient noisy binary search in graphs via median approximation. In Paola Flocchini and Lucia Moura, editors, IWOCA 2021, volume 12757 of Lecture Notes in Computer Science, pages 265-281. Springer, 2021. URL: https://doi.org/10.1007/978-3-030-79987-8_19.
  12. Dariusz Dereniowski and Adam Nadolski. Vertex rankings of chordal graphs and weighted trees. Inf. Process. Lett., 98(3):96-100, 2006. URL: https://doi.org/10.1016/j.ipl.2005.12.006.
  13. Dariusz Dereniowski, Stefan Tiegel, Przemyslaw Uznanski, and Daniel Wolleb-Graf. A framework for searching in graphs in the presence of errors. In Jeremy T. Fineman and Michael Mitzenmacher, editors, SOSA 2019, volume 69 of OASIcs, pages 4:1-4:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/OASIcs.SOSA.2019.4.
  14. Ehsan Emamjomeh-Zadeh, David Kempe, Mohammad Mahdian, and Robert E. Schapire. Interactive learning of a dynamic structure. In Aryeh Kontorovich and Gergely Neu, editors, ALT 2020, volume 117 of Proceedings of Machine Learning Research, pages 277-296. PMLR, 2020. Google Scholar
  15. Ehsan Emamjomeh-Zadeh, David Kempe, and Vikrant Singhal. Deterministic and probabilistic binary search in graphs. In Daniel Wichs and Yishay Mansour, editors, STOC 2016, pages 519-532. ACM, 2016. URL: https://doi.org/10.1145/2897518.2897656.
  16. Mine Su Erturk and Kuang Xu. Private genetic geneaology search. Research papers, Stanford University, Graduate School of Business, 2021. URL: https://EconPapers.repec.org/RePEc:ecl:stabus:3973.
  17. Ananth V. Iyer, H. Donald Ratliff, and Gopalakrishnan Vijayan. Optimal node ranking of trees. Inf. Process. Lett., 28(5):225-229, 1988. URL: https://doi.org/10.1016/0020-0190(88)90194-9.
  18. Ananth V. Iyer, H. Donald Ratliff, and Gopalakrishnan Vijayan. On an edge ranking problem of trees and graphs. Discret. Appl. Math., 30(1):43-52, 1991. URL: https://doi.org/10.1016/0166-218X(91)90012-L.
  19. William J. Knight. Search in an ordered array having variable probe cost. SIAM J. Comput., 17(6):1203-1214, 1988. URL: https://doi.org/10.1137/0217076.
  20. Donald E. Knuth. The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley, 1973. Google Scholar
  21. Eduardo Sany Laber, Ruy Luiz Milidiú, and Artur Alves Pessoa. On binary searching with non-uniform costs. In S. Rao Kosaraju, editor, SODA 2001, pages 855-864. ACM/SIAM, 2001. Google Scholar
  22. Tak Wah Lam and Fung Ling Yue. Optimal edge ranking of trees in linear time. In Howard J. Karloff, editor, SODA 1998, pages 436-445. ACM/SIAM, 1998. Google Scholar
  23. Shay Mozes, Krzysztof Onak, and Oren Weimann. Finding an optimal tree searching strategy in linear time. In Shang-Hua Teng, editor, SODA 2008, pages 1096-1105. SIAM, 2008. Google Scholar
  24. Gonzalo Navarro, Ricardo A. Baeza-Yates, Eduardo F. Barbosa, Nivio Ziviani, and Walter Cunto. Binary searching with nonuniform costs and its application to text retrieval. Algorithmica, 27(2):145-169, 2000. URL: https://doi.org/10.1007/s004530010010.
  25. Jaroslav Nešetřil and Patrice Ossona de Mendez. Tree-depth, subgraph coloring and homomorphism bounds. Eur. J. Comb., 27(6):1022-1041, 2006. URL: https://doi.org/10.1016/j.ejc.2005.01.010.
  26. Krzysztof Onak and Pawel Parys. Generalization of binary search: Searching in trees and forest-like partial orders. In FOCS 2006, pages 379-388. IEEE Computer Society, 2006. URL: https://doi.org/10.1109/FOCS.2006.32.
  27. Sherif Sakr, Angela Bonifati, Hannes Voigt, Alexandru Iosup, Khaled Ammar, Renzo Angles, Walid G. Aref, Marcelo Arenas, Maciej Besta, Peter A. Boncz, Khuzaima Daudjee, Emanuele Della Valle, Stefania Dumbrava, Olaf Hartig, Bernhard Haslhofer, Tim Hegeman, Jan Hidders, Katja Hose, Adriana Iamnitchi, Vasiliki Kalavri, Hugo Kapp, Wim Martens, M. Tamer Özsu, Eric Peukert, Stefan Plantikow, Mohamed Ragab, Matei Ripeanu, Semih Salihoglu, Christian Schulz, Petra Selmer, Juan F. Sequeda, Joshua Shinavier, Gábor Szárnyas, Riccardo Tommasini, Antonino Tumeo, Alexandru Uta, Ana Lucia Varbanescu, Hsiang-Yun Wu, Nikolay Yakovets, Da Yan, and Eiko Yoneki. The future is big graphs: a community view on graph processing systems. Commun. ACM, 64(9):62-71, 2021. URL: https://doi.org/10.1145/3434642.
  28. Alejandro A. Schäffer. Optimal node ranking of trees in linear time. Inf. Process. Lett., 33(2):91-96, 1989. URL: https://doi.org/10.1016/0020-0190(89)90161-0.
  29. Arunabha Sen, Haiyong Deng, and Sumanta Guha. On a graph partition problem with application to VLSI layout. Inf. Process. Lett., 43(2):87-94, 1992. URL: https://doi.org/10.1016/0020-0190(92)90017-P.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact