Meetings

Click on the theme item for the meeting plan for that theme.Click on the meeting item for references, exercises, and additional reading related to it.

**Theme 1 : Network Flows**- 4 meetings- Meeting 01 : Wed, Jan 15, 06:00 am-06:00 am
- Meeting 02 : Fri, Jan 17, 11:00 am-11:50 am
- Meeting 03 : Mon, Jan 20, 09:00 am-09:50 am
- Meeting 04 : Tue, Jan 21, 08:00 am-08:50 am

Introduction to the course, teachers. Evaluation pattern and policy. Introduction to flows and properties. Definition of a flow network. Definition of a flow. Value of a flow. Flow is well-defined. It has a bounded maximum. "Lifting" the definition of a low to involve pairs of sets. Obtaining an upper bound on the flow in terms of the min-cut. References Introduction to Algorithms: CLR, 2nd Edition, Chapter 26 Exercises Reading Introduction to the course, teachers. Evaluation pattern and policy. Introduction to flows and properties. Definition of a flow network. Definition of a flow. Value of a flow. Flow is well-defined. It has a bounded maximum. "Lifting" the definition of a low to involve pairs of sets. Obtaining an upper bound on the flow in terms of the min-cut.References: Introduction to Algorithms: CLR, 2nd Edition, Chapter 26 We complete the properties satisfied by a flow in a flow network. The aim to prove two intuitive properties: all the flow that leaves s arrives at t. second if we partition the vertex set into an s-t cut, then all the flow that leaves s, crosses from the part that contains s into that part that contains t. Then we define the residual network for a flow, and observe that if f is flow in G, and G_f is the residual network for f, and f' is a flow in G_f, then f+f' is a flow in G_f. We introduce the notion of an augmenting path, and Then we prove the max-flow min-cut theorem. References CLR Chapter 26. Exercises Exercises in Chapter 26 of CLR Reading We complete the properties satisfied by a flow in a flow network. The aim to prove two intuitive properties: all the flow that leaves s arrives at t. second if we partition the vertex set into an s-t cut, then all the flow that leaves s, crosses from the part that contains s into that part that contains t. Then we define the residual network for a flow, and observe that if f is flow in G, and G_f is the residual network for f, and f' is a flow in G_f, then f+f' is a flow in G_f. We introduce the notion of an augmenting path, and Then we prove the max-flow min-cut theorem.References: CLR Chapter 26. Exercises: Exercises in Chapter 26 of CLR Discussed the Ford Fulkerson Template algorithm for maximum flow. Demonstrated a constant sized network where the edge capacities and the choice of paths force this algorithm to take exponential time. Discussed reduction of bipartite matching problem to flows in a network. Discussed Edmonds Karp algorithm where we choose the shortest s-t path in each iteration instead of any s-t path. References Exercises Reading Discussed the Ford Fulkerson Template algorithm for maximum flow. Demonstrated a constant sized network where the edge capacities and the choice of paths force this algorithm to take exponential time. Discussed reduction of bipartite matching problem to flows in a network. Discussed Edmonds Karp algorithm where we choose the shortest s-t path in each iteration instead of any s-t path.References: None To Be Announced References Exercises Reading To Be AnnouncedReferences: None **Theme 2 : NP-completeness and Reductions**- 3 meetings- Meeting 05 : Wed, Jan 22, 12:00 pm-12:50 pm
- Meeting 06 : Fri, Jan 24, 11:00 am-11:50 am
- Meeting 07 : Mon, Jan 27, 09:00 am-09:50 am

