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 : Flows and Cuts**- 12 meetings- Meeting 01 : Mon, Jan 15, 11:00 am-11:50 am
- Meeting 02 : Tue, Jan 16, 10:00 am-10:50 am
- Meeting 03 : Wed, Jan 17, 09:00 am-09:50 am
- Meeting 04 : Thu, Jan 18, 12:00 pm-12:50 pm
- Meeting 05 : Mon, Jan 22, 11:00 am-11:50 am
- Meeting 06 : Tue, Jan 23, 10:00 am-10:50 am
- Meeting 07 : Wed, Jan 24, 09:00 am-09:50 am
- Meeting 08 : Thu, Jan 25, 12:00 pm-12:50 pm
- Meeting 09 : Mon, Jan 29, 11:00 am-11:50 am
- Meeting 10 : Tue, Jan 30, 10:00 am-10:50 am
- Meeting 11 : Wed, Jan 31, 09:00 am-09:50 am
- Meeting 12 : Thu, Feb 01, 12:00 pm-12:50 pm

Course Outline, Admin Announcements, TA introductionm Grading Policy. References Exercises Reading Course Outline, Admin Announcements, TA introductionm Grading Policy.References: None Network Flow Problem, Inputs and Output, Edge disjoint Paths problem in a directed graph. Reduction to network flows. Correctness Proof. References Kleinberg and Tardos Chapter 7. Exercises Reading Network Flow Problem, Inputs and Output, Edge disjoint Paths problem in a directed graph. Reduction to network flows. Correctness Proof.References: Kleinberg and Tardos Chapter 7. Edge disjoint paths problem in undirected case. What if flow uses both (u, v) and (v, u) in the directed case? <br> Flows and Cuts, Capacity of a cut, relation to flow. Max-Flow min cut theorem statement (without proof). <br> Flow with demands on vertices. References Kleinberg and Tardos. Exercises Reading Edge disjoint paths problem in undirected case. What if flow uses both (u, v) and (v, u) in the directed case?

Flows and Cuts, Capacity of a cut, relation to flow. Max-Flow min cut theorem statement (without proof).

Flow with demands on vertices.References: Kleinberg and Tardos. Network flow with demands on vertices to Network flow problem. <br> Network flow with lower bounds on edges to network flow with demands on vertices. <br> Reduction and proofs. References Kleinberg and Tardos Chapter 7. Exercises Reading Network flow with demands on vertices to Network flow problem.

Network flow with lower bounds on edges to network flow with demands on vertices.

Reduction and proofs.References: Kleinberg and Tardos Chapter 7. Flow algorithms. Ford Fulkerson Method. A quick recap. Notion of residual network. <br> Cuts and net flow across a cut. References CLRS Chapter 26. Exercises Reading Flow algorithms. Ford Fulkerson Method. A quick recap. Notion of residual network.

Cuts and net flow across a cut.References: CLRS Chapter 26. No Class. Friday Timetable. References Exercises Reading No Class. Friday Timetable.References: None Max-Flow min-cut theorem. Correctness of Ford Fulkerson Method. Analysis of Running time. <br> Brief introduction to Push Relabel algorithm. References CLRS Chapter 26. Exercises Reading Max-Flow min-cut theorem. Correctness of Ford Fulkerson Method. Analysis of Running time.

Brief introduction to Push Relabel algorithm.References: CLRS Chapter 26. Push Relabel algorithm. <br> The height function, excess of a vertex, invariants. Arguing that Push and Relabel maintain the invariants. <br> Saturating versus non saturating pushes. Properties. <br> Maximum height that a vertex can reach during the algorithm. Bound on number of relabel operations. <br> References CLRS Chapter 26. Exercises Reading Push Relabel algorithm.

The height function, excess of a vertex, invariants. Arguing that Push and Relabel maintain the invariants.

Saturating versus non saturating pushes. Properties.

