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 : Classical Matchings. - 22 meetings

Meeting 01 : Tue, Jan 13, 11:00 am-11:50 am

To Be Announced

Meeting 02 : Wed, Jan 14, 10:00 am-10:50 am

Matchings, Alternating vs. Augmenting paths. Notion of augmentation. M oplus p, Berge's theorem. A template algorithm to compute a maximum cardinality matching.

Meeting 03 : Thu, Jan 15, 08:00 am-08:50 am

No Lecture. Pongal Holiday.

Meeting 04 : Fri, Jan 16, 02:00 pm-02:50 pm

Proof of Berge's theorem completed. Bipartite matchings, quick review of O(mn) algorithm. Hopcroft Karp algorithm overall idea.

Meeting 05 : Tue, Jan 20, 11:00 am-11:50 am

Hopcroft Karp continued. Idea of Layered Network and proof that the length of aug. path strictly increases over iterations.

Meeting 06 : Wed, Jan 21, 10:00 am-10:50 am

Completed proof of Hopcroft Karp. Non-bipartite matchings. Why does the simple approach fail? Notion of blossoms.

Meeting 07 : Thu, Jan 22, 08:00 am-08:50 am

Non bipartite max. cardinality matchings. Edmond's Blossom shrinking lemma with proof. Overall sketch of the algorithm without running time analysis.

Meeting 08 : Fri, Jan 23, 02:00 pm-02:50 pm

Problem solving session. Reductions and applications of maximum matchings to other problems.

Meeting 09 : Tue, Jan 27, 11:00 am-11:50 am

Weighted bipartite matching. Linear program, notion of a dual. Definition of equality subgraph.

Meeting 10 : Wed, Jan 28, 10:00 am-10:50 am

To Be Announced

Meeting 11 : Thu, Jan 29, 08:00 am-08:50 am

Primal Dual algorithm for min-weight matching in bipartite graphs. O(n^4) algorithm with analysis.

Meeting 12 : Fri, Jan 30, 02:00 pm-02:50 pm

Dulmage Mendelsohn Decomposition theorem.

Meeting 13 : Tue, Feb 03, 11:00 am-11:50 am

Perfect Matchings in O(n log n) time. Randomized Algorithm.

Meeting 14 : Wed, Feb 04, 10:00 am-10:50 am

Class canceled. Instructor out of town.

Meeting 15 : Thu, Feb 05, 08:00 am-08:50 am

Class canceled.

Meeting 16 : Fri, Feb 06, 02:00 pm-02:50 pm

Tutorial class.

Meeting 17 : Tue, Feb 10, 11:00 am-11:50 am

Perfect Matchings in regular bipartite graphs continued.

Meeting 18 : Wed, Feb 11, 10:00 am-10:50 am

Tutte's theorem, proof.

Meeting 19 : Thu, Feb 12, 08:00 am-08:50 am

Tutte's theorem Proof completed.

Meeting 20 : Fri, Feb 13, 02:00 pm-02:50 pm

Tutte Berge Formula.

Meeting 21 : Tue, Feb 17, 11:00 am-11:50 am

Gallai Edmonds Decomposition.

Meeting 22 : Fri, Feb 20, 02:00 pm-02:50 pm

Theme 2 : Matchings Under Preferences. - 16 meetings

Meeting 23 : Tue, Feb 24, 11:00 am-11:50 am

Introduction to Matchings with Preferences. Stable marriage problem. Gale and Shapley algorithm.

Meeting 24 : Wed, Feb 25, 10:00 am-10:50 am

Gale Shapley continued. Proof of man-optimal stable matching.

Meeting 25 : Thu, Feb 26, 08:00 am-08:50 am

Some more properties of stable matchings. Popularity of stable matchings. Towards a lattice structure.

Meeting 26 : Fri, Feb 27, 02:00 pm-02:50 pm

Lattice Structure of the stable marriage problem. Generalization like incomplete lists and ties. All stable matchings of an instance with incomplete lists have the same size.

Meeting 27 : Mon, Mar 02, 11:00 am-11:50 am