Discussed the notions of Search/Optimization problem. Corresponding decision problems (with a parameter), encoding of a problem instance as a string. Defined the class P, NP. Verification vs solving. Every language in P is infact in NP. Defined co-NP. Polynomial time reductions. References CLRS Chapter 34. Exercises Reading Discussed the notions of Search/Optimization problem. Corresponding decision problems (with a parameter), encoding of a problem instance as a string. Defined the class P, NP. Verification vs solving. Every language in P is infact in NP. Defined co-NP. Polynomial time reductions.References: CLRS Chapter 34. Defined class NPC, reductions, transitivity of reductions, Mentioned 3CNF-SAT is NPC without proof. Reduction from 3CNF-SAT to Clique and Clique to Independent Set. References CLRS Chapter 34. Exercises Reading Defined class NPC, reductions, transitivity of reductions, Mentioned 3CNF-SAT is NPC without proof. Reduction from 3CNF-SAT to Clique and Clique to Independent Set.References: CLRS Chapter 34. Further on reductions. Clique to Vertex cover, CNF-SAT to Directed Hamiltonian Path. (This reduction is taken from Arora and Barak, Chapter 2). References CLRS and Computation Complexity: A modern approach -- By S. Arora and B. Barak http://www.cs.princeton.edu/theory/complexity/ Exercises Reading Further on reductions. Clique to Vertex cover, CNF-SAT to Directed Hamiltonian Path. (This reduction is taken from Arora and Barak, Chapter 2).References: CLRS and Computation Complexity: A modern approach -- By S. Arora and B. Barak http://www.cs.princeton.edu/theory/complexity/ **Theme 3 : Approximation algorithms.**- 52 meetings- Meeting 08 : Tue, Jan 28, 08:00 am-08:50 am
- Meeting 09 : Wed, Jan 29, 12:00 pm-12:50 pm
- Meeting 10 : Fri, Jan 31, 11:00 am-11:50 am
- Meeting 11 : Mon, Feb 03, 09:00 am-09:50 am
- Meeting 12 : Tue, Feb 04, 08:00 am-08:50 am
- Meeting 13 : Wed, Feb 05, 12:00 pm-12:50 pm
- Meeting 14 : Fri, Feb 07, 11:00 am-11:50 am
- Meeting 15 : Mon, Feb 10, 09:00 am-09:50 am
- Meeting 16 : Tue, Feb 11, 08:00 am-08:50 am
- Meeting 17 : Wed, Feb 12, 12:00 pm-12:50 pm
- Meeting 18 : Fri, Feb 14, 11:00 am-11:50 am
- Meeting 19 : Mon, Feb 17, 09:00 am-09:50 am
- Meeting 20 : Tue, Feb 18, 08:00 am-08:50 am
- Meeting 21 : Wed, Feb 19, 06:00 am-06:00 am
- Meeting 22 : Fri, Feb 21, 11:00 am-11:50 am
- Meeting 23 : Mon, Feb 24, 09:00 am-09:50 am
- Meeting 24 : Tue, Feb 25, 08:00 am-08:50 am
- Meeting 25 : Wed, Feb 26, 06:00 am-06:00 am
- Meeting 26 : Fri, Feb 28, 11:00 am-11:50 am
- Meeting 27 : Mon, Mar 03, 09:00 am-09:50 am
- Meeting 28 : Tue, Mar 04, 08:00 am-08:50 am
- Meeting 29 : Wed, Mar 05, 06:00 am-06:00 am
- Meeting 30 : Fri, Mar 07, 11:00 am-11:50 am
- Meeting 31 : Mon, Mar 10, 09:00 am-09:50 am
- Meeting 32 : Tue, Mar 11, 08:00 am-08:50 am
- Meeting 33 : Wed, Mar 12, 06:00 am-06:00 am
- Meeting 34 : Fri, Mar 14, 11:00 am-11:50 am
- Meeting 35 : Mon, Mar 17, 09:00 am-09:50 am
- Meeting 36 : Tue, Mar 18, 08:00 am-08:50 am
- Meeting 37 : Wed, Mar 19, 06:00 am-06:00 am
- Meeting 38 : Fri, Mar 21, 11:00 am-11:50 am
- Meeting 39 : Mon, Mar 24, 09:00 am-09:50 am
- Meeting 40 : Tue, Mar 25, 08:00 am-08:50 am
- Meeting 41 : Wed, Mar 26, 06:00 am-06:00 am
- Meeting 42 : Fri, Mar 28, 11:00 am-11:50 am
- Meeting 43 : Mon, Mar 31, 09:00 am-09:50 am
- Meeting 44 : Mon, Apr 14, 09:00 am-09:50 am
- Meeting 45 : Tue, Apr 15, 08:00 am-08:50 am
- Meeting 46 : Wed, Apr 16, 12:00pm-12:50pm
- Meeting 47 : Fri, Apr 18, 11:00 am-11:50 am
- Meeting 48 : Mon, Apr 21, 09:00 am-09:50 am
- Meeting 49 : Tue, Apr 22, 08:00 am-08:50 am
- Meeting 50 : Wed, Apr 23, 12:00pm-12:50pm
- Meeting 51 : Fri, Apr 25, 11:00 am-11:50 am
- Meeting 52 : Mon, Apr 28, 09:00 am-09:50 am
- Meeting 53 : Tue, Apr 29, 08:00 am-08:50 am
- Meeting 54 : Wed, Apr 30, 12:00pm-12:50pm
- Meeting 55 : Fri, May 02, 11:00 am-11:50 am
- Meeting 56 : Mon, May 05, 09:00 am-09:50 am
- Meeting 57 : Tue, May 06, 08:00 am-08:50 am
- Meeting 58 : Wed, May 07, 12:00pm-12:50pm
- Meeting 59 : Fri, May 09, 11:00 am-11:50 am

