CS6100 - Topics in Design and Analysis of Algorithms

Meetings  

• Theme 1 : Flows and Cuts - 12 meetings

  • Meeting 01 : Mon, Jan 15, 11:00 am-11:50 am

  Course Outline, Admin Announcements, TA introductionm Grading Policy.

  References
  Exercises
  Reading

  Course Outline, Admin Announcements, TA introductionm Grading Policy.
  

  References:

  None

  • Meeting 02 : Tue, Jan 16, 10:00 am-10:50 am

  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.

  • Meeting 03 : Wed, Jan 17, 09:00 am-09:50 am

  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.

  • Meeting 04 : Thu, Jan 18, 12:00 pm-12:50 pm

  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.

  • Meeting 05 : Mon, Jan 22, 11:00 am-11:50 am

  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.

  • Meeting 06 : Tue, Jan 23, 10:00 am-10:50 am

  No Class. Friday Timetable.

  References
  Exercises
  Reading

  No Class. Friday Timetable.
  

  References:

  None

  • Meeting 07 : Wed, Jan 24, 09:00 am-09:50 am

  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.

  • Meeting 08 : Thu, Jan 25, 12:00 pm-12:50 pm

  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.

  • Meeting 09 : Mon, Jan 29, 11:00 am-11:50 am

  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

  • Meeting 10 : Tue, Jan 30, 10:00 am-10:50 am

  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.

  • Meeting 11 : Wed, Jan 31, 09:00 am-09:50 am

  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.

  • Meeting 12 : Thu, Feb 01, 12:00 pm-12:50 pm

  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

  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

  • Meeting 14 : Tue, Apr 03, 10:00 am-10:50 am

  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

  • Meeting 15 : Wed, Apr 04, 09:00 am-09:50 am

  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.

  • Meeting 16 : Thu, Apr 05, 12:00 pm-12:50 pm

  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

  • Meeting 17 : Mon, Apr 09, 11:00 am-11:50 am

  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

  • Meeting 18 : Tue, Apr 10, 10:00 am-10:50 am

  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

  • Meeting 19 : Wed, Apr 11, 09:00 am-09:50 am

  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

  • Meeting 20 : Thu, Apr 12, 12:00 pm-12:50 pm

  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

  • Meeting 21 : Mon, Apr 16, 11:00 am-11:50 am

  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

  • Meeting 22 : Tue, Apr 17, 10:00 am-10:50 am

  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

  • Meeting 23 : Wed, Apr 18, 09:00 am-09:50 am

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

• Theme 3 : Matchings in Graphs - 19 meetings

  • Meeting 24 : Mon, Feb 05, 11:00 am-11:50 am

  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

  • Meeting 25 : Tue, Feb 06, 10:00 am-10:50 am

  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.

  • Meeting 26 : Wed, Feb 07, 09:00 am-09:50 am

  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.

  • Meeting 27 : Mon, Feb 12, 11:00 am-11:50 am

  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.

  • Meeting 28 : Tue, Feb 13, 10:00 am-10:50 am

  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.

  • Meeting 29 : Wed, Feb 14, 09:00 am-09:50 am

  No class (Holiday).

  References
  Exercises
  Reading

  No class (Holiday).
  

  References:

  None

  • Meeting 30 : Thu, Feb 15, 12:00 pm-12:50 pm

  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

  • Meeting 31 : Mon, Feb 19, 11:00 am-11:50 am

  Proof of Dulmage Mendelsohn decomposition theorem continued.

  References
  Exercises
  Reading

  Proof of Dulmage Mendelsohn decomposition theorem continued.
  

  References:

  None

  • Meeting 32 : Tue, Feb 20, 10:00 am-10:50 am

  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).

  • Meeting 33 : Wed, Feb 21, 09:00 am-09:50 am

  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

  • Meeting 34 : Thu, Feb 22, 12:00 pm-12:50 pm

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • Meeting 35 : Mon, Feb 26, 11:00 am-11:50 am

  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

  • Meeting 36 : Tue, Feb 27, 10:00 am-10:50 am

  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

  • Meeting 37 : Wed, Feb 28, 09:00 am-09:50 am

  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

  • Meeting 38 : Thu, Mar 01, 12:00 pm-12:50 pm

  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

  • Meeting 39 : Mon, Mar 05, 11:00 am-11:50 am

  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

  • Meeting 40 : Tue, Mar 06, 10:00 am-10:50 am

  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

  • Meeting 41 : Wed, Mar 07, 09:00 am-09:50 am

  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

  • Meeting 42 : Thu, Mar 08, 12:00 pm-12:50 pm

  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

  In class test 1.

  References
  Exercises
  Reading

  In class test 1.
  

  References:

  None

  • Meeting 44 : Thu, Mar 22, 12:00 pm-12:50 pm

  In class Test 2

  References
  Exercises
  Reading

  In class Test 2
  

  References:

  None

  • Meeting 45 : Thu, Apr 19, 12:00 pm-12:50 pm

  In Class test 3

  References
  Exercises
  Reading

  In Class test 3
  

  References:

  None

• Theme 5 : Matching in Markets - 11 meetings

  • Meeting 46 : Mon, Mar 12, 11:00 am-11:50 am

  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

  • Meeting 47 : Tue, Mar 13, 10:00 am-10:50 am

  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

  • Meeting 48 : Wed, Mar 14, 09:00 am-09:50 am

  Popular Matchings with Ties continued.

  References
  Exercises
  Reading

  Popular Matchings with Ties continued.
  

  References:

  None

  • Meeting 49 : Thu, Mar 15, 12:00 pm-12:50 pm

  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

  • Meeting 50 : Mon, Mar 19, 11:00 am-11:50 am

  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.

  • Meeting 51 : Tue, Mar 20, 10:00 am-10:50 am

  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

  • Meeting 52 : Wed, Mar 21, 09:00 am-09:50 am

  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

  • Meeting 53 : Mon, Mar 26, 11:00 am-11:50 am

  No Class -- Friday Time table.

  References
  Exercises
  Reading

  No Class -- Friday Time table.
  

  References:

  None

  • Meeting 54 : Tue, Mar 27, 10:00 am-10:50 am

  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

  • Meeting 55 : Wed, Mar 28, 09:00 am-09:50 am

  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.

  • Meeting 56 : Thu, Mar 29, 12:00 pm-12:50 pm

  No Class -- Institute Holiday.

  References
  Exercises
  Reading

  No Class -- Institute Holiday.
  

  References:

  None