Stable matchings with ties and incomplete lists. Kiraly's paper. A 2/3 approximation algorithm for computing maximum cardinality stable matchings. (Restricted case of one sided ties allowed).
A useful lemma on the way: A matching which avoids augmenting paths of length upto (2k-1) is a k/k+1 approximation to the maximum matching.

Meeting 28 : Tue, Mar 03, 11:00 am-11:50 am

Finished proof for 2/3 approximation algorithm. A sketch of the algorithm and the proof technique for 3/5 approximation for the general case (when both sides can have ties).

Meeting 29 : Wed, Mar 04, 10:00 am-10:50 am

Application of stable matchings to Dintiz Problem on list coloring Grid Graphs.

Meeting 30 : Thu, Mar 05, 08:00 am-08:50 am

Application of stable matchings to Dintiz Problem on list coloring Grid Graphs.

Meeting 31 : Fri, Mar 06, 02:00 pm-02:50 pm

To Be Announced

Meeting 32 : Tue, Mar 10, 11:00 am-11:50 am

Stable Room-mates problem. An algorithm to decide whether the instance admits a stable matching.

Meeting 33 : Wed, Mar 11, 10:00 am-10:50 am

Stable Roommates continued. 2-phase algorithm. Phase-1 similar to Gale and Shapley. Invariants on reduced preferences at the end of phase 1. Phase 2 involving rotations (equivalently all-or-nothing cycle). Elimination of rotation to reduce preference lists further.

Meeting 34 : Thu, Mar 12, 08:00 am-08:50 am

Finished discussion of phase 2 for stable roommates. Some practical questions -- what when stable matchings do not exist? What are alternative solutions.
Some structural questions:
Does the property (analogous to stable matchings in marriage problem) hold in the roommates case:
Given 2 stable matchings, for every person pick up the partner he prefers better amongst the 2 matchings. Prove or disprove that this choice leads to a stable matching.
Consider 3 stable matchings in the roommates instance and for every person, choose the median of the 3 partners he gets in 3 matchings. Show that such a choice leads to a matching and then show that it is a stable matching.

Meeting 35 : Fri, Mar 13, 02:00 pm-02:50 pm

Discussion on One sided preferences. Rank Maximiality, definition, reduction to maximum weight matchings.
Popular matchings. Definition. Strict lists. A characterization of popular matchings in terms of f and s posts.

Meeting 36 : Tue, Mar 17, 11:00 am-11:50 am

Popular matchings characterization with ties. O(m sqrt(n)) algorithm.

Meeting 37 : Wed, Mar 18, 10:00 am-10:50 am

Popular matchings: switching graph characterization for strict lists.
Answer the following questions efficiently:
1. How many popular matchings does the instance admit?
2. Given an edge (a,p) does there exist some popular matching that contains the edge (a,p)?

Meeting 38 : Thu, Mar 26, 08:00 am-08:50 am

Quiz 2.

Theme 3 : Dynamic Graph Algorithms. - 15 meetings

Meeting 39 : Fri, Mar 27, 02:00 pm-02:50 pm

Introduction, basic definitions -- updates, queries. Trade off between update time and query time. Incremental/decremental/partially dynamic updates.
Fully dynamic connectivity in Forests. Euler tour trees. An implementation using Doubly linked Lists.

Meeting 40 : Tue, Mar 31, 11:00 am-11:50 am

Euler tour trees continued. BST implementation by using Merge and split operations which can be supported by a balanced BST.
Splay trees as a balanced BST. Amortized log(n) update time for all operations.

Meeting 41 : Wed, Apr 01, 08:00 am-08:50 am

Splay trees continued. An amortized O(log(n)) operations -- insert, delete, search, split, join.

Meeting 42 : Thu, Apr 02, 08:00 am-08:50 am

Holiday.

Meeting 43 : Fri, Apr 03, 02:00 pm-02:50 pm

Holiday.

Meeting 44 : Tue, Apr 07, 11:00 am-11:50 am

Deterministic Algorithm for fully dynamic connectivity in graphs. Result by Holm et al. (JACM 2001). Uses fully dynamic connectivity algorithm for forests as a black box.