In the first part of the lecture showed examples of decision version as a black box being used to construct the solution to the optimization problem. Showed examples of Satisfiability and Independent set. (reference Appendix A.5, Vazirani).<br> Introduced the notion of approximation algorithm for a problem. Defined an alpha factor approximation algorithm. Considered the example of vertex cover, lower bound and a easy 2 approximation. Showed that the analysis of the algorithm is tight using Kn,n as an example. Showed that the approximation guarantee cannot be improved by using Kn on odd-vertices as an example. References Vazirani Chapter 1. Exercises Reading In the first part of the lecture showed examples of decision version as a black box being used to construct the solution to the optimization problem. Showed examples of Satisfiability and Independent set. (reference Appendix A.5, Vazirani).

Introduced the notion of approximation algorithm for a problem. Defined an alpha factor approximation algorithm. Considered the example of vertex cover, lower bound and a easy 2 approximation. Showed that the analysis of the algorithm is tight using Kn,n as an example. Showed that the approximation guarantee cannot be improved by using Kn on odd-vertices as an example.References: Vazirani Chapter 1. Discussed properties of a good lower bound -- 1) easy to compute (polynomial time), 2) as close as possible to OPT. TSP was considered. Inapproximability in general graphs. Notion of gap introducing reductions. Metric case -- 2 approximation and 3/2 approximation. References Vazirani Chapter 3. Exercises Reading Discussed properties of a good lower bound -- 1) easy to compute (polynomial time), 2) as close as possible to OPT. TSP was considered. Inapproximability in general graphs. Notion of gap introducing reductions. Metric case -- 2 approximation and 3/2 approximation.References: Vazirani Chapter 3. Steiner tree, reduction to Metric case, general approximation preserving reduction definition. 2-approximation for Metric Steiner tree. <br> Job scheduling on identical parallel machines. Greedy 2 approximation algorithm. References Vazirani Chapter 3. Exercises Reading Steiner tree, reduction to Metric case, general approximation preserving reduction definition. 2-approximation for Metric Steiner tree.

Job scheduling on identical parallel machines. Greedy 2 approximation algorithm.References: Vazirani Chapter 3. Job scheduling on identical parallel machines. 2-approximation algorithm (recap from last class), 4/3 approximation by longest processing time. Introduced the problem of set-cover. References Williamson and Shmoys Chapter 2 for Job scheduling. Exercises Reading Job scheduling on identical parallel machines. 2-approximation algorithm (recap from last class), 4/3 approximation by longest processing time. Introduced the problem of set-cover.References: Williamson and Shmoys Chapter 2 for Job scheduling. Set cover unweighted f-approximation and weighted ln (n) approximation greedy algorithm. References Vazirani Chapter 2. Exercises Reading Set cover unweighted f-approximation and weighted ln (n) approximation greedy algorithm.References: Vazirani Chapter 2. Metric k-center problem, greedy 2 approximation algorithm, inapproximability of < 2 by reduction from the dominating set problem. References Shmoys and Williamson Chapter 2. Exercises Reading Metric k-center problem, greedy 2 approximation algorithm, inapproximability of < 2 by reduction from the dominating set problem.References: Shmoys and Williamson Chapter 2. Local search technique for approximation algos. Started with max-cut and showed a simple 1/2 approximation using local search. <br> Minimum degree spanning tree problem. Defined a local move -- example where local move to max-degree vertex is not applicable directly. However, applying local move to a low-degree vertex enables a local move for a high-degree vertex. Generic lower bound on OPT. References Shmoys and Williamson Chapter 2 for Minimum Degree spanning tree. Exercises Reading Local search technique for approximation algos. Started with max-cut and showed a simple 1/2 approximation using local search.

