Document Open Access Logo

A Framework for Searching in Graphs in the Presence of Errors

Authors Dariusz Dereniowski, Stefan Tiegel, Przemyslaw Uznanski, Daniel Wolleb-Graf

PDF
Thumbnail PDF

File

OASIcs.SOSA.2019.4.pdf
  • Filesize: 0.51 MB
  • 17 pages

Document Identifiers

Author Details

Dariusz Dereniowski
Stefan Tiegel
Przemyslaw Uznanski
Daniel Wolleb-Graf

Cite As Get BibTex

Dariusz Dereniowski, Stefan Tiegel, Przemyslaw Uznanski, and Daniel Wolleb-Graf. A Framework for Searching in Graphs in the Presence of Errors. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/OASIcs.SOSA.2019.4

Abstract

We consider a problem of searching for an unknown target vertex t in a (possibly edge-weighted) graph. Each vertex-query points to a vertex v and the response either admits that v is the target or provides any neighbor s of v that lies on a shortest path from v to t. This model has been introduced for trees by Onak and Parys [FOCS 2006] and for general graphs by Emamjomeh-Zadeh et al. [STOC 2016]. In the latter, the authors provide algorithms for the error-less case and for the independent noise model (where each query independently receives an erroneous answer with known probability p<1/2 and a correct one with probability 1-p).
We study this problem both with adversarial errors and independent noise models. First, we show an algorithm that needs at most (log_2 n)/(1 - H(r)) queries in case of adversarial errors, where the adversary is bounded with its rate of errors by a known constant r<1/2. Our algorithm is in fact a simplification of previous work, and our refinement lies in invoking an amortization argument. We then show that our algorithm coupled with a Chernoff bound argument leads to a simpler algorithm for the independent noise model and has a query complexity that is both simpler and asymptotically better than the one of Emamjomeh-Zadeh et al. [STOC 2016].
Our approach has a wide range of applications. First, it improves and simplifies the Robust Interactive Learning framework proposed by Emamjomeh-Zadeh and Kempe [NIPS 2017]. Secondly, performing analogous analysis for edge-queries (where a query to an edge e returns its endpoint that is closer to the target) we actually recover (as a special case) a noisy binary search algorithm that is asymptotically optimal, matching the complexity of Feige et al. [SIAM J. Comput. 1994]. Thirdly, we improve and simplify upon an algorithm for searching of unbounded domains due to Aslam and Dhagat [STOC 1991].

Subject Classification

Keywords
  • graph algorithms
  • noisy binary search
  • query complexity
  • reliability

Metrics

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