Meeting 45 : Wed, Apr 08, 10:00 am-10:50 am

Fully Dynamic Connectivity in graphs continued. Amortized O(log^2(n)) bound for update time.
A quick sketch of the algorithm for decremental Minimum spanning forests (MSF).

Meeting 46 : Thu, Apr 09, 08:00 am-08:50 am

The Hidden Paths Algorithm: A static All Pairs shortest paths algorithm. A prelude to the dynamic APSP algorithm.

Meeting 47 : Fri, Apr 10, 02:00 pm-02:50 pm

Decremental APSP. The intuitive idea behind defining Locally Shortest paths.

Meeting 48 : Sat, Apr 11, 11:30 am-12:30 pm

Continued decremental APSP. The update algorithm. Cleanup and Fixup. Time complexity of cleanup and fixup in terms of number of LSPs considered in each operation.

Meeting 49 : Tue, Apr 14, 11:00 am-11:50 am

Holiday.

Meeting 50 : Wed, Apr 15, 10:00 am-10:50 am

Directed graphs -- Discussion on reachability problems. Single source reachability, Strongly connected components and All pairs reachability.
Even Shiloach Trees for maintaining BFS trees in directed graphs. This immediately gives a single source reachability. O(mn) total update time algorithm. O(n) amortized update.

Meeting 51 : Thu, Apr 16, 08:00 am-08:50 am

Finished discussion on Even Shiloach trees.
Decremental Strongly connected components. Main ideas: to maintain BFS trees in G and G-reverse. Also use of randomization to get efficient update time. O(m n log(n)) total update time.

Meeting 52 : Fri, Apr 17, 02:00 pm-02:50 pm

Decremental Strongly Connected components continued.

Meeting 53 : Tue, Apr 21, 04:45 pm-06:00 pm

Fully Dynamic Matchings -- An O(Delta^2) simple algorithm for maintaining a 3/2 approximate matching. Use this as a blackbox to get a (3+epsilon) approximate matching in O(sqrt(m)) time.

