I online Steiner träd problem, en sekvens av punkter avslöjas en-för-en: när en punkt anländer, har vi bara tid att lägga till en enda kant ansluter denna punkt till de tidigare, och vi vill minimera den totala längden av kanter läggs till. Här har en snäv gräns varit känd i två decennier: den giriga algoritmen upprätthåller ett träd vars kostnad är O (log n) gånger Steiner trädkostnaden, och detta är bäst möjligt. Men anta, förutom den nya kanten vi lägger till, vi har tid att ändra en enda kant från den tidigare uppsättningen av kanter: kan vi göra mycket bättre? Kan vi t.ex. upprätthålla ett träd som ständigt är konkurrenskraftigt? Vi besvarar denna fråga jakande. Vi ger en primaldual algoritm som endast gör en enda swap per steg (utöver att lägga till kanten ansluter den nya punkten till de tidigare), och så att trädets kostnad är bara en konstant gånger den optimala kostnaden. Vår dubbelbaserade analys skiljer sig helt från tidigare primära analyser. I synnerhet ger vi en korrespondens mellan radier av dubbla bollar och längder av trädkanter; eftersom dubbla bollar är förknippade med punkter och därmed inte rör sig runt (i motsats till kanter), kan vi noga övervaka kantlängder baserat på dubbla radier. Att visa att dessa dubbla radier inte kan ändras alltför snabbt är det tekniska hjärtat i tidningen, och tillåter oss att ge en hård gräns för antalet swappar per ankomst, samtidigt som vi upprätthåller en konstant konkurrenskraftig träd hela tiden. Tidigare resultat för detta problem gav en algoritm som utförde ett amorterat konstant antal swappar: för varje n var antalet swappar i de första n stegen O(n). Vi ger också en enklare snäv analys för detta amorterade fall.
Ref visade då att med endast en retroaktiv kant-swap per steg, en konstant konkurrenskraftig Steiner träd kan underhållas online.
The power of deferral: maintaining a constant-competitive steiner tree online
{'venue': "STOC '13", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}