# Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | 2019 | future lectures)

On 14.08.2014 at 10:40 in S6, there is the following noon lecture:

# Two very efficient approximation algorithms for the longest increasing subsequence

## Michael Saks

## Rutgers

## Abstract

The longest increasing subsequence (LIS) of a finite sequence has been the subject of much study within combinatorics and probability. As a computational problem it is a classic example of a problem efficiently solved by dynamic programming. Simple algorithms are known that run in time O(n log(n)) where n is the length of the array.

In recent years, many algorithmic problems have been revisited under the assumption that the input is so large that one can only afford restricted access to it, and one is willing to settle for an approximation to the solution. In this talk, I'll discuss joint work with C. Seshadhri, in which we study the LIS problem from this perspective in two distinct models of computation.

In the standard computational model we obtain an approximation algorithm that runs in time polylogarithmic in the input size. For any chosen constant c > 0, the

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | 2019 | future lectures)

Webmaster: kamweb.mff.cuni.cz Modified: 25. 02. 2019