Detta papper studerar en ny online problem, kallas mincost perfekt matchning med förseningar (MPMD), definieras över en ändlig metriska utrymme (dvs, en komplett graf med positiva kant vikter lyda triangeln ojämlikhet) M som är känd för algoritmen i förväg. Begäran kommer i en kontinuerlig tid online mode på punkterna M och bör serveras genom att matcha dem med varandra. Algoritmen får fördröja sin begäran matchande åtaganden, men detta kommer inte gratis: den totala kostnaden för algoritmen är summan av metriska avstånd mellan matchade förfrågningar plus summan av gånger varje begäran väntade sedan den anlände tills den matchades. En randomiserad online MPMD-algoritm presenteras vars konkurrensförhållande är O(log 2 n + log  en), där n är antalet punkter i M och  till är dess proportion. Analysen bygger på ett maskineri som utvecklats i samband med en ny stokastisk process som kan ses som två interleaded Poisson processer; överraskande, denna nya process fångar just beteendet hos vår algoritm. Ett relaterat problem där algoritmen är tillåten att rensa en oöverträffad begäran på en fast straffavgift tas också upp. Det föreslås att MPMD-problemet bara är toppen av isberget för en allmän ram av online-problem med försenad service som fångar många fler naturliga problem.
Problemet med min-kostnad perfekt matchning med förseningar presenterades i REF.
Online matching: haste makes waste!
{'venue': 'STOC 2016', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}