Maximum height that a vertex can reach during the algorithm. Bound on number of relabel operations.References: CLRS Chapter 26. Preflow - push algorithm continued. Bound on number of saturating pushes and non-saturating pushes. A small modification to the algorithm which picks a vertex at max-height. Proof of the fact that every vertex which has excess(x) > 0 has a path to s in the residual network. Why is the flow a max-flow at termination. References CLRS Chapter 26, Kleinberg and Tardos (for the modified algorithm). Also see very nice lecture notes here: http://www.cse.iitm.ac.in/~meghana/CS6100/ref/Push-Relabel-Roughgarden.pdf Exercises Reading Preflow - push algorithm continued. Bound on number of saturating pushes and non-saturating pushes. A small modification to the algorithm which picks a vertex at max-height. Proof of the fact that every vertex which has excess(x) > 0 has a path to s in the residual network. Why is the flow a max-flow at termination.References: CLRS Chapter 26, Kleinberg and Tardos (for the modified algorithm). Also see very nice lecture notes here: http://www.cse.iitm.ac.in/~meghana/CS6100/ref/Push-Relabel-Roughgarden.pdf Discussion on implementing an efficient preflow push algorithm. Need to maintain a list of vertices at every height. Efficiently select the edge along which push needs to be applied. Cuts in graphs. Undirected versus directed Cut. Global min-cut versus s-t cut. Computing a global min-cut using O(n) calls to a flow algorithm. <br> A completely different approach -- contraction based algorithm by David Karger. Basics of contraction, relation between min-cut value and minimum degree of a graph. Sampling edges Uniformly at Random. References Kleinberg and Tardos for data structures for preflow push. <br> Motwani Raghavan (Randomized Algorithms) for Kargers min-cut algorithm. Chapter 1 and Chapter 10. Exercises Reading Discussion on implementing an efficient preflow push algorithm. Need to maintain a list of vertices at every height. Efficiently select the edge along which push needs to be applied. Cuts in graphs. Undirected versus directed Cut. Global min-cut versus s-t cut. Computing a global min-cut using O(n) calls to a flow algorithm.

A completely different approach -- contraction based algorithm by David Karger. Basics of contraction, relation between min-cut value and minimum degree of a graph. Sampling edges Uniformly at Random.References: Kleinberg and Tardos for data structures for preflow push.

Motwani Raghavan (Randomized Algorithms) for Kargers min-cut algorithm. Chapter 1 and Chapter 10.Karger's algorithm continued. Analysis of a simple min-cut algorithm that runs in O(n^2) time and returns a min-cut with probability 2/n^2. Boosting to improve probability of success. <br> Discussion on number of global min-cuts in a graph. Examples of tree and cycle graphs. What is the largest number of min-cuts in any graph? References Motwani and Raghavan Chapter 10. Exercises Reading Karger's algorithm continued. Analysis of a simple min-cut algorithm that runs in O(n^2) time and returns a min-cut with probability 2/n^2. Boosting to improve probability of success.

Discussion on number of global min-cuts in a graph. Examples of tree and cycle graphs. What is the largest number of min-cuts in any graph?References: Motwani and Raghavan Chapter 10. Issues with Simple Min-Cut algorithm. Goal is to reuse the parts of the executions. Motivation for recursive algorithm. A recursive Fast-MinCut algorithm. Analysis of running time and derivation of recursive formula for probability of success. References Motwani and Raghavan Chapter 10. Exercises Reading Issues with Simple Min-Cut algorithm. Goal is to reuse the parts of the executions. Motivation for recursive algorithm. A recursive Fast-MinCut algorithm. Analysis of running time and derivation of recursive formula for probability of success.References: Motwani and Raghavan Chapter 10. **Theme 2 : Dynamic Graph Algorithms**- 11 meetings- Meeting 13 : Mon, Apr 02, 11:00 am-11:50 am
- Meeting 14 : Tue, Apr 03, 10:00 am-10:50 am
- Meeting 15 : Wed, Apr 04, 09:00 am-09:50 am
- Meeting 16 : Thu, Apr 05, 12:00 pm-12:50 pm
- Meeting 17 : Mon, Apr 09, 11:00 am-11:50 am
- Meeting 18 : Tue, Apr 10, 10:00 am-10:50 am
- Meeting 19 : Wed, Apr 11, 09:00 am-09:50 am
- Meeting 20 : Thu, Apr 12, 12:00 pm-12:50 pm
- Meeting 21 : Mon, Apr 16, 11:00 am-11:50 am
- Meeting 22 : Tue, Apr 17, 10:00 am-10:50 am
- Meeting 23 : Wed, Apr 18, 09:00 am-09:50 am