Minimum degree spanning tree problem. Defined a local move -- example where local move to max-degree vertex is not applicable directly. However, applying local move to a low-degree vertex enables a local move for a high-degree vertex. Generic lower bound on OPT.References: Shmoys and Williamson Chapter 2 for Minimum Degree spanning tree. Edge coloring Delta + 1 approximation. References Shmoys and Williamson Chapter 2. Exercises Reading Edge coloring Delta + 1 approximation.References: Shmoys and Williamson Chapter 2. PTAS and FPTAS definitions. 0/1 Knapsack problem, example when greedy can give unbounded ratio. Dynamic Programming Algorithm. FPTAS for 0/1 Knapsack. References Shmoys and Williamson Chapter 3. Exercises Reading PTAS and FPTAS definitions. 0/1 Knapsack problem, example when greedy can give unbounded ratio. Dynamic Programming Algorithm. FPTAS for 0/1 Knapsack.References: Shmoys and Williamson Chapter 3. Running time for FPTAS completed. Discussion about pseudopolynomial time and strongly NP-hard problems. Existence of FPTAS with some conditions on the problem imply a psedupolynomial time algorithm. <br> Introduction to LPs, ILPs. Set cover LP and deterministic rounding to get an f-approximation algorithm. References First part Vazirani Chapter 8. Second part Shmoys and Williamson Chapter 1. Exercises Reading Running time for FPTAS completed. Discussion about pseudopolynomial time and strongly NP-hard problems. Existence of FPTAS with some conditions on the problem imply a psedupolynomial time algorithm.