Theme 4 : Student Presentations.
- 19 meetings
Meeting 54 : Wed, Feb 18, 10:00 am-10:50 am
Linear Reductions of Maximum Matchings. Paper by Therese Biedl. Presented by Sreekanth Gorla.
References
Exercises
Reading
Linear Reductions of Maximum Matchings. Paper by Therese Biedl. Presented by Sreekanth Gorla.
References: None
Meeting 55 : Thu, Feb 19, 08:00 am-08:50 am
Semi-Matchings by Ashutosh Ingole.
References
Exercises
Reading
Semi-Matchings by Ashutosh Ingole.
References: None
Meeting 56 : Thu, Mar 19, 08:00 am-08:50 am
Stable Marriage and Indifference. Paper by Rob Irving. (Discrete Applied Maths, 1994) Presented by Nikhil Rongala.
References
Exercises
Reading
Stable Marriage and Indifference. Paper by Rob Irving. (Discrete Applied Maths, 1994)
Presented by Nikhil Rongala.
References: None
Meeting 57 : Fri, Mar 20, 02:00 pm-02:50 pm
Marriage Honesty and Stability -- Paper by N. Immorlica and M. Mahdian (SODA 2005). Presented by Arnesh Ghorai.
References
Exercises
Reading
Marriage Honesty and Stability -- Paper by N. Immorlica and M. Mahdian (SODA 2005).
Presented by Arnesh Ghorai.
References: None
Meeting 58 : Tue, Mar 24, 11:00 am-11:50 am
To Be Announced
References
Exercises
Reading
To Be Announced
References: None
Meeting 59 : Wed, Mar 25, 10:00 am-10:50 am
To Be Announced
References
Exercises
Reading
To Be Announced
References: None
Meeting 60 : Sat, Apr 11, 09:30 am-11:30 am
Presentations by Manas Jyoti and Rajesh Pandian on Uniquely Restricted Matchings.
References
Exercises
Reading
Presentations by Manas Jyoti and Rajesh Pandian on Uniquely Restricted Matchings.
References: None
Meeting 61 : Sat, Apr 18, 09:30 am-11:30 am
Presentation by Dheeraj and Chanti.
References
Exercises
Reading
Presentation by Dheeraj and Chanti.
References: None
Meeting 62 : Tue, Apr 21, 11:00 am-11:50 am
Mix and Match: Paper by I. Ashlagi et al. appeared in Electronic Commerce 2010). Presentation by Ayush and Nikhil.
References
Exercises
Reading
Mix and Match: Paper by I. Ashlagi et al. appeared in Electronic Commerce 2010).
Presentation by Ayush and Nikhil.
References: None
Meeting 63 : Wed, Apr 22, 10:00 am-10:50 am
Mix and Match: Paper by I. Ashlagi et al. appeared in Electronic Commerce 2010). Presentation by Ayush and Nikhil.
References
Exercises
Reading
Mix and Match: Paper by I. Ashlagi et al. appeared in Electronic Commerce 2010).
Presentation by Ayush and Nikhil.
References: None
Meeting 64 : Thu, Apr 23, 08:00 am-08:50 am
Presentation by Sasidhar and Raghavendra Kiran.
References
Exercises
Reading
Presentation by Sasidhar and Raghavendra Kiran.
References: None
Meeting 65 : Fri, Apr 24, 02:00 pm-02:50 pm
Presentation by Sasidhar and Raghavendra Kiran.
References
Exercises
Reading
Presentation by Sasidhar and Raghavendra Kiran.
References: None
Meeting 66 : Sat, Apr 25, 09:30 am-11:30 am
Samuel Peterson. Akshay Gaikwad.
References
Exercises
Reading
Samuel Peterson.
Akshay Gaikwad.
References: None
Meeting 67 : Mon, May 04, 09:30 am-12:30 pm
Presentation by Ajay Krishna 10.30-11.30AM. [link-cut Trees] Student presentations 2 slots available.
References
Exercises
Reading
Presentation by Ajay Krishna 10.30-11.30AM. [link-cut Trees]
Student presentations 2 slots available.
References: None
Meeting 68 : Tue, May 05, 09:30 am-12:30 pm
Student Presentations (3 slots).
References
Exercises
Reading
Student Presentations (3 slots).
References: None
Meeting 69 : Wed, May 06, 09:30 am-12:30 pm
Presentation by Alexander (Minimum spanning forest in Dynamic Planar graphs) 2 slots free.
References
Exercises
Reading
Presentation by Alexander (Minimum spanning forest in Dynamic Planar graphs)
2 slots free.
References: None
Meeting 70 : Thu, May 07, 09:30 am-12:30 pm
Presentation by Aswathi. (Maximum flows by Incremental BFS). Presentation by Amal Joy. (Incremental Algorithms for minimal length paths) Gunalaan and Anuj 
References
Exercises
Reading
Presentation by Aswathi. (Maximum flows by Incremental BFS).
Presentation by Amal Joy. (Incremental Algorithms for minimal length paths)
Gunalaan and Anuj

References: None
Meeting 71 : Fri, May 08, 09:30 am-12:30 pm
Presentation by Yogendra. Student Presentations -- 2 slots.
References
Exercises
Reading
Presentation by Yogendra.
Student Presentations -- 2 slots.
References: None
Meeting 72 : Sat, May 09, 09:30 am-12:30 pm
Presentation by Himanshu Jain. 2-slots available.
References
Exercises
Reading
Presentation by Himanshu Jain.
2-slots available.
References: None

CS6190 - Recent Developments in Theoretical Computer Science

Today : Sat, Apr 27, 2024

Announcements

Meetings

References	Book: Combinatorial Optimization by Papadimitriou and Steiglitz. Chapter 10.
Exercises
Reading

References	See Notes by Nitish Korula locally copied. http://www.cse.iitm.ac.in/~meghana/matchings/weighted-bip-NitishKorula-notes.pdf
Exercises
Reading

References	See notes at: http://www.cse.iitm.ac.in/~meghana/matchings/bip-decomp.pdf
Exercises
Reading

