Att hitta längden på den längsta ökande subsekvensen (LIS) är ett klassiskt algoritmiskt problem. Låt n betecknar storleken på arrayen. Enkel O(n log n) tid algoritmer är kända som bestämmer LIS exakt. I detta dokument utvecklar vi en randomiserad approximationsalgoritm, som för varje konstant δ > 0, körs i tiden polylogaritmisk i n och uppskattar längden på LIS av en matris upp till ett additivt fel av δn. Den algoritm som presenteras i denna förlängda abstrakt körs i tid (log n) O(1/δ). I det fullständiga dokumentet kommer vi att ge en förbättrad version av algoritmen med körtid (log n) c (1/δ) O(1/δ) där exponenten c är oberoende av δ. Tidigare, de mest kända polylogaritmiska tid algoritmer kunde bara uppnå en additiv n/2-uppskattning. Våra tekniker ger också en snabb algoritm för att uppskatta avståndet till monotonitet till inom en liten multiplikativ faktor. Avståndet mellan f till monotonitet, ε f, är lika med 1 −  till L/n (den bråkdels längd av LIS-komplementet). För alla δ > 0, ger vi en algoritm med körtid O((ε −1 f log n) O(1/δ) ) som ger en (1 + δ)-multiplikativ approximation till ε f. Detta kan förbättras så att exponenten är en fast konstant. De tidigare kända polylogaritmiska algoritmerna gav bara en 2- approximation.
I synnerhet Saks och Seshadhri gav i REF en randomiserad algoritm som, på ingång f : [n] → R, gör poly (log n, 1/δ) frågor och utgångar m approximerar upp till additivt fel δn längden av den längsta ökande subsekvensen av f.
Estimating the Longest Increasing Sequence in Polylogarithmic Time
{'venue': '2010 IEEE 51st Annual Symposium on Foundations of Computer Science', 'journal': '2010 IEEE 51st Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Computer Science', 'Mathematics']}