{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T05:18:43Z","timestamp":1648876723693},"reference-count":18,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2000,6]]},"abstract":"<jats:p> We propose a completely general, informed randomized dynamic load balancing method called random seeking (RS) suitable for parallel algorithms with characteristics found in many search algorithms used in artificial intelligence and operations research and many divide-and-conquer algorithms. In it, source processors randomly seek out sink processors for load balancing by flinging \"probe\" messages. These probes not only locate sinks, but also collect load distribution information which is used to efficiently regulate load balancing activities. We empirically compare RS with a well-known randomized dynamic load balancing method, the random communication (RC) strategy, by using them in parallel best-first branch-and-bound algorithms on up to 512 processors of a parallel system. We find that the RC execution times are more than those of RS by 16\u201367% when used to perform combined dynamic quantitative and qualitative load balancing, and by 9\u201374% when used to perform only dynamic quantitative load balancing. <\/jats:p>","DOI":"10.1142\/s0129054100000144","type":"journal-article","created":{"date-parts":[[2002,8,24]],"date-time":"2002-08-24T21:40:19Z","timestamp":1030225219000},"page":"231-246","source":"Crossref","is-referenced-by-count":2,"title":["RANDOM SEEKING: A GENERAL, EFFICIENT, AND INFORMED RANDOMIZED SCHEME FOR DYNAMIC LOAD BALANCING"],"prefix":"10.1142","volume":"11","author":[{"given":"NIHAR R.","family":"MAHAPATRA","sequence":"first","affiliation":[{"name":"Department of Computer Science &amp; Engineering, State University of New York at Buffalo, 137 Bell Hall, Buffalo, NY 14260-2000, U.S.A."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"SHANTANU","family":"DUTT","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering &amp; Computer Science, University of Illinois at Chicago, 851 South Morgan Street (M\/C 154), Chicago, IL 60607-7053, U.S.A."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"p_1","first-page":"309","author":"Anderson S.","year":"1987","journal-title":"Proc. Second Conference on Hypercube Multiprocessors"},{"issue":"2","key":"p_3","first-page":"16","volume":"25","author":"Bixby R.E.","year":"1992","journal-title":"SIAM News"},{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1994.1106"},{"key":"p_6","author":"Eckstein J.","year":"1994","journal-title":"SIAM Journal on Optimization"},{"key":"p_8","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.39.6.657"},{"key":"p_9","first-page":"23","author":"Huang S.-R.","year":"1989","journal-title":"Proc. Eleventh Int'l Joint Conf. on Artificial Intelligence"},{"key":"p_10","first-page":"290","author":"Karp R.M.","year":"1988","journal-title":"J. of the ACM"},{"key":"p_11","doi-asserted-by":"publisher","DOI":"10.1016\/0098-1354(94)00084-0"},{"key":"p_14","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1994.1070"},{"key":"p_15","doi-asserted-by":"publisher","DOI":"10.1109\/IPPS.1992.222970"},{"key":"p_17","first-page":"197","volume":"22","author":"Mahapatra N.R.","year":"1995","journal-title":"Pardalos, M.G. Resende, and K.G. Ramakrishnan (eds.)"},{"key":"p_18","doi-asserted-by":"publisher","DOI":"10.1109\/71.598348"},{"key":"p_21","doi-asserted-by":"publisher","DOI":"10.1109\/43.46806"},{"key":"p_23","doi-asserted-by":"publisher","DOI":"10.1145\/113379.113383"},{"key":"p_24","doi-asserted-by":"publisher","DOI":"10.1007\/BF01389000"},{"key":"p_27","first-page":"78","author":"Rich E.","year":"1983","journal-title":"McGraw Hill. New York"},{"key":"p_30","first-page":"389","volume":"89","author":"Shu W.","year":"1989","journal-title":"Proc. Supercomputing"},{"key":"p_31","first-page":"138","author":"Silberschatz A.","year":"1994","journal-title":"Massachusetts"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054100000144","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T15:33:49Z","timestamp":1565192029000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054100000144"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,6]]},"references-count":18,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2000,6]]}},"alternative-id":["10.1142\/S0129054100000144"],"URL":"https:\/\/doi.org\/10.1142\/s0129054100000144","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2000,6]]}}}