References	This result is from a paper by Goel, Kapralov and Khanna (STOC 2010). <br> Find the paper at: http://www.cse.iitm.ac.in/~meghana/matchings/p39-goel.pdf <br> The presentation in the class is based on the lecture notes by Prof. Spielman. http://www.cs.cmu.edu/~15859n/RelatedWork/Spielman/Spielman-Matching.pdf
Exercises
Reading

References	See earlier lecture for references.
Exercises
Reading

References	See Lecture Notes: http://www.cse.iitm.ac.in/~meghana/matchings/gen-matching-Notes.pdf
Exercises
Reading

References	http://www.cse.iitm.ac.in/~meghana/matchings/gen-matching-Notes.pdf
Exercises
Reading

References	Stable Marriage: Structure and Algorithms by Irving and Gusfield. (Chapter 1).
Exercises
Reading

References	http://www.cs.elte.hu/egres/tr/egres-08-04.pdf
Exercises
Reading

References	Proofs from the Book. Chapter 33. <br> cage.ugent.be/~kn/thebook.pdf
Exercises
Reading

References	See the orginial and self explanatory paper by Rob Irving. http://www.dcs.gla.ac.uk/~pat/jchoco/roommates/papers/Comp_sdarticle.pdf
Exercises
Reading

References	https://people.mpi-inf.mpg.de/~mehlhorn/ftp/PopularMatchingsJournal.pdf
Exercises
Reading

References	http://www.dcs.gla.ac.uk/publications/PAPERS/9011/PopMatchTechRep.pdf
Exercises
Reading

References	See Prof. Venkatesh Raman's notes on Dynamic Connectivity. <br> http://www.imsc.res.in/~vraman/adsjan2012/lect15.pdf
Exercises
Reading

References	See original Paper by Sleator and Tarjan:<br> https://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf See lecture notes by Prof. Goemans. <br> http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-854j-advanced-algorithms-fall-2008/lecture-notes/lec6.pdf
Exercises
Reading

References	http://dl.acm.org/citation.cfm?id=502095 Section 2 from the paper.
Exercises
Reading

References	See original paper: <br> http://ai.stanford.edu/~koller/Papers/Karger+al:93.pdf <br> Section 2 of the paper.
Exercises
Reading

References	See original paper by Demetrescu and Italiano: <br> http://www.dis.uniroma1.it/~demetres/docs/dapsp-full.pdf <br> Covered parts before Section 3.4.
Exercises
Reading

References	Original Paper by Even and Shiloach. <br> Search for "An Online Edge Deletion Problem" (JACM, 1981). <br> See also lecture video by Sayan Bhattacharya for the presentation on directed graphs.
Exercises
Reading

References	For SCC : see paper by Roddity and Zwick (SI-Comp, 2008). <br> http://epubs.siam.org/doi/pdf/10.1137/060650271 <br> Section 2 of above paper.
Exercises
Reading

References	Paper by Sayan Bhattacharya et. al (SODA 2015). <br> http://epubs.siam.org/doi/pdf/10.1137/1.9781611973730.54 <br> Section 3 from the above paper.
Exercises
Reading

Linear Reductions of Maximum Matchings. Paper by Therese Biedl. Presented by Sreekanth Gorla.

Stable Marriage and Indifference. Paper by Rob Irving. (Discrete Applied Maths, 1994)<br> Presented by Nikhil Rongala.

Marriage Honesty and Stability -- Paper by N. Immorlica and M. Mahdian (SODA 2005). <br> Presented by Arnesh Ghorai.

Presentations by Manas Jyoti and Rajesh Pandian on Uniquely Restricted Matchings.

Mix and Match: Paper by I. Ashlagi et al. appeared in Electronic Commerce 2010).<br> Presentation by Ayush and Nikhil.

Presentation by Ajay Krishna 10.30-11.30AM. [link-cut Trees] <br> Student presentations 2 slots available.

Presentation by Alexander (Minimum spanning forest in Dynamic Planar graphs) <br> 2 slots free.

Presentation by Aswathi. (Maximum flows by Incremental BFS). <br> Presentation by Amal Joy. (Incremental Algorithms for minimal length paths) <br> Gunalaan and Anuj <br>

Presentation by Yogendra. <br> Student Presentations -- 2 slots.