Introduction to LPs, ILPs. Set cover LP and deterministic rounding to get an f-approximation algorithm.References: First part Vazirani Chapter 8. Second part Shmoys and Williamson Chapter 1. Completed proof for f-approximation. 1/2 integrality of vertex cover. Introduced the notion of a dual. References Vazirani Chapter 14, 12. Exercises Reading Completed proof for f-approximation. 1/2 integrality of vertex cover. Introduced the notion of a dual.References: Vazirani Chapter 14, 12. Proof of Weak duality. Dual fitting applied to Set cover to get an H_n approximation. References Vazirani Chapter 13. Exercises Reading Proof of Weak duality. Dual fitting applied to Set cover to get an H_n approximation.References: Vazirani Chapter 13. Constrained Multicover -- greedy algorithm and analysis using Dual Fitting. References Vazirani Chapter 13. Exercises Reading Constrained Multicover -- greedy algorithm and analysis using Dual Fitting.References: Vazirani Chapter 13. Vertex cover structure and nemhauser trotter theorem References section 3.7 of Approximating covering and packing problems. Book by Dorit Hochbaum Exercises Reading Section 3.7.1 of Hochbaum Vertex cover structure and nemhauser trotter theoremReferences: section 3.7 of Approximating covering and packing problems. Book by Dorit Hochbaum Reading: Section 3.7.1 of Hochbaum Why NT theorem does not give P time algorithms for Vertex cover!!! Odd cycles, for which all 1/2 is hte only optimum. How to prove this? Use the half integrality of the VC polytope. Combinatorial structure of half integral solutioons. The vertices that are 0 are an independent set, their neighbours are 1. Testing if there is a half integral optimum in not all values are 1/2. References Chapter 6 of book titled Matching Theory by lovasz and plummer Exercises Reading The sections of lovasz and plummer on 2 matchings and 2 covers. Why NT theorem does not give P time algorithms for Vertex cover!!! Odd cycles, for which all 1/2 is hte only optimum. How to prove this? Use the half integrality of the VC polytope. Combinatorial structure of half integral solutioons. The vertices that are 0 are an independent set, their neighbours are 1. Testing if there is a half integral optimum in not all values are 1/2.References: Chapter 6 of book titled Matching Theory by lovasz and plummer Reading: The sections of lovasz and plummer on 2 matchings and 2 covers. No class. References Exercises Reading No class.References: None Further application of deterministic rounding: Prize collecting Steiner tree. An LP with exponentially many constraints. Separation oracle using max-flow. References Section 4.4 Shmoys and Williamson. Exercises Reading Further application of deterministic rounding: Prize collecting Steiner tree. An LP with exponentially many constraints. Separation oracle using max-flow.References: Section 4.4 Shmoys and Williamson. Prize collecting Steiner tree continued. A 3 factor approximation. MAX-CUT and MAX-E3-SAT definitions. References Exercises Reading Prize collecting Steiner tree continued. A 3 factor approximation. MAX-CUT and MAX-E3-SAT definitions.References: None Set up the following experiment for MAX-SAT -- choose a setting of variables uniformly at random from the space of all possible settings. Compute the expectation. Similarly for MAX-CUT place each vertex v into one of th partitions uniformly at random and compute expectations. Gives a 1/2 approximation randomized algorithm for both. References Section 5.1 Shmoys and Williamson. Exercises Reading Set up the following experiment for MAX-SAT -- choose a setting of variables uniformly at random from the space of all possible settings. Compute the expectation. Similarly for MAX-CUT place each vertex v into one of th partitions uniformly at random and compute expectations. Gives a 1/2 approximation randomized algorithm for both.References: Section 5.1 Shmoys and Williamson. Method of conditional expectations for MAX-SAT. Alternative view is to think of it as derandomizing the randomized algorithm studied in previous class. <br> Flipping biased coins for MAX-SAT. An improved randomized algorithm for MAX-SAT by setting p > 1/2. But still we have the same probability for each variable. <br> Now we choose a different probability for each variable. Randomized rounding for MAX-SAT. Gives a (1 -1/e) factor approximation for MAX-SAT. References Sections 5.2--5.4 Shmoys and Williamson. Exercises Reading Method of conditional expectations for MAX-SAT. Alternative view is to think of it as derandomizing the randomized algorithm studied in previous class.

Flipping biased coins for MAX-SAT. An improved randomized algorithm for MAX-SAT by setting p > 1/2. But still we have the same probability for each variable.

Now we choose a different probability for each variable. Randomized rounding for MAX-SAT. Gives a (1 -1/e) factor approximation for MAX-SAT.References: Sections 5.2--5.4 Shmoys and Williamson. Prize Collecting Steiner tree revisited. A randomized rounding algorithm which yields a 2.54 factor approximation. References Section 5.7 Shmoys and Williamson. Exercises Reading Prize Collecting Steiner tree revisited. A randomized rounding algorithm which yields a 2.54 factor approximation.References: Section 5.7 Shmoys and Williamson. Markov Inequality and Chernoff Bounds. References Section 5.10 Shmoys and Williamson. Exercises Reading Markov Inequality and Chernoff Bounds.References: Section 5.10 Shmoys and Williamson. No class. References Exercises Reading No class.References: None Application of Chernoff Bound for Randomized rounding of Integer Multicommodity flow. References Section 5.11 Shmoys and Williamson. Exercises Reading Application of Chernoff Bound for Randomized rounding of Integer Multicommodity flow.References: Section 5.11 Shmoys and Williamson. Coloring 3-colorable Dense graphs. <br> Summary of different methods seen till now: (1) Threshold based rounding, (2) Randomized Rounding. Deviation bound -- need a stronger bound than obtained by Markov's inequality; a possible way is to use Chernoff bounds. <br> Discussion on Strong Duality and Complementary Slackness conditions. References Section 5.12 Shmoys and Williamson. <br> Appendix A of Shmoys and Williamson for Strong duality and complementary slackness. Exercises Reading Coloring 3-colorable Dense graphs.

Summary of different methods seen till now: (1) Threshold based rounding, (2) Randomized Rounding. Deviation bound -- need a stronger bound than obtained by Markov's inequality; a possible way is to use Chernoff bounds.