Introduction to the dynamic model. Update time, query time. Tradeoff. <br> First problem -- Dynamic connectivity in graphs. Need to support edge additions and deletions on trees. Maintaining Dynamic forests. References Exercises Reading Introduction to the dynamic model. Update time, query time. Tradeoff.

First problem -- Dynamic connectivity in graphs. Need to support edge additions and deletions on trees. Maintaining Dynamic forests.References: None Euler Tour trees -- data structure for dynamic connectivity in forests. <br> Updates : insert, delete, reroot a tree. Query: isconnected. Supported in O(log(n)) time. References See these lecture slides. Watch out for minor typos in reroot procedure. web.stanford.edu/class/archive/cs/cs166/cs166.1166/lectures/17/Small17.pdf Exercises Reading Euler Tour trees -- data structure for dynamic connectivity in forests.

Updates : insert, delete, reroot a tree. Query: isconnected. Supported in O(log(n)) time.References: See these lecture slides. Watch out for minor typos in reroot procedure. web.stanford.edu/class/archive/cs/cs166/cs166.1166/lectures/17/Small17.pdf Dynamic Connectivity in Graphs. Maintaining a hierarchical collection of forests. Insert and delete supported in O(log(n)) amortized updated time. Is connected supported in O(log(n)) worst case update time. References Paper by Holm et al. https://people.csail.mit.edu/jshun/6886-s18/papers/Holm2001.pdf Section 2.1 of the paper for ET trees. <br> Section 3 of the paper for Fully dynamic connectivity. Exercises Reading Dynamic Connectivity in Graphs. Maintaining a hierarchical collection of forests. Insert and delete supported in O(log(n)) amortized updated time. Is connected supported in O(log(n)) worst case update time.References: Paper by Holm et al. https://people.csail.mit.edu/jshun/6886-s18/papers/Holm2001.pdf Section 2.1 of the paper for ET trees.

Section 3 of the paper for Fully dynamic connectivity.Towards Dynamic All Pairs Shortest Paths (APSP). A static algorithm for computing APSP -- Hidden Paths Algorithm. Introduction to the parameter m* which is upper bounded by m (number of edges). <br> Algorithm and proof of correctness of algorithm. References Paper by Karger et al: https://epubs.siam.org/doi/abs/10.1137/0222071 Exercises Reading Towards Dynamic All Pairs Shortest Paths (APSP). A static algorithm for computing APSP -- Hidden Paths Algorithm. Introduction to the parameter m* which is upper bounded by m (number of edges).

Algorithm and proof of correctness of algorithm.References: Paper by Karger et al: https://epubs.siam.org/doi/abs/10.1137/0222071 Dynamic All pairs shortest paths, some context and simple case of incremental APSP. <br> Difficulty with the decremental updates. Definition of Locally shortest paths and properties. References Paper by Demetrescu and Italiano. https://dl.acm.org/citation.cfm?id=1039492 Exercises Reading Dynamic All pairs shortest paths, some context and simple case of incremental APSP.

