![Algorithms Lab](/img/default-banner.jpg)
- Видео 118
- Просмотров 302 306
Algorithms Lab
Германия
Добавлен 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 tot...
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 tot...
Просмотров: 335
Видео
Steiner Forest via Primal-Dual
Просмотров 8958 месяцев назад
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
Просмотров 4438 месяцев назад
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
Просмотров 9168 месяцев назад
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
Просмотров 2629 месяцев назад
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
Просмотров 3799 месяцев назад
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
Просмотров 1949 месяцев назад
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
Просмотров 1129 месяцев назад
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
Просмотров 1079 месяцев назад
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
Просмотров 2059 месяцев назад
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
Просмотров 2099 месяцев назад
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
Просмотров 6039 месяцев назад
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
Просмотров 2059 месяцев назад
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
Просмотров 6809 месяцев назад
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,8 тыс.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
Просмотров 61510 месяцев назад
Approximation Algorithm for Metric k-Center using Parametric Pruning
Approximation Algorithm for Multiway Cut
Просмотров 69910 месяцев назад
Approximation Algorithm for Multiway Cut
Approximations algorithms for the Steiner Tree Problem and the Traveling Salesperson Problem (TSP)
Просмотров 1,5 тыс.10 месяцев назад
Approximations algorithms for the Steiner Tree Problem and the Traveling Salesperson Problem (TSP)
From Set Cover to Shortest Superstring
Просмотров 45010 месяцев назад
From Set Cover to Shortest Superstring
Approximation algorithm for vertex cover using local ratio (aka layering)
Просмотров 49110 месяцев назад
Approximation algorithm for vertex cover using local ratio (aka layering)
Greedy Approximation Algorithm for Set Cover
Просмотров 4,8 тыс.10 месяцев назад
Greedy Approximation Algorithm for Set Cover
Approximation Algorithms: Introduction by the Example of Vertex Cover
Просмотров 1,3 тыс.10 месяцев назад
Approximation Algorithms: Introduction by the Example of Vertex Cover
Practical Efficiency of Fibonacci Heaps
Просмотров 13510 месяцев назад
Practical Efficiency of Fibonacci Heaps
Binomial heaps (part 3/3): Lazy Union
Просмотров 27810 месяцев назад
Binomial heaps (part 3/3): Lazy Union
Binomial Heaps (part 2/3): Amortized Analysis of Insert
Просмотров 98510 месяцев назад
Binomial Heaps (part 2/3): Amortized Analysis of Insert
Binomial heaps (part 1/3): Introduction and worst-case analysis
Просмотров 86610 месяцев назад
Binomial heaps (part 1/3): Introduction and worst-case analysis
Traveling Salesperson Problem and the Held-Karp Dynamic Programming Algorithm
Просмотров 34310 месяцев назад
Traveling Salesperson Problem and the Held-Karp Dynamic Programming Algorithm
Djikstra's algorithms and priority queues (recap)
Просмотров 15910 месяцев назад
Djikstra's algorithms and priority queues (recap)
In the first algorithm is not clear how to recombine the selected vertices to obtain a vertex cover. The lemma is true, but the dimension of obtained vertex cover can be lower than the minimum :(. I can show to you a counter example on the size of an optimal vertex cover with just 5 vertices. The first algorithm does not approximate at all, since it does not return a correct vertex cover. However, you give to me the correct intuition about layering❤
Thanks for the comment! I expect there is simply a misunderstanding about the base case of the recursion. In short, the algorithm chooses as vertex cover the vertices v which have w(v)=0 in the base case (i.e. when the recursion stops). I think the problem is that I say this very late in the video (starting at 10:44) and never write down the full algorithm. (Yes, reordering the presentation and adding pseudo-code seems like a good idea.) Here is a simple, non-recursive formulation of the algorithm in pseudo-code: 1. While there exists an edge (u, v), such that min{w(u), w(v)} > 0: 2. Let eps = min{w(u), w(v)}. 3. w(u) ← w(u) − eps. 4. w(v) ← w(v) − eps. 5. Return the set C = {v | w(v) = 0} LIne 5 here corresponds to the base case of the recursion. I hope this clarifies the algorithm. This algorithm is by Bar-Yehuda and Evan ["A local ratio theorem for approximating the weighted vertex cover problem". Ann. Discr. Math. 25, 27-46.], and a nice article about it is here: www.wisdom.weizmann.ac.il/~oded/bbfr.pdf [Bar-Yehuda, R., Bendel, K., Freund, A., & Rawitz, D. (2004). Local ratio: A unified framework for approximation algorithms. In memoriam: Shimon Even 1935-2004. ACM Computing Surveys (CSUR), 36(4), 422-463.]
the best..
Amazing! Thank you
Thank you very much for your clarification but could you please provide me with any reference or notes or book to further boost my understanding?
There are certainly many excellent books and notes on linear programming. My lectures/videos are based on the book "Understanding and using linear programming" by Jiří Matoušek and Bernd Gärtner (2007). It is a great book, because it strikes a good balance between the underlying maths and how LPs are actually used.
Nice and enlightening video, thanks! If I'd dare some criticism, It could be more clear the reason for the rotation in case2. It seems almost like the criterium is whether it's the right or left child of the parent, but that depends again on which child the parent is of the grandparent. Anyway, it's the most informative video I found on the topic, so good job!
Thanks, good point. From the perspective of the algorithm it makes sense to order the cases as they are (i.e. discuss the corresponding slide from left to right). But for explaining why we have the cases, it might be better to go from right to left (i.e. what do we want to achieve, how we get if from case 3, and then how we get case 3, in case we have case 2). Anyway, you figured it out, so I achieved my goal!
Good decent video. better definition of convex here if you didn't understand her mathematical expressiveness : ruclips.net/video/KdKjXRwEa_0/видео.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: ruclips.net/video/omsr-55nG7s/видео.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 (ruclips.net/video/qIJCoaTrHVI/видео.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.
Great to hear that it's helpful! This video covers parts of three chapters from the Vazirani book (13,14,15), so I fully see how this could be spread out over several lectures. My aim here was to give a first overview of LP-based techniques for approximation algorithms.
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?
This doesn't quite work, because Ci might not be constant. The first question you need to do is to define an appropriate potential function. For the binary counter it was the number of 1s, but here it has to look different (Hint: It has to involve the number of 2s. It can also involve the number of 1s.) c_i is the actual cost. Just like for the binary counter, this may vary, i.e., it is not necessarily constant. The trick then is (again like for the binary counter) to make sure to have defined the potential function in such a way, that whenever the counter has to change many digits, that then the potential drops by a similar number. This is a nice exercise.
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
We are working on a collection of Jupyter notebooks for the algorithms presented in the videos. I nice feature is that they don't just provide the code but also lets you visually explore the algorithms step by step. The repository is here: github.com/ls11ae/geoalg-notebooks Specifically, for line segment intersection the notebook is here: nbviewer.org/github/ls11ae/geoalg-notebooks/blob/master/notebooks/02-LineSegmentIntersection.ipynb To modify it and to use the interactive elements, you can use binder (and wait a bit) or simply download the repo.
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!
Happy to hear, thanks!
underrated channel, helps me a lot
Great to hear!