You must be logged in to take this course → LOGIN | REGISTER NOW
Combinatorial Optimization consists of finding an optimal-object from a finite object’s set where exhaustive search may not be feasible. Through this [course_title] you will be able to develop the best airline-network of spokes and destinations, decide which taxis in a fleet to route to pick up fares. This [course_title] will help you understand the topics like non-bipartite-matchings and cover many results extending the fundamental results of matchings, flows, and matroids.
Assessment
This course does not involve any written exams. Students need to answer 5 assignment questions to complete the course, the answers will be in the form of written work in pdf or word. Students can write the answers in their own time. Each answer needs to be 200 words (1 Page). Once the answers are submitted, the tutor will check and assess the work.
Certification
Edukite courses are free to study. To successfully complete a course you must submit all the assignment of the course as part of assessment. Upon successful completion of a course, you can choose to make your achievement formal by obtaining your Certificate at a cost of £49.
Having an Official Edukite Certification is a great way to celebrate and share your success. You can:
- Add the certificate to your CV or resume and brighten up your career
- Show it to prove your success
Course Credit: MIT
Course Curriculum
Module: 01 | |||
Non-Bipartite Matching: Tutte-Berge Formula, Gallai-Edmonds Decomposition, Blossoms | 00:15:00 | ||
Non-Bipartite Matching: Edmonds’ Cardinality Algorithm and Proofs of Tutte-Berge Formulas and Gallai-Edmonds Decomposition | 00:30:00 | ||
Cubic Graphs and Matchings, Factor-Critical Graphs, Ear Decompositions | 00:30:00 | ||
The Matching Polytope, Total Dual Integrality, and Hilbert Bases | 00:30:00 | ||
Total Dual Integrality, Totally Unimodularity | 00:30:00 | ||
Posets and Dilworth Theorem | 00:30:00 | ||
Partitioning Digraphs by Paths and Covering them by Cycles | 00:30:00 | ||
Module: 02 | |||
Proof of the Bessy-Thomasse Result | 00:30:00 | ||
Matroids: Defs, Dual, Minor, Representability | 00:30:00 | ||
Matroids: Representability, Greedy Algorithm, Matroid Polytope | 00:30:00 | ||
Matroid Intersection | 00:30:00 | ||
Matroid Intersection, Matroid Union, Shannon Switching Game | 00:30:00 | ||
Matroid Intersection Polytope, Matroid Union | 00:30:00 | ||
Matroid Union, Packing and Covering with Spanning Trees, Strong Basis Exchange Properties | 00:30:00 | ||
Module: 03 | |||
Matroid Matching: Examples, Complexity, Lovasz’s Minmax Relation for Linear Matroids | 00:30:00 | ||
Jump Systems: Definitions, Examples, Operations, Optimization, and Membership | 00:30:00 | ||
Graph Orientations, Directed Cuts (Lucchesi-Younger Theorem), Submodular Flows | 00:30:00 | ||
Submodular Flows: Examples, Edmonds-Giles Theorem, Reduction to Matroid Intersection in Special Cases | 00:30:00 | ||
Splitting Off | 00:30:00 | ||
Proof of Splitting-Off | 00:30:00 | ||
Multiflow and Disjoint Path Problems | 00:30:00 | ||
The Okamura-Seymour Theorem | 00:30:00 | ||
Assessment | |||
Submit Your Assignment | 00:00:00 | ||
Certification | 00:00:00 |
Course Reviews
No Reviews found for this course.