YoVDO

On LP-Relaxations for the Tree Augmentation Problem

Offered By: Hausdorff Center for Mathematics via YouTube

Tags

Graph Theory Courses STEM Courses Combinatorial Optimization Courses Traveling Salesman Problem Courses

Course Description

Overview

Explore a lecture on LP-relaxations for the tree augmentation problem, delivered by Zeev Nutov at the Hausdorff Center for Mathematics. Delve into the intricacies of the Tree Augmentation Problem, its equivalent formulations, and the significance of studying it. Examine the Cut-LP and dual-fitting algorithms, and understand the concept of shadow-minimal solutions along with their properties. Investigate twin-links, stems, and blocking trees, and learn about an LP and its dual, including initial assignment of duals. The lecture, part of the Hausdorff Trimester Program on Combinatorial Optimization, also covers additional possible constraints and presents an algorithm for solving the problem. Gain insights into this complex topic through a comprehensive 33-minute presentation that combines theoretical concepts with practical applications in the field of combinatorial optimization.

Syllabus

The Tree Augmentation Problem
Equivalent Formulation 2
Why is it interesting?
The Cut-LP
Dual-fitting algorithms
Shadow-minimal solutions
Properties of shadow minimal solutions
Twin-links and stems
Blocking trees
An LP and its dual
Initial assignment of duals
The algorithm
Additional possible constraints


Taught by

Hausdorff Center for Mathematics

Related Courses

Learning Creative Learning
Massachusetts Institute of Technology via Independent
Tinkering Fundamentals: A Constructionist Approach to STEM Learning
Exploratorium via Coursera
Re-Engineering Your Science Curriculum
Exploratorium via Coursera
Teaching Computing: Part 1
University of East Anglia via FutureLearn
Assessment and Teaching of 21st Century Skills
University of Melbourne via Coursera