Explore a 26-minute IEEE conference talk on fully-dynamic submodular cover with bounded recourse. Delve into the research presented by Anupam Gupta and Roie Levin from Carnegie Mellon University, based on their paper available on arXiv. Learn about the core features of submodularity, the dynamic model, and the main theorem. Understand the greedy algorithm, swap and jump operations, competitive ratio, and potential function used in the proof. Gain insights into this complex topic through an example problem and a comprehensive outline of the research findings.
Overview
Syllabus
Introduction
Example Problem
Core Features
Submodularity
The Problem
Outline
Dynamic Model
Results
Main Theorem
Greedy Algorithm
Swap and Jump
Competitive Ratio
Potential Function
Proof
Summary
Taught by
IEEE FOCS: Foundations of Computer Science
Tags
Related Courses
-
Edge-Weighted Online Bipartite Matching
-
Sublinear Algorithms for Gap Edit Distance
-
Testing Positive Semi-Definiteness via Random Submatrices
-
Network Coding Gaps for Completion Times of Multiple Unicasts
-
Analysis of Two-variable Recurrence Relations with Application to Parameterized Approximations
-
Dichotomy for Graph Homomorphisms with Complex Values on Bounded Degree Graphs
