Abstrakt. Gupta m.fl. [J. ACM, 54 (2007), artikel 11] och Gupta, Kumar och Roughgarden [i ACM:s symposium om teori om datorsystem, ACM, New York, 2003, s. 365-372] har nyligen utvecklat ett elegant ramverk för utveckling av randomiserade approximationsalgoritmer för hyres- eller köpnätsdesignproblem. Den viktigaste byggstenen i denna ram är en approximationsalgoritm för det underliggande nätdesignproblemet som medger ett strikt kostnadsdelningssystem. Sådana kostnadsdelningssystem har också visat sig vara användbara i utvecklingen av approximativa algoritmer i samband med tvåstegs stokastisk optimering med användning. Det viktigaste bidraget i detta dokument är att visa att problemet med Steinerskogen medger kostnadsandelar som är 3-strikt och 4-grupps-strikt. Som en följd härleder vi förvånansvärt enkla approximationsalgoritmer för hyra-eller-buy-multicast-hyra-eller-buy-problem med approximationsgraderna 5 och 6, vilket förbättrar de tidigare bästa approximationsgraderna på 6,828 respektive 12,8. Vi visar också att inget approximationsförhållande bättre än 4.67 kan uppnås med hjälp av sampleand-augment ram i kombination med de för närvarande mest kända Steiner skog approximation algoritmer. I samband med tvåstegs stokastisk optimering leder vårt resultat till en 6-approximationsalgoritm för det stokastiska Steiner-trädproblemet i den svarta boxmodellen och en 5-approximationsalgoritm för det stokastiska Steiner-skogsproblemet i den självständiga beslutsmodellen. 1. Vad är det för fel på dig? Inledning. I multicommodity hyra-eller-buy (MRoB) problem vi ges en oriktad graf G = (V, E) med icke-negativa kostnader c e för alla kanter e E, en uppsättning k terminalpar R = { (s 1, t 1 ),. ., (s k, t k )} V × V, en positiv efterfrågan d i för varje terminal par (s i, t i ) R och en parameter M ≥ 1. Målet är att installera kapaciteter på kanterna av G så att för alla (s i, t i ) R kan vi samtidigt rutt d i enheter av flödet från s i till t i. Vi kan antingen hyra kapacitet på en kant e på kostnad λ(e) · c(e), där λ(e) är flödet traversing edge e, eller köpa oändlig kapacitet på kant e på kostnad M · c(e). Köpta kanter har ingen inkrementell, flödesberoende kostnad. Det övergripande målet är att hitta en genomförbar lösning på minsta totala kostnad. MRoB-problemet generaliserar ett antal grundläggande optimeringsproblem som är NP-hårda. För M = 1 och enhetskrav minskar MRoB-problemet till
• Flera varor hyra-eller-köp REF.
STRICT COST SHARING SCHEMES FOR STEINER FOREST
{'venue': 'SIAM J. Comput.', 'journal': 'SIAM J. Comput.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}