Difficulty with the decremental updates. Definition of Locally shortest paths and properties.References: Paper by Demetrescu and Italiano. https://dl.acm.org/citation.cfm?id=1039492 Locally Shortest paths and properties. Paths that stop being locally shortest and that start being locally shortest. Counting the number of such paths under a unique shortest paths assumption. References https://dl.acm.org/citation.cfm?id=1039492 Exercises Reading Locally Shortest paths and properties. Paths that stop being locally shortest and that start being locally shortest. Counting the number of such paths under a unique shortest paths assumption.References: https://dl.acm.org/citation.cfm?id=1039492 The decremental update algorithm and data structures. The algorithm for cleanup, correctness and running time. References https://dl.acm.org/citation.cfm?id=1039492 Exercises Reading The decremental update algorithm and data structures. The algorithm for cleanup, correctness and running time.References: https://dl.acm.org/citation.cfm?id=1039492 The update algorithm continued. The need for additional data structures (shortest extension sets). The fixup algorithm, running time and correctness. References https://dl.acm.org/citation.cfm?id=1039492 Exercises Reading The update algorithm continued. The need for additional data structures (shortest extension sets). The fixup algorithm, running time and correctness.References: https://dl.acm.org/citation.cfm?id=1039492 Dynamic Matchings in graphs. Motivation, a simple O(Delta) algorithm for maintaining a maximal matching and a matching without 3 length augmenting path. References Exercises Reading Dynamic Matchings in graphs. Motivation, a simple O(Delta) algorithm for maintaining a maximal matching and a matching without 3 length augmenting path.References: None Fully dynamic deterministic matchings without 1 length and 3 length aug. paths in O(sqrt(m+n)) time. Idea of maintaining high degree vertices matched. Algorithm for additions and deletions. References Paper by Neiman and Solomon: https://arxiv.org/abs/1207.1277 Exercises Reading Fully dynamic deterministic matchings without 1 length and 3 length aug. paths in O(sqrt(m+n)) time. Idea of maintaining high degree vertices matched. Algorithm for additions and deletions.References: Paper by Neiman and Solomon: https://arxiv.org/abs/1207.1277 To Be Announced References Exercises Reading To Be AnnouncedReferences: None **Theme 3 : Matchings in Graphs**- 19 meetings- Meeting 24 : Mon, Feb 05, 11:00 am-11:50 am
- Meeting 25 : Tue, Feb 06, 10:00 am-10:50 am
- Meeting 26 : Wed, Feb 07, 09:00 am-09:50 am
- Meeting 27 : Mon, Feb 12, 11:00 am-11:50 am
- Meeting 28 : Tue, Feb 13, 10:00 am-10:50 am
- Meeting 29 : Wed, Feb 14, 09:00 am-09:50 am
- Meeting 30 : Thu, Feb 15, 12:00 pm-12:50 pm
- Meeting 31 : Mon, Feb 19, 11:00 am-11:50 am
- Meeting 32 : Tue, Feb 20, 10:00 am-10:50 am
- Meeting 33 : Wed, Feb 21, 09:00 am-09:50 am
- Meeting 34 : Thu, Feb 22, 12:00 pm-12:50 pm
- Meeting 35 : Mon, Feb 26, 11:00 am-11:50 am
- Meeting 36 : Tue, Feb 27, 10:00 am-10:50 am
- Meeting 37 : Wed, Feb 28, 09:00 am-09:50 am
- Meeting 38 : Thu, Mar 01, 12:00 pm-12:50 pm
- Meeting 39 : Mon, Mar 05, 11:00 am-11:50 am
- Meeting 40 : Tue, Mar 06, 10:00 am-10:50 am
- Meeting 41 : Wed, Mar 07, 09:00 am-09:50 am
- Meeting 42 : Thu, Mar 08, 12:00 pm-12:50 pm

Matchings -- review of basic definitions, maximal versus maximum matching, alternating paths, augmenting paths, size of maximum matching versus size of maximal matching. <br> The process of "augmentation". Symmetric difference between a Matching and an augmenting path. <br> Symmetric Difference of two matchings. A template algorithm for computing a maximum matching. Correctness of the template algorithm. Berge's theorem and its proof. <br> References http://math.mit.edu/~goemans/18453S17/matching-notes.pdf Exercises Reading Matchings -- review of basic definitions, maximal versus maximum matching, alternating paths, augmenting paths, size of maximum matching versus size of maximal matching.

The process of "augmentation". Symmetric difference between a Matching and an augmenting path.

Symmetric Difference of two matchings. A template algorithm for computing a maximum matching. Correctness of the template algorithm. Berge's theorem and its proof.References: http://math.mit.edu/~goemans/18453S17/matching-notes.pdf Matchings without short augmenting paths. Maximal matching size versus maximum matching size. <br> If a matching does not admit upto 2k-1 length aug. paths, then it is (k/k+1) approximate. Proof of the lemma. References Will be uploaded soon. Exercises Reading Matchings without short augmenting paths. Maximal matching size versus maximum matching size.

