{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T12:41:03Z","timestamp":1760100063672},"reference-count":22,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2008,9,12]],"date-time":"2008-09-12T00:00:00Z","timestamp":1221177600000},"content-version":"unspecified","delay-in-days":5764,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[1992,12]]},"abstract":"<jats:p>There is a simple greedy algorithm for seeking large values of a function <jats:italic>f<\/jats:italic> defined on the vertices of the binary tree. Modeling <jats:italic>f<\/jats:italic> as a random function whose increments along edges are i.i.d., we show that (under a natural assumption) the values found by the greedy algorithm grow linearly in time, with rate specified in terms of a fixed-point identity for distributions.<\/jats:p>","DOI":"10.1017\/s096354830000033x","type":"journal-article","created":{"date-parts":[[2008,9,12]],"date-time":"2008-09-12T11:18:24Z","timestamp":1221218304000},"page":"281-293","source":"Crossref","is-referenced-by-count":9,"title":["Greedy Search on the Binary Tree with Random Edge-Weights"],"prefix":"10.1017","volume":"1","author":[{"given":"David","family":"Aldous","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2008,9,12]]},"reference":[{"key":"S096354830000033X_ref001","unstructured":"[1] Aldous D. J. (1992) Random Walk on Galton-Watson trees, unpublished."},{"key":"S096354830000033X_ref019","volume-title":"Disorder in Physical Systems","author":"McDiarmid","year":"1990"},{"key":"S096354830000033X_ref002","volume-title":"Applied Probability and Queues","author":"Asmussen","year":"1987"},{"key":"S096354830000033X_ref015","volume-title":"The Art of Computer Programing","volume":"1","author":"Knuth","year":"1968"},{"key":"S096354830000033X_ref013","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(83)80006-X"},{"key":"S096354830000033X_ref017","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176989920"},{"key":"S096354830000033X_ref011","volume-title":"An introduction to Probability Theory and its Applictations","volume":"II","author":"Feller","year":"1966"},{"key":"S096354830000033X_ref004","volume-title":"Seminar on Stochastic Processes","author":"Benjamini","year":"1991"},{"key":"S096354830000033X_ref007","doi-asserted-by":"publisher","DOI":"10.2307\/3213469"},{"key":"S096354830000033X_ref018","volume-title":"Evolution of Random Search Trees","author":"Mahmoud","year":"1992"},{"key":"S096354830000033X_ref006","volume-title":"Tree-indexed random walk and first passage percolation","author":"Benjamini","year":"1992"},{"key":"S096354830000033X_ref003","doi-asserted-by":"publisher","DOI":"10.2307\/1427052"},{"key":"S096354830000033X_ref009","volume-title":"Probability: Theory and Examples","author":"Durrett","year":"1991"},{"key":"S096354830000033X_ref022","doi-asserted-by":"publisher","DOI":"10.1016\/0304-4149(92)90035-O"},{"key":"S096354830000033X_ref016","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177005779"},{"key":"S096354830000033X_ref010","doi-asserted-by":"publisher","DOI":"10.1007\/BF00532962"},{"key":"S096354830000033X_ref008","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177005839"},{"key":"S096354830000033X_ref021","volume-title":"Probability metrics and recursive algorithms","author":"Rachev","year":"1992"},{"key":"S096354830000033X_ref005","volume-title":"Random walk on trees and capacity in the interval","author":"Benjamini","year":"1992"},{"key":"S096354830000033X_ref012","volume-title":"A Second Course in Stochastic Processes","author":"Karlin","year":"1981"},{"key":"S096354830000033X_ref014","volume-title":"A queueing network model leading to a second-order Lindley equation","author":"Karpelevitch","year":"1991"},{"key":"S096354830000033X_ref020","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176995581"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S096354830000033X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T20:07:28Z","timestamp":1558037248000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S096354830000033X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,12]]},"references-count":22,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1992,12]]}},"alternative-id":["S096354830000033X"],"URL":"https:\/\/doi.org\/10.1017\/s096354830000033x","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,12]]}}}