An Almost-Greedy Search on Random Binary Vectors and Random Graphs

✍ Scribed by Avner Dor; Eitan Greenshtein

• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 193 KB
• Volume: 40
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.2000.1140

✦ Synopsis

A random vector is sampled from a general binary probability space and a search goes through the coordinates until a 1-coordinate is found. A search algorithm called ''almost greedy'' is shown to posses some novel characteristics. Its expectation is shown to be sharply bounded by four times the expectation of the optimal Ž 4 . search. In addition an algorithm of complexity O n log n finds with high probability an almost-greedy search procedure. This paper also studies connectivity testing of communication networks represented by random graphs. Suppose that some edges fell from a connected graph with accordance to a known distribution and we want to find if the resulting subgraph is connected. A single test is a check for the existence of a path between two vertices of our choice. The proportion between the expectations of an almost greedy and an optimal search procedures is Ž 5 . proven to be sharply bounded by 4. Finally an algorithm of complexity O n log n finds with high probability an almost greedy search where n is the number of vertices.