I den k-arc anslutna subgraph problem, vi ges en riktad graf G och ett heltal k och målet är att hitta en subgraph av minsta kostnad så att det finns minst k-arc åtskilda vägar mellan varje par hörn. Vi ger en enkel (1 + 1/k) - approximation till den oviktade varianten av problemet, där alla bågar av G har samma kostnad. Detta förbättrar på 1 + 2 / k approximationen av Gabow et al. [GGTW09]............................................................. Liknar den 2- approximation algoritmen för detta problem [FJ81], tar vår algoritm helt enkelt föreningen av en k in-arborescence och en k ut-arborescence. Den största skillnaden är i valet av de två argorescenserna. Här, inspirerat av de senaste tillämpningarna av avrundning genom provtagningsmetod (se t.ex. [AGM + 10, MOS11, OSS11, AKS12]), väljer vi arborescences slumpmässigt genom att ta prover från en distribution på föreningar av k arborescences som definieras utifrån en extrem punktlösning av den linjära programmeringen av problemet. I analysen använder vi avgörande den gleshet egenskapen hos den extrema punktlösningen för att överbringa storleken på föreningen av de provade argorescenserna. För att komplettera algoritmen visar vi också att integrality gapet i den minsta kostnad starkt ansluten subgraf problem (dvs. när k = 1) är minst 3/2 −, för alla > 0. Vår integrality gap instans är inspirerad av integratet gap exempel på asymmetriska resande säljare problem [CGK06], vilket ger ytterligare bevis på samband mellan approximabiliteten av de två problemen.
För den minsta k-edge-anslutna spännvidden (kECSS), Laehanukit et al. REF gav en randomiserad (1 + 1/k) approximationsalgoritm.
A Rounding by Sampling Approach to the Minimum Size k-Arc Connected Subgraph Problem
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}