If a matching does not admit upto 2k-1 length aug. paths, then it is (k/k+1) approximate. Proof of the lemma.References: Will be uploaded soon. Hopcroft Karp algorithm for bipartite maximum matching. Augmenting along a set of vertex disjoint paths. A collection of "maximal" vertex disjoint shortest paths. Computing this efficiently. Proof that this leads to a O(m sqrt{n}) algorithm. References http://www.cse.iitm.ac.in/~meghana/CS6100/ref/Hopcroft-Karp.pdf Exercises Reading Check out the chapter on matchings in DB West. Hopcroft Karp algorithm for bipartite maximum matching. Augmenting along a set of vertex disjoint paths. A collection of "maximal" vertex disjoint shortest paths. Computing this efficiently. Proof that this leads to a O(m sqrt{n}) algorithm.References: http://www.cse.iitm.ac.in/~meghana/CS6100/ref/Hopcroft-Karp.pdf Reading: Check out the chapter on matchings in DB West. Discussion of solutions for Inclass Test 1. <br> Three questions related to matchings in bipartite graphs. 1. Perfect matchings in bipartite graphs (statement of Halls theorem) 2. Vertex covers in bipartite graphs. 3. Can we identify edges that do not belong to any maximum matching in a bipartite graph? References For Q1. Halls theorem and its proof refer Kleinberg and Tardos. Exercises Reading Discussion of solutions for Inclass Test 1.

Three questions related to matchings in bipartite graphs. 1. Perfect matchings in bipartite graphs (statement of Halls theorem) 2. Vertex covers in bipartite graphs. 3. Can we identify edges that do not belong to any maximum matching in a bipartite graph?References: For Q1. Halls theorem and its proof refer Kleinberg and Tardos. Halls theorem statement and proof. Proof using max-flow min-cut theorem. As an exercise you are supposed to prove Konig's theorem (equality of min-VC size and max-matching size in a bipartite graph) using max-flow min-cut theorem. References Kleinberg and Tardos. Exercises Reading Halls theorem statement and proof. Proof using max-flow min-cut theorem. As an exercise you are supposed to prove Konig's theorem (equality of min-VC size and max-matching size in a bipartite graph) using max-flow min-cut theorem.References: Kleinberg and Tardos. No class (Holiday). References Exercises Reading No class (Holiday).References: None Motivation for the Dulmage Mendelsohn decomposition theorem. Examples and definition of Even / odd / unreachable vertices. Proof of Invariance of these sets w.r.t. a maximum matching. References http://www.cse.iitm.ac.in/~meghana/matchings/bip-decomp.pdf Exercises Reading Motivation for the Dulmage Mendelsohn decomposition theorem. Examples and definition of Even / odd / unreachable vertices. Proof of Invariance of these sets w.r.t. a maximum matching.References: http://www.cse.iitm.ac.in/~meghana/matchings/bip-decomp.pdf Proof of Dulmage Mendelsohn decomposition theorem continued. References Exercises Reading Proof of Dulmage Mendelsohn decomposition theorem continued.References: None Introduction to Linear Programs, writing LP for max-weight matching, motivation for dual. References See CLRS chapter on LPs. Presentation in class from Approximation algorithms book, by Vazirani (Chapter 12, initial parts). Exercises Reading Introduction to Linear Programs, writing LP for max-weight matching, motivation for dual.References: See CLRS chapter on LPs. Presentation in class from Approximation algorithms book, by Vazirani (Chapter 12, initial parts). Max-weight perfect matching in bipartite graphs. Dual, initializing a dual feasible solution. The overall algorithm. Definition of tight edges and equality subgraph. References https://webdocs.cs.ualberta.ca/~mreza/courses/CombOpt09/lecture4.pdf Exercises Reading Max-weight perfect matching in bipartite graphs. Dual, initializing a dual feasible solution. The overall algorithm. Definition of tight edges and equality subgraph.References: https://webdocs.cs.ualberta.ca/~mreza/courses/CombOpt09/lecture4.pdf To Be Announced References Exercises Reading To Be AnnouncedReferences: None Non-bipartite matching, difficulty with odd cycles, definition of a blossom, ways to avoid a blossom. Edmonds' idea of shrinking a blossom. References https://webdocs.cs.ualberta.ca/~mreza/courses/CombOpt09/lecture4.pdf Exercises Reading Non-bipartite matching, difficulty with odd cycles, definition of a blossom, ways to avoid a blossom. Edmonds' idea of shrinking a blossom.References: https://webdocs.cs.ualberta.ca/~mreza/courses/CombOpt09/lecture4.pdf Non-bipartite matchings continued, Proof of correctness of shrinking a blossom. <br> How many times do we need to "explore" an unmatched vertex? Proof that it suffices to explore it at most once. References https://webdocs.cs.ualberta.ca/~mreza/courses/CombOpt09/lecture4.pdf Exercises Reading Non-bipartite matchings continued, Proof of correctness of shrinking a blossom.

