Tree Augmentation Problem (TAP) är: ges ett träd T = (V, E) och en uppsättning E av kanter (kallas länkar) på V delas till E, hitta en minsta storlek kant delmängd F  och E så att T + F är 2-kants ansluten. TAP är likvärdigt med problemet med att hitta en minsta storlek kant-cover F  på en laminar set-familj. Vi anser att begränsningen LL-TAP av TAP till fall när varje länk i E ansluter två blad av T. Det bästa approximation förhållandet för TAP är 3/2 [ 3, 4, 5] och inget bättre förhållande var känt för LL-TAP. Alla tidigare approximationsalgoritmer som uppnår ett förhållande bättre än 2 för TAP, eller ens för LL-TAP, var ganska involverade. För LL-TAP får vi följande ungefärliga proportioner: 17/12 för allmänna träd, 11/8 för träd på höjd 3, och 4/3 för träd på höjd 2. Vi ger också en mycket enkel 3/2-approximation algoritm (för allmänna träd) och bevisa att den beräknar en lösning av storlek som mest min { 3 2 t, 5 3 t * }, där t är den minsta storleken på en kant-omslag av bladen, och t * är det optimala värdet av den naturliga LP-avslappning för problemet med att täcka bladens kanter bara. Detta ger den första bevisningen för att integraiteten i en naturlig LP-relaxering för LL-TAP är mindre än 2.
REF gav ett förhållande på 17/12 för specialfallet TAP när varje länk ansluter 2 blad och erhöll ett förhållande på 3/2 för denna version w.r.t.
Covering a laminar family by leaf to leaf links
{'venue': None, 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}