Abstract-Vi studerar trafikvård i optisk nätverksdesign. Målet är att aggregera trafikströmmar med låg bandbredd för att effektivt utnyttja högbandsbreddsmedier såsom våglängdskanaler. Mer exakt, med tanke på trafikkrav som ska styras i ett nätverk, är designproblemet att definiera en samling ljusvägar så att varje efterfrågan kan följa en sekvens av på varandra följande ljusvägar. Varje ljusväg har bandbredd enhet-våglängd, och flera sub-våglängd krav kan dela en gemensam ljusväg. Trafiken måste endast gå in och avgå från en ljusväg vid dess två ändpunkter. Det mesta tidigare arbetet med grooming fokuserade på ringtopologin och behandlade vanligtvis bara enhetliga bandbreddskrav, medan vi överväger mer allmänna inställningar. Vi studerar två mål. Det ena är att minimera den totala utrustningskostnaden som krävs för att stödja ljusvägarna; det andra är helt enkelt att minimera antalet ljusvägar. Även för den extremt begränsade specialfallet av en linje topologi och trafik krav som begär halvvågslängd bandbredd, visar vi att båda målen är APX-hård att optimera, vilket innebär att vi inte kan approximera den optimala godtyckligt. På den andra ytterligheten av generalitet, för godtyckliga nättopologier och trafikkrav som begär godtyckliga mängder bandbredd, visar vi en logaritmisk approximation för kostnadsminimering och en 2- approximation för minimering ljusväg räknas. Dessutom upptäcker vi att det speciella fallet med krav på halvvågslängd har rika kombinatoriska egenskaper, nära relaterade till grafproblem som cykelpackning och mönstermatchning problem såsom utbytesavstånd i strängar. Vi visar hur man kan närma båda målen upp till små konstanta faktorer i detta fall, samtidigt som man på samma sätt förbättrar approximationen och hårdheten i utbytesavståndet problem också.
I REF infördes approximationsalgoritmer för att minimera den totala utrustningskostnaden och för att minimera antalet ljusvägar.
Approximation Algorithms for Grooming in Optical Network Design
{'venue': 'IEEE INFOCOM 2009', 'journal': 'IEEE INFOCOM 2009', 'mag_field_of_study': ['Mathematics', 'Computer Science']}