![Algorithms Lab](/img/default-banner.jpg)
- 118
- 296 635
Algorithms Lab
Germany
Приєднався 12 лис 2012
Welcome to my youtube channel! Here I post my video lectures and sometimes videos about my research.
Kevin Buchin
Kevin Buchin
Applications of LP Duality: Matchings, Flows and Shortest Path
In this video we put duality to use. Specifically, we will
1.) prove Hall's theorem, which characterizes when a bipartite graph has a perfect matching based on the duality of max-matching and min-vertex-cover in bipartite graphs (König's theorem)
2.) see two LP formulations of the Max-Flow, which lead to different formulations of Min-Cut (and proving through LP duality the Max-Flow Min-Cut theorem)
3.) Dualize the flow-based formulation of the shortest path problem
One tool used in these applications and discussed in the video are totally unimodular matrices.
00:00 Matchings
03:12 Hall's theorem
04:44 König's theorem
05:47 proof of Hall's theorem
10:00 totally unimodular matrices
12:46 LPs with totally unimodular matrix A
17:24 incidence matrices of bipartite graphs
21:01 König's theorem
26:27 Deriving the Max-Flow LP
30:20 The Max-Flow LP
31:44 Discussion of Max-Flow LP
34:08 Dualizing the Max-Flow LP
35:40 The Dual LP
37:46 Compacter formulation of Dual LP
38.51 Why the Dual LP describes Min-Cut
40:21 Alternative Max-Flow LP (s-t-paths)
42:09 Dual of alternative LP
43:39 Shortest-Path LP
45:34 Dualizing the Shortest-Path LP
1.) prove Hall's theorem, which characterizes when a bipartite graph has a perfect matching based on the duality of max-matching and min-vertex-cover in bipartite graphs (König's theorem)
2.) see two LP formulations of the Max-Flow, which lead to different formulations of Min-Cut (and proving through LP duality the Max-Flow Min-Cut theorem)
3.) Dualize the flow-based formulation of the shortest path problem
One tool used in these applications and discussed in the video are totally unimodular matrices.
00:00 Matchings
03:12 Hall's theorem
04:44 König's theorem
05:47 proof of Hall's theorem
10:00 totally unimodular matrices
12:46 LPs with totally unimodular matrix A
17:24 incidence matrices of bipartite graphs
21:01 König's theorem
26:27 Deriving the Max-Flow LP
30:20 The Max-Flow LP
31:44 Discussion of Max-Flow LP
34:08 Dualizing the Max-Flow LP
35:40 The Dual LP
37:46 Compacter formulation of Dual LP
38.51 Why the Dual LP describes Min-Cut
40:21 Alternative Max-Flow LP (s-t-paths)
42:09 Dual of alternative LP
43:39 Shortest-Path LP
45:34 Dualizing the Shortest-Path LP
Переглядів: 317
Відео
Steiner Forest via Primal-Dual
Переглядів 8667 місяців тому
In this video, we look at the 2-approximation for the Minimum Steiner Forest Problem using the primal-dual scheme with synchronized increases. In a previous video, I should you how to use the primal-dual scheme for set cover problem. But this is not just yet another application, but what is new here are the "synchronized increases", i.e., we are increasing several dual variables at the same tim...
MaxSat by LP Rounding
Переглядів 4267 місяців тому
We take a look at 2 randomized algorithms for Maximum Satisfiability (MaxSat): First simply randomly setting the variables, and then solving the relaxed LP for MaxSat and setting the variables by "randomized rounding". We analyze both algorithms, and show that the combination of both gives us a 0.75-approximation. Further, we get to know conditional expectations as technique for derandomizing r...
LP-based Approximation Algorithms for Set Cover: LP Rounding, Primal-Dual and Dual fitting
Переглядів 8508 місяців тому
An introduction to approximation algorithms based on linear programming (LP) by the example of the set cover problem. The techniques that we cover are: - LP Rounding - Primal-Dual - Dual fitting (for the analysis of the greedy set cover algorithm) 00:00 Lower bounds from Linear Programming 04:17 Set Cover ILP 07:59 LP Rounding 09:50 Set Cover: Optimum vs Optimum of relaxed LP 11:13 First Attemp...
Linear Programming (LP) Duality, part 1: Introduction and Physical Interpretation
Переглядів 2518 місяців тому
I introduce duality by an example, we take a look at weak and strong duality, go through a recipe for duality and conclude with a physical interpretation of duality: 00:00 Introduction to LP Duality 08:05 Weak Duality Theorem 10:53 Feasibility vs Optimality 15:15 Duality recipe 19:57 Physical Interpretation of LP Duality
Linear Programming (LP) Duality, part 2: Farkas Lemma
Переглядів 3418 місяців тому
Farkas Lemma is the key tool for proving the Strong Duality Theorem. In this video, I provide a geometric interpretation of Farkas Lemma and show how to use it to prove the Strong Duality Theorem. 00:00 Farkas Lemma 05:02 Variant of Farkas Lemma 10:16 Strong Duality Theorem, proof 13:53 proof, part 2
Simplex Algorithm, part 4: Efficiency/Pivot Rules
Переглядів 1868 місяців тому
The focus of this part lies on common options for pivot rules, and the number of pivot steps needed. 00:00 Warm-Up Example 02:43 Efficiently implementing a pivot step 05:42 Pivot Rules 08:25 Exponential running time/Klee-Minty Cubes 10:52 Fewer Pivot Steps? 14:22 Summary of Simplex Method
Simplex Algorithm, part 2: Exceptions
Переглядів 1088 місяців тому
00:00 Unboundedness 04:30 Degeneracy 08:30 Infeasibility, or how to find the initial basic feasible solution 10:20 Auxiliary linear program with auxiliary variables 14:23 Back to the original problem
Simplex Algorithm, part 3: the simplex algorithm in general
Переглядів 1028 місяців тому
After introducing linear programming by examples in the previous 2 videos, we here take a look at a general description of the simplex algorithm. 00:00 Simplex tableaus in general 04:49 Proof of Lemma 07:15 Decisions in the algorithm 09:15 Correctness statement (without proof)
Simplex Algorithm, part 1: Introductory Example
Переглядів 1998 місяців тому
Here I introduce the simplex algorithm by an example. This example follows the book "Understanding and Using Linear Programming" by Jirka Matoušek and Bernd Gärtner. Make sure to know the concepts of equational (aka standard) form and basic feasible solutions, before watching this (I have a video on these concepts.) 00:00 Deriving the equational form and the first basis 02:52 A simplex tableau ...
Theory of Linear Programming: convex polytopes, equational form and basic feasible solutions
Переглядів 1928 місяців тому
In preparation for the simplex algorithm we are taking a look at some algebraic and geometric concepts underlying linear programming. 00:00 linear programming vs linear algebra 02:05 convex polytopes 06:21 cubes and cross-polytopes 10:55 Writing LPs in the form Ax at most x 13:00 Equational form 18:14 basic feasible solutions: geometric intuition 22:38 What is a basic feasible solution (bfs)? 2...
Integer Linear Programming
Переглядів 5809 місяців тому
Introduction to Integer Linear Programming (ILP). We are going to take a look at ILPs for three problems: - maximum weight perfect matching - minimum vertex cover - maximum independent set 00:00 Integer Linear Programming 04:13 Maximum Weight Perfect Matching 09:54 Integer solution to the LP relaxation 17:49 Minimum Vertex Cover 19:38 Rounding 24:34 Maximum Independent Set 25:58 LP relaxation n...
Integer Linear Programming (ILP), part 2: More Examples + techniques for solving ILPs
Переглядів 1899 місяців тому
This is a "bonus" video on ILPs, where I show you for two algorithmic problems, how to model them as ILP: shortest path and TSP. At the end I briefly discuss techniques for solving ILPs like branch and bound. 00:00 Shortest path as ILP 03:30 Shortest path as LP 05:40 TSP 07:58 MTZ formulation 10:05 DFJ formulation 12:24 Solving ILPs 12:55 Branch and bound 15:33 Cutting Planes
Linear Programming: Introduction and Examples
Переглядів 6559 місяців тому
An introduction to linear programming, largely consisting of examples. It follows the book "Understanding and Using Linear Programming" by Jiří Matoušek and Bernd Gärtner (Chapters 1 2) 00:00 Introduction 01:53 A linear program 06:26 Example in Python 07:73 Cases: 1, several, no and unbounded solution 09:44 Efficiency/Algorithms 11:40 Diet problem 16:16 Network Flow 20:11 Fitting a line 24:49 S...
Fully Polynomial-Time Approximation Scheme for the Knapsack Problem
Переглядів 3,7 тис.9 місяців тому
We first present a pseudo-polynomial time algorithm for the knapsack problem, which we then use as a basis for a fully polynomial-time approximation scheme. There is also some complexity theory in this video, since we need concepts like pseudo-polynomial (vs. polynomial) time algorithms, weakly (vs. strongly) NP-hard problems, and of course (fully) polynomial time approximation schemes. 00:00 K...
Approximation Algorithm for Metric k-Center using Parametric Pruning
Переглядів 5839 місяців тому
Approximation Algorithm for Metric k-Center using Parametric Pruning
Approximation Algorithm for Multiway Cut
Переглядів 6839 місяців тому
Approximation Algorithm for Multiway Cut
Approximations algorithms for the Steiner Tree Problem and the Traveling Salesperson Problem (TSP)
Переглядів 1,4 тис.9 місяців тому
Approximations algorithms for the Steiner Tree Problem and the Traveling Salesperson Problem (TSP)
From Set Cover to Shortest Superstring
Переглядів 4169 місяців тому
From Set Cover to Shortest Superstring
Approximation algorithm for vertex cover using local ratio (aka layering)
Переглядів 4649 місяців тому
Approximation algorithm for vertex cover using local ratio (aka layering)
Greedy Approximation Algorithm for Set Cover
Переглядів 4,6 тис.9 місяців тому
Greedy Approximation Algorithm for Set Cover
Approximation Algorithms: Introduction by the Example of Vertex Cover
Переглядів 1,2 тис.10 місяців тому
Approximation Algorithms: Introduction by the Example of Vertex Cover
Practical Efficiency of Fibonacci Heaps
Переглядів 13310 місяців тому
Practical Efficiency of Fibonacci Heaps
Binomial heaps (part 3/3): Lazy Union
Переглядів 27610 місяців тому
Binomial heaps (part 3/3): Lazy Union
Binomial Heaps (part 2/3): Amortized Analysis of Insert
Переглядів 97610 місяців тому
Binomial Heaps (part 2/3): Amortized Analysis of Insert
Binomial heaps (part 1/3): Introduction and worst-case analysis
Переглядів 83110 місяців тому
Binomial heaps (part 1/3): Introduction and worst-case analysis
Traveling Salesperson Problem and the Held-Karp Dynamic Programming Algorithm
Переглядів 33110 місяців тому
Traveling Salesperson Problem and the Held-Karp Dynamic Programming Algorithm
Djikstra's algorithms and priority queues (recap)
Переглядів 15310 місяців тому
Djikstra's algorithms and priority queues (recap)
Good decent video. better definition of convex here if you didn't understand her mathematical expressiveness : ua-cam.com/video/KdKjXRwEa_0/v-deo.html
Hi, thanks for explanation, but it didn’t get the difference between perfect and random list for deletion. What is the difference between deletion of 12 in the first implementation and deletion of 10 in the second? Thanks in advance
In the first implementation, if we would want to delete the 12, the whole second half of the list would need to change. The 13 would need to take the role of the 12 with 4 levels, while 15 would now only have 1 level instead of 2, and so on. But if it is a randomized skip list, deleting the 12 is easy. All the references into the 12 now need to continue to the next nodes as seen from the 12; however none of the nodes need to change its number of levels.
@@algorithmslab oh thanks, changing of level is a key to understand the difference :)
Amazing video really good explanation ! Thanks so much
Cheers
Hey can you guys do a trajectory on an ideal pathway to learning computational geometry, beginning with high school algebra?
The main prerequisite is basic knowledge of “algorithms and data structures”, and the prerequisites for that. Prerequisites for “algorithms and data structures” are basic programming skills (language does not matter, it is more about the concepts) and “high-school maths”++. So the pathsway would be: A. Introduction to programming B. Mathematics for Computer Scientists (must include proof techniques & basic probability theory) C. Introduction to Algorithms and Data structures And now you should be set. The more exposure you had to algorithms & basic maths, the easier it should be, but in principle the above should be sufficient. A and B are independent of each other, and may be known partially from school. “Mathematics for Computer Scientists” is of course a bit vague, but a solid mathematical foundation is crucial for algorithms. And sometimes a basic maths course for computer scientists does not yet include probability theory, so it might be necessary to learn that separately. All of the above are standard first-year courses in a computer science curriculum, so you will find plenty of excellent online resources. For Algorithms and Data Structures I also have videos, but there are also excellent MOOCs, e.g. from Princeton and Stanford. Finally, I do have a video where I list prerequisites for my advances algorithms course: ua-cam.com/video/omsr-55nG7s/v-deo.htmlsi=bwRs7wCMCA-8ZWgb I think this comes quite close to what I would expect for computational geometry.
@@algorithmslab thank you so much!
This is a great playlist. I love all your videos. Please share the playlist slides so I can adopt them in my course.
I switched to a different set of slides a while ago, and don't have these lying around anymore. If you send me an e-mail (to my TU Dortmund address), I could see whether I can help you with a different slide set (also based on the Cormen et al.)
Can you please provide the slides?
the slides are the second half of the following: github.com/kbuchin/slide-archive/blob/main/advanced-algorithms-2024/02-Amortized-Analysis.pdf
Professor, I was not able to understand how did you write the horizontal line segment comparison in status comparator as in the book (computational geometry algorithms and applications) on p. 26 it is written that horizontal line segments must be placed last, I am not sure how does your code work. But it works correctly as I have seen in my points test cases. Thanks and Regards
In the video I just gloss over this, so I assume you are referring to the Jupyter notebook. The comparator class there unfortunately turned out rather complicated, since it has to handle quite a few edge cases to make the code reasonable robust. The horizontal line segments are handled in the last two cases in the method "_check_special_cases". There one can see that a segment comes later in the comparison, when the y-coordinates of the two end points are (nearly) the same and the other segment is not to the right of the event point. The latter is necessary, because (as is written in the book) "If there is a horizontal segment, it comes last among all segments containing p".
@@algorithmslab yes proffesor I understood and wrote the code, it works. I wrote the code in cpp and it is really fast it takes about 1 second for brute force for 10000 segments. it is a lovely code you wrote. Thanks and Regards
@@user-nw9ch3zi9d great to hear, thanks! (And the code was written by the other author of the notebook, so I will pass on the compliment)
Very amazing! Before seeing the video, I could not get the physical meaning of the dual variables of the LP. The visualization is fantastic! The whole lecture is clear and inspired.
Thank you! Happy to hear this.
to the point and concise, really helpful. thanks!!
Thank you so much for this video!
Excellent video, really well explained, with clear examples. Thank you.
SOO helpful! thanks!
great to hear, thanks!
Servus
Glück auf
sir I very very love u 😘😘
Happy to hear that the videos are helpful!
very good explanation. thank u sir
Very good presentation, thanks!
But wait, how did you fix the RB properties at 17:56, if #5 is violated? "For each node, all paths from the node to descendant leaves contain the same number of black nodes".
The important observation here, is that #5 is actually never violated (i.e. assuming it holds at the beginning, all operations that we do don't break it). When inserting a new node, we make it red. So assuming that I had a correct tree before, the only violation that I now might have is one red child-parent pair. This is fixed in "Step 3". For all operations in Step 3 it is quite clear that they don't introduce a violation of #5. Only for the last rotation (the right rotation on the slide) we have to be careful. There we recolor z and b. But I explain, starting at 17:18, why property #5 still holds, assuming it was true before. So in short, the recoloring of z and b is what we do to make sure that #5 is not violated. I hope this answers the question.
Can you kindly explain how the potential difference in case of linking in -c??
Linking means that I take one of the trees and make it a subtree of another tree by connecting it via an edge to the root of that tree. That means that by linking the number of trees goes down by one. So if the number of trees before linking is some number k, it is k-1 after linking. The potential is c* number of trees. So before linking the potential was c*k, and after the linking it is c*(k-1) = c*k - c. The change in potential is therefore (c*k - c) - c*k = - c.
@@algorithmslab Thanks!
Even though I dont understand some of the terms you use (its me on since Im not that good in DSA) but as a whole I like the way you explain things. Im currently studying DSA.
Thanks! This video is part of a series, and it is probably a good idea to first watch the video that introduces binary search trees (ua-cam.com/video/qIJCoaTrHVI/v-deo.htmlsi=N-9x-yNDKw8VcHmi) Success with studying Data Structures and Algorithms!
Thank you😊 ❤
Best explanation I got from my 1hr of searching!!!
Great video!
2024 & you're still helping TU/e students! Thanks!
Can we get the pdfs of the slids? Just like the Data Structure once
okay, I didn't really have a good place to point at, but this should work for now: github.com/kbuchin/slide-archive
@@algorithmslab Thank a lot sir!!
Your ways of teaching as well as the slides are absolutely awesome. If I get your slides PDF available, it would enlighten me a lot!!
Thanks! In the video description there is a link to the copy of the course (canvas.instructure.com/courses/3752774). It also contains the slides; for each unit, the slides are in the unit summary at the start of the unit. As a direct link to this slide set, the following should work: canvas.instructure.com/files/158068175/download?download_frd=1
My analysis of algorithm teacher directly use your pdf to teach us.NO JOKE
That's great to hear! It is great to see that they are being used, just like I am happy that people find this videos useful. I also like reusing slides from colleagues.
Thanks for the video! I was wondering for the Min cut - Max Flow LP why the Cut that was displayed in 40:21 did not look minimal to me. The edges that are cut (in the original graph in 29:47) have a summed up cost of 12 whereas cutting away the vertices so the new connected components are {o, a} and {b, c, d, e, n} would have a min cut cost of 4 which is equal to the max flow of the network. Did I miss something in the example?
It does not look minimal, because it is not minimal. In the video (at 40:21), I just wanted to show a cut to demonstrate the constraints; it was not intended to be minimal (sorry, if that wasn't clear). The cut fulfills the constraints of the ILP (if setting at least y_{2,5}=1, y_{4,5}=1 and y_{3,6} = 1) , but its objective value is 5 (= 1 + 2 + 2). Indeed, setting u_0=0 and u_2=0 and all other u_i=1, corresponds to the cut {o,a} and {b,c,d,e,n}, which results in an objective value of 4. Just one more remark about my cut, which was actually not intentional but is okay: it has the edge from 6 to 4, where we now go from a "1" to a "0". But that is okay since 0 - (-1) = 1 >= 0. I hope this clarifies the example and answers your question!
Yeah that clears things up! Thanks for taking the time to write such an elaborate answer!@@algorithmslab
thank you for making this video, it really helped me to understand the proof behind the steiner tree approximation algo!
First!
Thank you so much for putting this series online! I'm rewatching this for my advanced algorithms class and it's so helpful!
Love the explanation for dynamic tables accounting method
Happy to hear this, thanks!
Thank you so much. You covered almost half of my semester in only one video. Although I still haven't comprehended the proofs quite clearly but at least I know where to look.
awesome vid :)
amazing lecture. learnt so much in just 45 minutes. thank you
That's great to hear!
Could you please give me an idea, how the base-3 counter amortized cost will be calculated here? I am getting, Ci = 2, Potential change = 2. So, amortized cost = 4. Is it okay?
Thanks!
Thanks a lot for this video, very well explained and easy to follow. It helped me a lot!
Thanks a bunch!
Thank you Prof. I only wish that for just that are just starting now, some code be shown and explained so we’d have a glimpse of how to actually mod this in code
you are a legend!
This video is proof that you don't need a 50 minute MIT lecture to teach something so simple!
Promo`SM
Great lecture. Thank you!
underrated channel, helps me a lot
Thanks a lot!!
Thanks for the video! Keep up the good work.
Thanks for commenting!
this is slept on. what a fantastic explanation. you're the man!
Thank you, it is a detailed explnation