Vi presenterar förbättrade deterministiska distribuerade algoritmer för ett antal välstuderade matchningsproblem, som är enklare, snabbare, mer exakta och/eller mer allmänna än deras kända motsvarigheter. Den gemensamma nämnaren för dessa resultat är en deterministisk distribuerad avrundningsmetod för vissa linjära program, som är den första avrundningsmetoden, till vår kunskap. En provtagning av våra slutresultat är följande: • En O log 2 · log n -round deterministisk distribuerad algoritm för att beräkna en maximal matchning, i n-node grafer med maximal grad. Detta är den första förbättringen på cirka 20 år jämfört med den berömda O(log 4 n)-round-algoritmen för Hańćkowiak, Karoński och Panconesi [SODA'98, PODC'99]. • En deterministisk distribuerad algoritm för beräkning av en (2 + ε)-uppskattning av maximal matchning i O log 2 · log 1 ε + log * n rundor. Detta är exponentiellt snabbare än den klassiska O( + log * n)-runda 2- approximation av Panconesi och Rizzi [DIST'01]. Med vissa ändringar kan algoritmen också hitta en nästan maximal matchning som endast lämnar en ε-fraktion av kanterna på oöverträffade noder. • En O log 2 · log 1 ε · log 1+ε W + log * n -round deterministisk distribuerad algoritm för beräkning av en (2 + ε)-uppskattning av en maximal viktad matchning, och även för det mer allmänna problemet med maximal viktad b-matchning. Här betecknar W den maximala normaliserade vikten. Dessa förbättrar över O log 4 n · log 1+ε W -round (6 + ε) - approximation algoritm av Panconesi och Sozio [DIST'10].
Den nuvarande bästa deterministiska algoritmen i CONGEST-modellen (och även i LOCAL-modellen) är av Fischer REF och den beräknar en maximal matchning i O(log 2  på log n) rundor, där  till exempel den maximala graden av nätverksgrafen G. På bekostnad av ett högre beroende av  och kan beroendet av n minskas och det visades av Panconesi och Rizzi [PR01] att en maximal matchning kan beräknas i O( ska + log * n) rundor.
Improved deterministic distributed matching via rounding
{'venue': 'Distributed Computing', 'journal': 'Distributed Computing', 'mag_field_of_study': ['Computer Science', 'Engineering']}