Abstract-Vi anser att single-source (eller single-sink) buyat-bulk problem med en okänd konkava kostnadsfunktion. Vi vill leda en uppsättning krav längs en graf till eller från en utsedd rotnod, och kostnaden för routing x enheter av flödet längs en kant är proportionell mot någon konkava, icke-decreasing funktion f sådan att f (0) = 0. Vi presenterar en polynom tid algoritm som finner en fördelning över träd så att den förväntade kostnaden för ett träd för alla f är inom en O(1)-faktor för den optimala kostnaden för att f. Den tidigare bästa samtidig approximation för detta problem, även ignorera beräkningstiden, var O (logg  på D), där D är multi-uppsättningen av efterfrågenoder. Vi utformar en enkel algoritmisk ram med hjälp av ellipsoid metod som finner en O(1)-uppskattning om en finns, och sedan konstruera en separation orakel med hjälp av en ny anpassning av Guha, Meyerson, och Munagala [10] algoritm för den enda-sink buy-atbulk problem som bevisar en O(1) approximation är möjligt för alla f. Antalet träd i stödet för distributionen som konstruerats av vår algoritm är som mest 1 + log.
I en relaterad papper av REF, författarna konstruera (i polynom tid) en uppsättning överlagrade träd från en given allmän graf sådan att den förväntade kostnaden för ett träd för alla f är inom en O(1)-faktor för den optimala kostnaden för att f.
An Oblivious O(1)-Approximation for Single Source Buy-at-Bulk
{'venue': '2009 50th Annual IEEE Symposium on Foundations of Computer Science', 'journal': '2009 50th Annual IEEE Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}