NDLI: Estimating the Longest Increasing Sequence in Polylogarithmic Time

Content Provider	IEEE Xplore Digital Library
Author	Saks, M. Seshadhri, C.
Copyright Year	2010
Abstract	Finding the length of the longest increasing subsequence (LIS) is a classic algorithmic problem. Let $n$ denote the size of the array. Simple O(n log n) time algorithms are known that determine the LIS exactly. In this paper, we develop a randomized approximation algorithm, that for any constant delta > 0, runs in time polylogarithmic in n and estimates the length of the LIS of an array up to an additive error of (delta n). The algorithm presented in this extended abstract runs in time (log n)^{O(1/delta)}. In the full paper, we will give an improved version of the algorithm with running time (log n)^c (1/delta)^{O(1/delta)} where the exponent c is independent of delta. Previously, the best known polylogarithmic time algorithms could only achieve an additive n/2-approximation. Our techniques also yield a fast algorithm for estimating the distance to monotonicity to within a small multiplicative factor. The distance of f to monotonicity, eps_f, is equal to 1 - \|LIS\|/n (the fractional length of the complement of the LIS). For any delta > 0, we give an algorithm with running time O((eps^{-1}_f log n)^{O(1/delta)}) that outputs a (1+delta)-multiplicative approximation to eps_f. This can be improved so that the exponent is a fixed constant. The previously known polylogarithmic algorithms gave only a 2-approximation.
Starting Page	458
Ending Page	467
File Size	411977
Page Count	10
File Format	PDF
ISBN	9781424485253
ISSN	02725428
DOI	10.1109/FOCS.2010.51
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2010-10-23
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Approximation algorithms Approximation methods Indexes Additives Heuristic algorithms Arrays Protocols Dynamic Programming Sublinear algorithms Monotonicity Longest Increasing Subsequence
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in