Abstrakt. Vi föreslår en allmän metod för att konvertera online-algoritmer till lokala beräkningsalgoritmer, 3 genom att välja en slumpmässig permutation av indata, och simulera kör online-algoritm. Vi band antalet steg av algoritmen med hjälp av ett frågeträd, som modellerar beroenden mellan frågor. Vi förbättrar tidigare analyser av frågeträd på grafer av avgränsad grad, och utvidga analysen till de fall där graderna distribueras binomialt, och till ett specialfall av bipartit grafer. Med denna metod ger vi en lokal beräkningsalgoritm för maximal matchning i grafer av avgränsad grad, som körs i tid och rum O(log 3 n). Vi visar också hur man konverterar en stor familj av lastbalanseringsalgoritmer (relaterade till bollar och bins problem) till lokala beräkningsalgoritmer. Detta ger flera lokala lastbalanseringsalgoritmer som uppnår samma approximationsförhållande som online-algoritmerna, men som körs i O(log n) tid och utrymme. Slutligen ändrar vi befintliga lokala beräkningsalgoritmer för hypergraf 2-färgning och k-CNF och använder vår förbättrade analys för att få bättre tid och utrymme gränser, av O(log 4 n), ta bort beroendet av maximal grad av grafen från exponenten.
Algoritmernas komplexitet i REF beror på storleken på C mon (v).
Converting online algorithms to local computation algorithms
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}