YoVDO

Fully-Dynamic Submodular Cover with Bounded Recourse

Offered By: IEEE via YouTube

Tags

IEEE FOCS: Foundations of Computer Science Courses Algorithms Courses Theoretical Computer Science Courses Greedy Algorithms Courses

Course Description

Overview

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.

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

An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games Against Nature
IEEE via YouTube
Computation in the Brain Tutorial - Part 2
IEEE via YouTube
Computation in the Brain - Part 1
IEEE via YouTube
Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model
IEEE via YouTube
Cookbook Lower Bounds for Statistical Inference in Distributed and Constrained Settings - Part 1
IEEE via YouTube