Explore cutting-edge research on approximation algorithms for Longest Common Subsequence (LCS) and Longest Increasing Subsequence (LIS) problems in this 18-minute IEEE conference talk. Delve into the latest advancements presented by researchers Aviad Rubinstein, Saeed Seddighin, Zhao Song, and Xiaorui Sun as they discuss innovative approaches to improve running times for these fundamental computational problems. Gain insights into the theoretical and practical implications of their work, which has the potential to enhance efficiency in various applications of sequence analysis and dynamic programming.
Approximation Algorithms for LCS and LIS with Truly Improved Running Times
Overview
Syllabus
Approximation Algorithms for LCS and LIS with Truly Improved Running Times
Taught by
IEEE FOCS: Foundations of Computer Science
Tags
Related Courses
-
Introduction to Graduate Algorithms
-
Dynamic Programming, Greedy Algorithms
5.0 -
Dynamic Algorithms for LIS and Distance to Monotonicity
-
Longest Common Subsequence Using Dynamic Programming - Design and Analysis of Algorithms
-
Smoothed Complexity of 2-player Nash Equilibria
-
Undergrad Complexity at CMU - Problems in P