Discussion on Strong Duality and Complementary Slackness conditions.References: Section 5.12 Shmoys and Williamson.

Appendix A of Shmoys and Williamson for Strong duality and complementary slackness.Semidefinite Programming. Using SDP as a blackbox an algorithm for Max-cut. References Section 6.2 Shmoys and Williamson. Exercises Reading Semidefinite Programming. Using SDP as a blackbox an algorithm for Max-cut.References: Section 6.2 Shmoys and Williamson. Introduction to Semindefinite Programming. Properties of positive semidefinite matrices in terms of eigen values. <br> Discussion on how the ellipsoid method can be used to solve semidefinite programs in polynomial time. References Section 6.1 Shmoys and Williamson. Exercises Reading Introduction to Semindefinite Programming. Properties of positive semidefinite matrices in terms of eigen values.

Discussion on how the ellipsoid method can be used to solve semidefinite programs in polynomial time.References: Section 6.1 Shmoys and Williamson. References Exercises Reading References: None Coloring 3-colorable graphs. A simple sqrt{n} algorithm by Widgerson -- using the 2 facts (a) for a 3-colorable graph neighbourhood of any vertex is 2 colorable and (b) any graph can be properly colored using delta+1 colors where delta is the maximum degree. <br> Use of semidefinite programs to color it in n^0.387 colors. References Section 6.5 Shmoys and Williamson. Exercises Reading Coloring 3-colorable graphs. A simple sqrt{n} algorithm by Widgerson -- using the 2 facts (a) for a 3-colorable graph neighbourhood of any vertex is 2 colorable and (b) any graph can be properly colored using delta+1 colors where delta is the maximum degree.

Use of semidefinite programs to color it in n^0.387 colors.References: Section 6.5 Shmoys and Williamson. No Class. References Exercises Reading No Class.References: None 3-coloring via SDP continued. References Section 6.5 Shmoys and Williamson. Exercises Reading 3-coloring via SDP continued.References: Section 6.5 Shmoys and Williamson. Introduction to Primal Dual Method. Shortest s-t path via primal dual method. References Section 7.3 Shmoys and Williamson. Exercises Reading Introduction to Primal Dual Method. Shortest s-t path via primal dual method.References: Section 7.3 Shmoys and Williamson. Discussion on shortest s-t paths continued. Set cover via primal dual method -- gives an f-approximation. The choice of dual variable to be increased in set cover is a easy choice. References Section 7.1 Shmoys and Williamson. Exercises Reading Discussion on shortest s-t paths continued. Set cover via primal dual method -- gives an f-approximation. The choice of dual variable to be increased in set cover is a easy choice.References: Section 7.1 Shmoys and Williamson. Feedback Vertex Set via primal dual method. The choice of which dual variable to increase needs to be carefully done. A 4 log(n) approximation for Feedback vertex Set. References Section 7.2 Shmoys and Williamson. Exercises Reading Feedback Vertex Set via primal dual method. The choice of which dual variable to increase needs to be carefully done. A 4 log(n) approximation for Feedback vertex Set.References: Section 7.2 Shmoys and Williamson. Guarding a set of Line Segments. References Will be provided. Exercises Reading Guarding a set of Line Segments.References: Will be provided. No Class -- Ugadi. References Exercises Reading No Class -- Ugadi.References: None To Be Announced References Exercises Reading To Be AnnouncedReferences: None To Be Announced References Exercises Reading To Be AnnouncedReferences: None To Be Announced References Exercises Reading To Be AnnouncedReferences: None To Be Announced References Exercises Reading To Be AnnouncedReferences: None 3-coloring via SDP continued. References Section 6.5 Shmoys and Williamson. Exercises Reading 3-coloring via SDP continued.References: Section 6.5 Shmoys and Williamson. To Be Announced References Exercises Reading To Be AnnouncedReferences: None To Be Announced References Exercises Reading To Be AnnouncedReferences: None To Be Announced References Exercises Reading To Be AnnouncedReferences: None To Be Announced References Exercises Reading To Be AnnouncedReferences: None To Be Announced References Exercises Reading To Be AnnouncedReferences: None To Be Announced References Exercises Reading To Be AnnouncedReferences: None To Be Announced References Exercises Reading To Be AnnouncedReferences: None To Be Announced References Exercises Reading To Be AnnouncedReferences: None To Be Announced References Exercises Reading To Be AnnouncedReferences: None To Be Announced References Exercises Reading To Be AnnouncedReferences: None To Be Announced References Exercises Reading To Be AnnouncedReferences: None **Theme 4 : Algorithms for Matchings.**- 7 meetings- Meeting 60 : Tue, Apr 01, 08:00 am-08:50 am
- Meeting 61 : Wed, Apr 02, 12:00 pm-12:50 pm
- Meeting 62 : Fri, Apr 04, 11:00 am-11:50 am
- Meeting 63 : Mon, Apr 07, 09:00 am-09:50 am
- Meeting 64 : Tue, Apr 08, 08:00 am-08:50 am
- Meeting 65 : Wed, Apr 09, 06:00 am-06:00 am
- Meeting 66 : Fri, Apr 11, 11:00 am-11:50 am