How many times do we need to "explore" an unmatched vertex? Proof that it suffices to explore it at most once.References: https://webdocs.cs.ualberta.ca/~mreza/courses/CombOpt09/lecture4.pdf Polynomial time algorithms and succinct proof of optimality of the solution. <br> Maximum matching in a bipartite graphs and same sized vertex cover. <br> Maximum flow in a flow network and an s-t cut of same capacity. <br> A desirable proof of optimality for non-bipartite matching. <br> Deficiency of any set. Relation to size of maximum matching. References http://www.cse.iitm.ac.in/~meghana/matchings/gen-matching-Notes.pdf Exercises Reading Polynomial time algorithms and succinct proof of optimality of the solution.

Maximum matching in a bipartite graphs and same sized vertex cover.

Maximum flow in a flow network and an s-t cut of same capacity.

A desirable proof of optimality for non-bipartite matching.

Deficiency of any set. Relation to size of maximum matching.References: http://www.cse.iitm.ac.in/~meghana/matchings/gen-matching-Notes.pdf Tutte's theorem statement. Proof. References http://www.cse.iitm.ac.in/~meghana/matchings/gen-matching-Notes.pdf Exercises Reading Tutte's theorem statement. Proof.References: http://www.cse.iitm.ac.in/~meghana/matchings/gen-matching-Notes.pdf Proof of Tutte's theorem continued. Tutte Berge Formula and its proof. References Exercises Reading Proof of Tutte's theorem continued. Tutte Berge Formula and its proof.References: None Towards Gallai Edmonds Decomposition Theorem. Definition of Even / Odd / Unreachable vertices. Invariance of the set Even w.r.t. max. matching. References Exercises Reading Towards Gallai Edmonds Decomposition Theorem. Definition of Even / Odd / Unreachable vertices. Invariance of the set Even w.r.t. max. matching.References: None Gallai Edmonds Decomposition theorem continued. The set of odd vertices as the witness Tuttess set. Decomposition of the graph when Odd vertices are removed. Structural properties with examples and proof. References Exercises Reading Gallai Edmonds Decomposition theorem continued. The set of odd vertices as the witness Tuttess set. Decomposition of the graph when Odd vertices are removed. Structural properties with examples and proof.References: None Gallai Edmonds Decomposition continued. <br> Application of GED. Matching in bipartite graph with Preferences. Notions of optimality. Popular matchings (see references). References epubs.siam.org/doi/pdf/10.1137/06067328X Exercises Reading Gallai Edmonds Decomposition continued.

Application of GED. Matching in bipartite graph with Preferences. Notions of optimality. Popular matchings (see references).References: epubs.siam.org/doi/pdf/10.1137/06067328X **Theme 4 : Evaluation meetings**- 3 meetings- Meeting 43 : Thu, Feb 08, 12:00 pm-12:50 pm
- Meeting 44 : Thu, Mar 22, 12:00 pm-12:50 pm
- Meeting 45 : Thu, Apr 19, 12:00 pm-12:50 pm

In class test 1. References Exercises Reading In class test 1.References: None In class Test 2 References Exercises Reading In class Test 2References: None In Class test 3 References Exercises Reading In Class test 3References: None **Theme 5 : Matching in Markets**- 11 meetings- Meeting 46 : Mon, Mar 12, 11:00 am-11:50 am
- Meeting 47 : Tue, Mar 13, 10:00 am-10:50 am
- Meeting 48 : Wed, Mar 14, 09:00 am-09:50 am
- Meeting 49 : Thu, Mar 15, 12:00 pm-12:50 pm
- Meeting 50 : Mon, Mar 19, 11:00 am-11:50 am
- Meeting 51 : Tue, Mar 20, 10:00 am-10:50 am
- Meeting 52 : Wed, Mar 21, 09:00 am-09:50 am
- Meeting 53 : Mon, Mar 26, 11:00 am-11:50 am
- Meeting 54 : Tue, Mar 27, 10:00 am-10:50 am
- Meeting 55 : Wed, Mar 28, 09:00 am-09:50 am
- Meeting 56 : Thu, Mar 29, 12:00 pm-12:50 pm

