Problemet Tree Sparsity definieras enligt följande: med tanke på ett nodviktat träd av storlek n och ett heltal k, ut ett rotat underträd av storlek k med maximal vikt. Den mest kända algoritmen löser detta problem i tiden O(kn), d.v.s. kvadratisk i storleken på inmatningsträdet för k =  på (n). I detta arbete designar vi (1 + ε)-tillnärmningsalgoritmer för Tree Sparsity problem som körs i nästan linjär tid. Till skillnad från tidigare algoritmer för detta problem, våra resultat erbjuder enstaka kriterium approximationer, dvs. de ökar inte glesheten i output-lösningen, och arbetar för godtyckliga träd (inte bara balanserade träd). Vi tillhandahåller också ytterligare algoritmer för detta problem med olika körtid kontra approximation kompromisser. Slutligen visar vi att om den exakta versionen av Tree Sparsity problemet kan lösas i starkt subquadratic tid, då (min, +) convolution problem kan lösas i starkt subquadratic tid också. Det senare är ett välstuderat problem för vilket ingen starkt subkvadratisk tid algoritm är känd.
Alldeles nyligen under SODA17 konferensen visste vi att parallellt med vårt arbete, Backurs et al. I REF tillhandahölls också algoritmer för enskilda kriterier för problemet med träds gleshet.
Better Approximations for Tree Sparsity in Nearly-Linear Time
{'venue': 'SODA', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}