References

  1. Dana Angluin. Queries and Concept Learning. Machine Learning, 2(4):319-342, 1987. URL: http://dx.doi.org/10.1007/BF00116828.
  2. Javed A Aslam. Noise tolerant algorithms for learning and searching. PhD thesis, Massachusetts Institute of Technology, 1995. Google Scholar
  3. Pranjal Awasthi, Maria-Florina Balcan, and Konstantin Voevodski. Local algorithms for interactive clustering. Journal of Machine Learning Research, 18:3:1-3:35, 2017. URL: http://jmlr.org/papers/v18/15-085.html.
  4. Maria-Florina Balcan and Avrim Blum. Clustering with Interactive Feedback. In Algorithmic Learning Theory, 19th International Conference, ALT 2008, Budapest, Hungary, October 13-16, 2008. Proceedings, pages 316-328, 2008. URL: http://dx.doi.org/10.1007/978-3-540-87987-9_27.
  5. Michael Ben-Or and Avinatan Hassidim. The Bayesian Learner is Optimal for Noisy Binary Search (and Pretty Good for Quantum as Well). In FOCS, pages 221-230, 2008. URL: http://dx.doi.org/10.1109/FOCS.2008.58.
  6. Elvyn R. Berlekamp. Block Coding For The Binary Symmetric Channel With Noiseless, Delayless Feedback, pages 61-88. Wiley &Sons, New York, 1968. Google Scholar
  7. Lucas Boczkowski, Amos Korman, and Yoav Rodeh. Searching a Tree with Permanently Noisy Advice. CoRR, abs/1611.01403, 2016. URL: http://arxiv.org/abs/1611.01403.
  8. Ryan S. Borgstrom and S. Rao Kosaraju. Comparison-based search in the presence of errors. In STOC, pages 130-136, 1993. URL: http://dx.doi.org/10.1145/167088.167129.
  9. Ferdinando Cicalese. Fault-Tolerant Search Algorithms: Reliable Computation with Unreliable Information. Springer Publishing Company, Incorporated, 2013. Google Scholar
  10. Ferdinando Cicalese, Tobias Jacobs, Eduardo Sany Laber, and Caio Dias Valentim. The binary identification problem for weighted trees. Theor. Comput. Sci., 459:100-112, 2012. URL: http://dx.doi.org/10.1016/j.tcs.2012.06.023.
  11. 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: http://dx.doi.org/10.1016/j.tcs.2016.07.019.
  12. Argyrios Deligkas, George B. Mertzios, and Paul G. Spirakis. Binary Search in Graphs Revisited. In MFCS, pages 20:1-20:14, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.MFCS.2017.20.
  13. Christian Deppe. Coding with Feedback and Searching with Lies, pages 27-70. Springer Berlin Heidelberg, Berlin, Heidelberg, 2007. URL: http://dx.doi.org/10.1007/978-3-540-32777-6_2.
  14. Dariusz Dereniowski. Edge ranking of weighted trees. Discrete Applied Mathematics, 154(8):1198-1209, 2006. URL: http://dx.doi.org/10.1016/j.dam.2005.11.005.
  15. Dariusz Dereniowski. Edge ranking and searching in partial orders. Discrete Applied Mathematics, 156(13):2493-2500, 2008. URL: http://dx.doi.org/10.1016/j.dam.2008.03.007.
  16. Dariusz Dereniowski, Adrian Kosowski, Przemyslaw Uznański, and Mengchuan Zou. Approximation Strategies for Generalized Binary Search in Weighted Trees. In ICALP, pages 84:1-84:14, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2017.84.
  17. Dariusz Dereniowski and Adam Nadolski. Vertex rankings of chordal graphs and weighted trees. Inf. Process. Lett., 98(3):96-100, 2006. URL: http://dx.doi.org/10.1016/j.ipl.2005.12.006.
  18. Ehsan Emamjomeh-Zadeh and David Kempe. A General Framework for Robust Interactive Learning. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA, pages 7085-7094, 2017. URL: http://papers.nips.cc/paper/7283-a-general-framework-for-robust-interactive-learning.
  19. Ehsan Emamjomeh-Zadeh, David Kempe, and Vikrant Singhal. Deterministic and probabilistic binary search in graphs. In STOC, pages 519-532, 2016. URL: http://dx.doi.org/10.1145/2897518.2897656.
  20. Uriel Feige, Prabhakar Raghavan, David Peleg, and Eli Upfal. Computing with Noisy Information. SIAM J. Comput., 23(5):1001-1018, 1994. URL: http://dx.doi.org/10.1137/S0097539791195877.
  21. Nicolas Hanusse, David Ilcinkas, Adrian Kosowski, and Nicolas Nisse. Locating a target with an agent guided by unreliable local advice: how to beat the random walk when you have a clock? In PODC, pages 355-364, 2010. URL: http://dx.doi.org/10.1145/1835698.1835781.
  22. Nicolas Hanusse, Dimitris J. Kavvadias, Evangelos Kranakis, and Danny Krizanc. Memoryless search algorithms in a network with faulty advice. Theor. Comput. Sci., 402(2-3):190-198, 2008. URL: http://dx.doi.org/10.1016/j.tcs.2008.04.034.
  23. Nicolas Hanusse, Evangelos Kranakis, and Danny Krizanc. Searching with mobile agents in networks with liars. Discrete Applied Mathematics, 137(1):69-85, 2004. URL: http://dx.doi.org/10.1016/S0166-218X(03)00189-6.
  24. Richard M. Karp and Robert Kleinberg. Noisy binary search and its applications. In SODA, pages 881-890, 2007. URL: http://dl.acm.org/citation.cfm?id=1283383.1283478.
  25. Michael J. Kearns and Umesh V. Vazirani. An Introduction to Computational Learning Theory. MIT Press, 1994. URL: https://mitpress.mit.edu/books/introduction-computational-learning-theory.
  26. Evangelos Kranakis and Danny Krizanc. Searching with Uncertainty. In SIROCCO'99, 6th International Colloquium on Structural Information & Communication Complexity, Lacanau-Ocean, France, 1-3 July, 1999, pages 194-203, 1999. Google Scholar
  27. Eduardo Sany Laber, Ruy Luiz Milidiú, and Artur Alves Pessoa. On binary searching with non-uniform costs. In SODA, pages 855-864, 2001. URL: http://dl.acm.org/citation.cfm?id=365411.365796.
  28. Tak Wah Lam and Fung Ling Yue. Optimal Edge Ranking of Trees in Linear Time. Algorithmica, 30(1):12-33, 2001. URL: http://dx.doi.org/10.1007/s004530010076.
  29. Nick Littlestone. Learning Quickly When Irrelevant Attributes Abound: A New Linear-threshold Algorithm. Machine Learning, 2(4):285-318, 1987. URL: http://dx.doi.org/10.1007/BF00116827.
  30. Tie-Yan Liu. Learning to Rank for Information Retrieval. Springer, 2011. URL: http://dx.doi.org/10.1007/978-3-642-14267-3.
  31. Shay Mozes, Krzysztof Onak, and Oren Weimann. Finding an optimal tree searching strategy in linear time. In SODA, pages 1096-1105, 2008. URL: http://dl.acm.org/citation.cfm?id=1347082.1347202.
  32. S. Muthukrishnan. On Optimal Strategies for Searching in Presence of Errors. In SODA, pages 680-689, 1994. URL: http://dl.acm.org/citation.cfm?id=314464.314672.
  33. Jaroslav Nesetril and Patrice Ossona de Mendez. Tree-depth, subgraph coloring and homomorphism bounds. Eur. J. Comb., 27(6):1022-1041, 2006. URL: http://dx.doi.org/10.1016/j.ejc.2005.01.010.
  34. Krzysztof Onak and Pawel Parys. Generalization of Binary Search: Searching in Trees and Forest-Like Partial Orders. In FOCS, pages 379-388, 2006. URL: http://dx.doi.org/10.1109/FOCS.2006.32.
  35. Andrzej Pelc. Searching games with errors - fifty years of coping with liars. Theoretical Computer Science, 270(1):71-109, 2002. URL: http://dx.doi.org/10.1016/S0304-3975(01)00303-6.
  36. Filip Radlinski and Thorsten Joachims. Query chains: learning to rank from implicit feedback. In Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Chicago, Illinois, USA, August 21-24, 2005, pages 239-248, 2005. URL: http://dx.doi.org/10.1145/1081870.1081899.
  37. Ronald L. Rivest, Albert R. Meyer, Daniel J. Kleitman, Karl Winklmann, and Joel Spencer. Coping with errors in binary search procedures. Journal of Computer and System Sciences, 20(3):396-404, 1980. Google Scholar
  38. Alfréd Rényi. On a problem of information theory. MTA Mat. Kut. Int. Kozl., 6B:505-516, 1961. Google Scholar
  39. Alejandro A. Schäffer. Optimal Node Ranking of Trees in Linear Time. Inf. Process. Lett., 33(2):91-96, 1989. URL: http://dx.doi.org/10.1016/0020-0190(89)90161-0.
  40. Burr Settles. Active Learning. Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan & Claypool Publishers, 2012. URL: http://dx.doi.org/10.2200/S00429ED1V01Y201207AIM018.
  41. Stanislaw M. Ulam. Adventures of a Mathematician. Scribner, New York, 1976. Google Scholar
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