Popular Matchings (strict lists) -- a characterization and a polynomial time algorithm. References Exercises Reading Popular Matchings (strict lists) -- a characterization and a polynomial time algorithm.References: None Popular Matchings continued. Extension to case of ties. Application of Gallai Edmonds Decomposition. References Exercises Reading Popular Matchings continued. Extension to case of ties. Application of Gallai Edmonds Decomposition.References: None Popular Matchings with Ties continued. References Exercises Reading Popular Matchings with Ties continued.References: None Kidney Exchange Problem and Pairwise Kidney exchange -- a case study. Motivation and an algorithm for pairwise kidney exchange with priorities on vertices. References See Paper by Roth et al. https://web.stanford.edu/~alroth/papers/kidneys.JET.2005.pdf Exercises Reading Kidney Exchange Problem and Pairwise Kidney exchange -- a case study. Motivation and an algorithm for pairwise kidney exchange with priorities on vertices.References: See Paper by Roth et al. https://web.stanford.edu/~alroth/papers/kidneys.JET.2005.pdf Pairwise Kidney exchange continued. Using the Gallai Edmonds decomposition for an efficient algorithm. References See Paper: https://web.stanford.edu/~alroth/papers/kidneys.JET.2005.pdf Section 3.2 and onwards of the paper. Exercises Reading Pairwise Kidney exchange continued. Using the Gallai Edmonds decomposition for an efficient algorithm.References: See Paper: https://web.stanford.edu/~alroth/papers/kidneys.JET.2005.pdf Section 3.2 and onwards of the paper. Pairwise Kidney Exchange discussion on algorithm completed. <br> Stable Matching -- another example of a matching market, motivation and Gale and Shapley Algorithm. References Exercises Reading Pairwise Kidney Exchange discussion on algorithm completed.

Stable Matching -- another example of a matching market, motivation and Gale and Shapley Algorithm.References: None Proof of GS algorithm properties. The GS algorithm outputs a stable matching. The order of choice of a's to propose does not affect the output of the GS algorithm. References www.cse.iitm.ac.in/~meghana/public_html/stable.pdf Exercises Reading Proof of GS algorithm properties. The GS algorithm outputs a stable matching. The order of choice of a's to propose does not affect the output of the GS algorithm.References: www.cse.iitm.ac.in/~meghana/public_html/stable.pdf No Class -- Friday Time table. References Exercises Reading No Class -- Friday Time table.References: None More on properties of stable matchings. All stable matchings match the same set of a's and b's (even in instances where there are incomplete lists).<br> A stable matching is popular. References www.cse.iitm.ac.in/~meghana/stable.pdf Exercises Reading More on properties of stable matchings. All stable matchings match the same set of a's and b's (even in instances where there are incomplete lists).

A stable matching is popular.References: www.cse.iitm.ac.in/~meghana/stable.pdf Stable matchings with incomplete lists and ties. Stable matchings can be of different sizes. Computing max. cardinality stable matching is NP-Complete (statement w/o proof). <br> A 3/2 approximation algorithm for the case with ties on one side. References https://link.springer.com/article/10.1007/s00453-009-9371-7 Parts of Section 1 and Section 2 completely were covered in class. Exercises Reading Stable matchings with incomplete lists and ties. Stable matchings can be of different sizes. Computing max. cardinality stable matching is NP-Complete (statement w/o proof).

A 3/2 approximation algorithm for the case with ties on one side.References: https://link.springer.com/article/10.1007/s00453-009-9371-7 Parts of Section 1 and Section 2 completely were covered in class. No Class -- Institute Holiday. References Exercises Reading No Class -- Institute Holiday.References: None