Online (uniform) buy-at-bulk nätverk design problem ber oss att utforma ett nätverk, där kant-kostnader uppvisar skalekonomi. Tidigare metoder för detta problem använde trädbäddar, vilket ger oss randomiserade algoritmer. Dessutom kräver de optimala resultaten med ett logaritmiskt konkurrensförhållande det mått på vilket nätet byggs för att vara känt i förväg; konkurrensförhållandena beror sedan på storleken på detta mått (som kan vara mycket större än antalet terminaler som anländer). Vi anser att buy-at-bulk problemet i den minst restriktiva modellen där metriska är inte känd i förväg, men avslöjas i delar tillsammans med de efterfrågepunkter som söker anslutning anländer online. För den enda diskbänk buy-at-bulk problem, ger vi en deterministisk online algoritm med konkurrensförhållande som är logaritmisk i k, antalet terminaler som har anlänt, matchar den nedre gränsen känd även för online Steiner träd problem. I det glömska fallet när buy-at-bulk-funktionen som används för att beräkna nätets kantkostnader inte är känd i förväg (men är densamma över alla kanter), ger vi en deterministisk algoritm med konkurrensförhållande polylogaritmisk i k, antalet terminaler. I hjärtat av våra algoritmer finns optimala konstruktioner för online Light Ungefärliga Shortest-path Trees (LAST) och skiftnycklar, och deras varianter. Vi ger konstruktioner som har optimala kompromisser i form av kostnad och stretch. Vi definierar och ger också konstruktioner för en ny uppfattning om LAST där uppsättningen rötter (utöver punkterna) expanderar över tiden. Vi förväntar oss att dessa tekniker kommer att hitta applikationer i andra online nätverk-design problem.
För buy-at-bulk problemet, är det enda tidigare arbetet på ensjunk fall: REF gav en deterministisk O(log k)-konkurrenskraftig algoritm och även observerade att det är möjligt att använda online träd inbäddningar och få en randomiserad O(log 2 k)-konkurrenskraftig algoritm.
LAST but not Least: Online Spanners for Buy-at-Bulk
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}