Vi presenterar problemet med kostnadsdistans: att hitta ett Steinerträd som optimerar summan av kantkostnader längs en meter och summan av källsänka avstånd längs ett icke-relaterat andra mätvärde. Vi ger det första kända O(log k) randomiserade approximationssystemet för kostnadsdistans, där k är antalet källor. Vi minskar flera vanliga problem med nätverksdesign till CostDistans och får (i vissa fall) den första kända logaritmiska approximationen för dem. Dessa problem inkluderar enkelsänka buy-at-bulk med varierande rörtyper mellan olika uppsättningar av noder, anläggning plats med buy-at-bulk typ kostnader på kanter (integrerad logistik), bygga en källa multicast träd med goda kostnader och fördröjningsegenskaper, prioritet Steiner träd, och flernivå anläggningsplats. Vår algoritm är också lättare att implementera och betydligt snabbare än tidigare kända algoritmer för buy-at-bulk design problem. * En preliminär version av detta verk publicerades i 41
Kombinationen av anläggningen plats och buy-at-bulk nätverk problem har övervägts för första gången i REF.
Cost-Distance: Two Metric Network Design
{'venue': 'SIAM J. Comput.', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}