Matchings revisited, augmenting paths, alternating paths, Berge's theorem. Hopcroft Karp algorithm for bipartite matchings. References Papadimitriou and Stieglitz, Chapter 10, Algorithms for Matchings. Hopcroft Karp's Paper on Bipartite Matching (SIAM Journal of Computing, 1973). You can find the paper locally at: http://www.cse.iitm.ac.in/~meghana/matchings/Hopcroft-Karp-bipartite-matching.pdf Exercises Reading Matchings revisited, augmenting paths, alternating paths, Berge's theorem. Hopcroft Karp algorithm for bipartite matchings.References: Papadimitriou and Stieglitz, Chapter 10, Algorithms for Matchings. Hopcroft Karp's Paper on Bipartite Matching (SIAM Journal of Computing, 1973). You can find the paper locally at: http://www.cse.iitm.ac.in/~meghana/matchings/Hopcroft-Karp-bipartite-matching.pdf Completed the Hopcroft Karp algorithm and its analysis. Weighted Bipartite Matching -- primal dual method. References You can refer to the following notes for the weighted matching by M. Goemans here: www.cse.iitm.ac.in/~meghana/matchings/matching-notes-Goemans.pdf The presentation in Papadimitriou and Stieglitz is a little different from what we will cover in the class. Exercises Reading Completed the Hopcroft Karp algorithm and its analysis. Weighted Bipartite Matching -- primal dual method.References: You can refer to the following notes for the weighted matching by M. Goemans here: www.cse.iitm.ac.in/~meghana/matchings/matching-notes-Goemans.pdf The presentation in Papadimitriou and Stieglitz is a little different from what we will cover in the class. Weighted bipartite matching continued. Konigs theorem and its application to changing the dual variables appropriately. An O(n^4) algorithm for computing weighted perfect bipartite matching. References Same as previous lecture. Exercises Reading Weighted bipartite matching continued. Konigs theorem and its application to changing the dual variables appropriately. An O(n^4) algorithm for computing weighted perfect bipartite matching.References: Same as previous lecture. Non-bipartite maximum cardinality matching -- Edmond's algorithm. Need to define blossoms; definition of a blosoom and the shrinking operation. References Papadimitriou and Steiglitz Chapter 10. Exercises Reading Non-bipartite maximum cardinality matching -- Edmond's algorithm. Need to define blossoms; definition of a blosoom and the shrinking operation.References: Papadimitriou and Steiglitz Chapter 10. To Be Announced References Exercises Reading To Be AnnouncedReferences: None Tutorial class. Primal Dual method examples. Max-weight matching in bipartite graphs. References Exercises Reading Tutorial class. Primal Dual method examples. Max-weight matching in bipartite graphs.References: None Gallai Edmonds Decomposition theorem for Bipartite graphs. An application of the theorem to popular matchings. References See Paper: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.72.8202&rep=rep1&type=pdf Lemma 3.2 and its Proof. Exercises Reading Gallai Edmonds Decomposition theorem for Bipartite graphs. An application of the theorem to popular matchings.References: See Paper: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.72.8202&rep=rep1&type=pdf Lemma 3.2 and its Proof.