LOWER BOUNDS ON STREAMING ALGORITHMS FOR APPROXIMATING THE LENGTH OF THE LONGEST INCREASING SUBSEQUENCE

We show that any deterministic streaming algorithm that makes a constant number of passes over the input and gives a constant factor approximation of the length of the longest increasing subsequence in a sequence of length n must use space ... This proves a conjecture made by Gopalan et al. [Proceed...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on computing 2010-01, Vol.39 (7-8), p.3463-3479
Main Authors: GAL, Anna, GOPALAN, Parikshit
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Algorithms
Applied sciences
Approximation
Asymptotic properties
Codes
Computation
Computer science
control theory
systems
Exact sciences and technology
Lower bounds
Mathematical analysis
Miscellaneous
Studies
Symbols
Theoretical computing
Upper bounds
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c420t-844a60cd9108ab95f6b59203343afcd376b541ce4fd8fdb7770cab94855232083
cites cdi_FETCH-LOGICAL-c420t-844a60cd9108ab95f6b59203343afcd376b541ce4fd8fdb7770cab94855232083
container_end_page 3479
container_issue 7-8
container_start_page 3463
container_title SIAM journal on computing
container_volume 39
creator GAL, Anna
GOPALAN, Parikshit
description We show that any deterministic streaming algorithm that makes a constant number of passes over the input and gives a constant factor approximation of the length of the longest increasing subsequence in a sequence of length n must use space ... This proves a conjecture made by Gopalan et al. [Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, 2007, pp. 318-327] who proved a matching upper bound. Our results yield asymptotically tight lower bounds for all approximation factors, thus resolving the main open problem from their paper. Our proof is based on analyzing a related communication problem and proving a direct sum type property for it.(ProQuest: ... denotes formulae/symbols omitted.) [PUBLICATION ABSTRACT]
doi_str_mv 10.1137/090770801
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_miscellaneous_1671380279</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2412701951</sourcerecordid><originalsourceid>FETCH-LOGICAL-c420t-844a60cd9108ab95f6b59203343afcd376b541ce4fd8fdb7770cab94855232083</originalsourceid><addsrcrecordid>eNpdkM1OwzAQhC0EEqVw4A0sJCQ4BNaxU8fHUNw0UhqXJBXcItdNUKv-EbcH3h5XrXrgtBrtt6PZQeiewAshlL-CAM4hBHKBOgRE4HFCyCXqAAjuBVTwa3Rj7QKAMEZoB32n6lPm-E1NsvcCqwwXZS6jUZLFOEpjlSflcFTggcpxNB7n6isZReVhWQ4lTmUWl0OsBkelslgWJU6yvnMoDlAxeSvkx0RmfXmLrhq9tPXdaXbRZCDL_tBLVZz0o9QzzIedFzKme2BmgkCopyJoetNA-EApo7oxM8qdZsTUrJmFzWzK3a_GcSwMAp_6ENIuejr6btvNz762u2o1t6ZeLvW63uxtRXqc0BB8Lhz68A9dbPbt2qWrQkcA9ARz0PMRMu3G2rZuqm07X-n2tyJQHRqvzo079vFkqK3Ry6bVazO35wOfupyMAv0DFS90yA</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>880200694</pqid></control><display><type>article</type><title>LOWER BOUNDS ON STREAMING ALGORITHMS FOR APPROXIMATING THE LENGTH OF THE LONGEST INCREASING SUBSEQUENCE</title><source>EBSCOhost Business Source Ultimate</source><source>ABI/INFORM Global</source><source>LOCUS - SIAM's Online Journal Archive</source><creator>GAL, Anna ; GOPALAN, Parikshit</creator><creatorcontrib>GAL, Anna ; GOPALAN, Parikshit</creatorcontrib><description>We show that any deterministic streaming algorithm that makes a constant number of passes over the input and gives a constant factor approximation of the length of the longest increasing subsequence in a sequence of length n must use space ... This proves a conjecture made by Gopalan et al. [Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, 2007, pp. 318-327] who proved a matching upper bound. Our results yield asymptotically tight lower bounds for all approximation factors, thus resolving the main open problem from their paper. Our proof is based on analyzing a related communication problem and proving a direct sum type property for it.(ProQuest: ... denotes formulae/symbols omitted.) [PUBLICATION ABSTRACT]</description><identifier>ISSN: 0097-5397</identifier><identifier>EISSN: 1095-7111</identifier><identifier>DOI: 10.1137/090770801</identifier><language>eng</language><publisher>Philadelphia, PA: Society for Industrial and Applied Mathematics</publisher><subject>Algorithmics. Computability. Computer arithmetics ; Algorithms ; Applied sciences ; Approximation ; Asymptotic properties ; Codes ; Computation ; Computer science; control theory; systems ; Exact sciences and technology ; Lower bounds ; Mathematical analysis ; Miscellaneous ; Studies ; Symbols ; Theoretical computing ; Upper bounds</subject><ispartof>SIAM journal on computing, 2010-01, Vol.39 (7-8), p.3463-3479</ispartof><rights>2015 INIST-CNRS</rights><rights>Copyright Society for Industrial and Applied Mathematics 2010</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c420t-844a60cd9108ab95f6b59203343afcd376b541ce4fd8fdb7770cab94855232083</citedby><cites>FETCH-LOGICAL-c420t-844a60cd9108ab95f6b59203343afcd376b541ce4fd8fdb7770cab94855232083</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://www.proquest.com/docview/880200694?pq-origsite=primo$$EHTML$$P50$$Gproquest$$H</linktohtml><link.rule.ids>314,780,784,3185,11688,27924,27925,36060,36061,44363</link.rule.ids><backlink>$$Uhttp://pascal-francis.inist.fr/vibad/index.php?action=getRecordDetail&amp;idt=23948430$$DView record in Pascal Francis$$Hfree_for_read</backlink></links><search><creatorcontrib>GAL, Anna</creatorcontrib><creatorcontrib>GOPALAN, Parikshit</creatorcontrib><title>LOWER BOUNDS ON STREAMING ALGORITHMS FOR APPROXIMATING THE LENGTH OF THE LONGEST INCREASING SUBSEQUENCE</title><title>SIAM journal on computing</title><description>We show that any deterministic streaming algorithm that makes a constant number of passes over the input and gives a constant factor approximation of the length of the longest increasing subsequence in a sequence of length n must use space ... This proves a conjecture made by Gopalan et al. [Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, 2007, pp. 318-327] who proved a matching upper bound. Our results yield asymptotically tight lower bounds for all approximation factors, thus resolving the main open problem from their paper. Our proof is based on analyzing a related communication problem and proving a direct sum type property for it.(ProQuest: ... denotes formulae/symbols omitted.) [PUBLICATION ABSTRACT]</description><subject>Algorithmics. Computability. Computer arithmetics</subject><subject>Algorithms</subject><subject>Applied sciences</subject><subject>Approximation</subject><subject>Asymptotic properties</subject><subject>Codes</subject><subject>Computation</subject><subject>Computer science; control theory; systems</subject><subject>Exact sciences and technology</subject><subject>Lower bounds</subject><subject>Mathematical analysis</subject><subject>Miscellaneous</subject><subject>Studies</subject><subject>Symbols</subject><subject>Theoretical computing</subject><subject>Upper bounds</subject><issn>0097-5397</issn><issn>1095-7111</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2010</creationdate><recordtype>article</recordtype><sourceid>M0C</sourceid><recordid>eNpdkM1OwzAQhC0EEqVw4A0sJCQ4BNaxU8fHUNw0UhqXJBXcItdNUKv-EbcH3h5XrXrgtBrtt6PZQeiewAshlL-CAM4hBHKBOgRE4HFCyCXqAAjuBVTwa3Rj7QKAMEZoB32n6lPm-E1NsvcCqwwXZS6jUZLFOEpjlSflcFTggcpxNB7n6isZReVhWQ4lTmUWl0OsBkelslgWJU6yvnMoDlAxeSvkx0RmfXmLrhq9tPXdaXbRZCDL_tBLVZz0o9QzzIedFzKme2BmgkCopyJoetNA-EApo7oxM8qdZsTUrJmFzWzK3a_GcSwMAp_6ENIuejr6btvNz762u2o1t6ZeLvW63uxtRXqc0BB8Lhz68A9dbPbt2qWrQkcA9ARz0PMRMu3G2rZuqm07X-n2tyJQHRqvzo079vFkqK3Ry6bVazO35wOfupyMAv0DFS90yA</recordid><startdate>20100101</startdate><enddate>20100101</enddate><creator>GAL, Anna</creator><creator>GOPALAN, Parikshit</creator><general>Society for Industrial and Applied Mathematics</general><scope>IQODW</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>3V.</scope><scope>7RQ</scope><scope>7WY</scope><scope>7WZ</scope><scope>7X2</scope><scope>7XB</scope><scope>87Z</scope><scope>88A</scope><scope>88F</scope><scope>88I</scope><scope>88K</scope><scope>8AL</scope><scope>8FE</scope><scope>8FG</scope><scope>8FH</scope><scope>8FK</scope><scope>8FL</scope><scope>8G5</scope><scope>ABJCF</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>ARAPS</scope><scope>ATCPS</scope><scope>AZQEC</scope><scope>BBNVY</scope><scope>BENPR</scope><scope>BEZIV</scope><scope>BGLVJ</scope><scope>BHPHI</scope><scope>CCPQU</scope><scope>D1I</scope><scope>DWQXO</scope><scope>FRNLG</scope><scope>F~G</scope><scope>GNUQQ</scope><scope>GUQSH</scope><scope>HCIFZ</scope><scope>JQ2</scope><scope>K60</scope><scope>K6~</scope><scope>K7-</scope><scope>KB.</scope><scope>L.-</scope><scope>L6V</scope><scope>LK8</scope><scope>M0C</scope><scope>M0K</scope><scope>M0N</scope><scope>M1Q</scope><scope>M2O</scope><scope>M2P</scope><scope>M2T</scope><scope>M7P</scope><scope>M7S</scope><scope>MBDVC</scope><scope>P5Z</scope><scope>P62</scope><scope>PATMY</scope><scope>PDBOC</scope><scope>PQBIZ</scope><scope>PQBZA</scope><scope>PQEST</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>PRINS</scope><scope>PTHSS</scope><scope>PYCSY</scope><scope>Q9U</scope><scope>S0W</scope><scope>U9A</scope><scope>7SC</scope><scope>8FD</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope></search><sort><creationdate>20100101</creationdate><title>LOWER BOUNDS ON STREAMING ALGORITHMS FOR APPROXIMATING THE LENGTH OF THE LONGEST INCREASING SUBSEQUENCE</title><author>GAL, Anna ; GOPALAN, Parikshit</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c420t-844a60cd9108ab95f6b59203343afcd376b541ce4fd8fdb7770cab94855232083</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2010</creationdate><topic>Algorithmics. Computability. Computer arithmetics</topic><topic>Algorithms</topic><topic>Applied sciences</topic><topic>Approximation</topic><topic>Asymptotic properties</topic><topic>Codes</topic><topic>Computation</topic><topic>Computer science; control theory; systems</topic><topic>Exact sciences and technology</topic><topic>Lower bounds</topic><topic>Mathematical analysis</topic><topic>Miscellaneous</topic><topic>Studies</topic><topic>Symbols</topic><topic>Theoretical computing</topic><topic>Upper bounds</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>GAL, Anna</creatorcontrib><creatorcontrib>GOPALAN, Parikshit</creatorcontrib><collection>Pascal-Francis</collection><collection>CrossRef</collection><collection>ProQuest Central (Corporate)</collection><collection>Career &amp; Technical Education Database</collection><collection>ABI/INFORM Collection</collection><collection>ABI/INFORM Global (PDF only)</collection><collection>Agricultural Science Collection</collection><collection>ProQuest Central (purchase pre-March 2016)</collection><collection>ABI/INFORM Global (Alumni Edition)</collection><collection>Biology Database (Alumni Edition)</collection><collection>Military Database (Alumni Edition)</collection><collection>Science Database (Alumni Edition)</collection><collection>Telecommunications (Alumni Edition)</collection><collection>Computing Database (Alumni Edition)</collection><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>ProQuest Natural Science Collection</collection><collection>ProQuest Central (Alumni) (purchase pre-March 2016)</collection><collection>ABI/INFORM Collection (Alumni Edition)</collection><collection>Research Library (Alumni Edition)</collection><collection>Materials Science &amp; Engineering Collection</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central</collection><collection>Advanced Technologies &amp; Aerospace Collection</collection><collection>Agricultural &amp; Environmental Science Collection</collection><collection>ProQuest Central Essentials</collection><collection>Biological Science Collection</collection><collection>ProQuest Central</collection><collection>Business Premium Collection</collection><collection>Technology Collection</collection><collection>Natural Science Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Materials Science Collection</collection><collection>ProQuest Central</collection><collection>Business Premium Collection (Alumni)</collection><collection>ABI/INFORM Global (Corporate)</collection><collection>ProQuest Central Student</collection><collection>Research Library Prep</collection><collection>SciTech Premium Collection</collection><collection>ProQuest Computer Science Collection</collection><collection>ProQuest Business Collection (Alumni Edition)</collection><collection>ProQuest Business Collection</collection><collection>Computer Science Database</collection><collection>Materials Science Database</collection><collection>ABI/INFORM Professional Advanced</collection><collection>ProQuest Engineering Collection</collection><collection>ProQuest Biological Science Collection</collection><collection>ABI/INFORM Global</collection><collection>Agricultural Science Database</collection><collection>Computing Database</collection><collection>Military Database</collection><collection>Research Library</collection><collection>Science Database</collection><collection>Telecommunications Database</collection><collection>ProQuest Biological Science Journals</collection><collection>Engineering Database</collection><collection>Research Library (Corporate)</collection><collection>Advanced Technologies &amp; Aerospace Database</collection><collection>ProQuest Advanced Technologies &amp; Aerospace Collection</collection><collection>Environmental Science Database</collection><collection>Materials Science Collection</collection><collection>ProQuest One Business</collection><collection>ProQuest One Business (Alumni)</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>ProQuest Central China</collection><collection>Engineering Collection</collection><collection>Environmental Science Collection</collection><collection>ProQuest Central Basic</collection><collection>DELNET Engineering &amp; Technology Collection</collection><collection>Computer and Information Systems Abstracts</collection><collection>Technology Research Database</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>SIAM journal on computing</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>GAL, Anna</au><au>GOPALAN, Parikshit</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>LOWER BOUNDS ON STREAMING ALGORITHMS FOR APPROXIMATING THE LENGTH OF THE LONGEST INCREASING SUBSEQUENCE</atitle><jtitle>SIAM journal on computing</jtitle><date>2010-01-01</date><risdate>2010</risdate><volume>39</volume><issue>7-8</issue><spage>3463</spage><epage>3479</epage><pages>3463-3479</pages><issn>0097-5397</issn><eissn>1095-7111</eissn><abstract>We show that any deterministic streaming algorithm that makes a constant number of passes over the input and gives a constant factor approximation of the length of the longest increasing subsequence in a sequence of length n must use space ... This proves a conjecture made by Gopalan et al. [Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, 2007, pp. 318-327] who proved a matching upper bound. Our results yield asymptotically tight lower bounds for all approximation factors, thus resolving the main open problem from their paper. Our proof is based on analyzing a related communication problem and proving a direct sum type property for it.(ProQuest: ... denotes formulae/symbols omitted.) [PUBLICATION ABSTRACT]</abstract><cop>Philadelphia, PA</cop><pub>Society for Industrial and Applied Mathematics</pub><doi>10.1137/090770801</doi><tpages>17</tpages><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 0097-5397
ispartof SIAM journal on computing, 2010-01, Vol.39 (7-8), p.3463-3479
issn 0097-5397
1095-7111
language eng
recordid cdi_proquest_miscellaneous_1671380279
source EBSCOhost Business Source Ultimate; ABI/INFORM Global; LOCUS - SIAM's Online Journal Archive
subjects Algorithmics. Computability. Computer arithmetics
Algorithms
Applied sciences
Approximation
Asymptotic properties
Codes
Computation
Computer science
control theory
systems
Exact sciences and technology
Lower bounds
Mathematical analysis
Miscellaneous
Studies
Symbols
Theoretical computing
Upper bounds
title LOWER BOUNDS ON STREAMING ALGORITHMS FOR APPROXIMATING THE LENGTH OF THE LONGEST INCREASING SUBSEQUENCE
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-28T17%3A44%3A55IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=LOWER%20BOUNDS%20ON%20STREAMING%20ALGORITHMS%20FOR%20APPROXIMATING%20THE%20LENGTH%20OF%20THE%20LONGEST%20INCREASING%20SUBSEQUENCE&rft.jtitle=SIAM%20journal%20on%20computing&rft.au=GAL,%20Anna&rft.date=2010-01-01&rft.volume=39&rft.issue=7-8&rft.spage=3463&rft.epage=3479&rft.pages=3463-3479&rft.issn=0097-5397&rft.eissn=1095-7111&rft_id=info:doi/10.1137/090770801&rft_dat=%3Cproquest_cross%3E2412701951%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c420t-844a60cd9108ab95f6b59203343afcd376b541ce4fd8fdb7770cab94855232083%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=880200694&rft_id=info:pmid/&rfr_iscdi=true