CS6841 - Advanced Algorithms

Meetings  

• Theme 1 : Network Flows - 4 meetings

  • Meeting 01 : Wed, Jan 15, 06:00 am-06:00 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

  • Meeting 02 : Fri, Jan 17, 11:00 am-11:50 am

  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

  • Meeting 03 : Mon, Jan 20, 09:00 am-09:50 am

  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

  • Meeting 04 : Tue, Jan 21, 08:00 am-08:50 am

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

• Theme 2 : NP-completeness and Reductions - 3 meetings

  • Meeting 05 : Wed, Jan 22, 12:00 pm-12:50 pm

  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.

  • Meeting 06 : Fri, Jan 24, 11:00 am-11:50 am

  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.

  • Meeting 07 : Mon, Jan 27, 09:00 am-09:50 am

  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

  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.

  • Meeting 09 : Wed, Jan 29, 12:00 pm-12:50 pm

  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.

  • Meeting 10 : Fri, Jan 31, 11:00 am-11:50 am

  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.

  • Meeting 11 : Mon, Feb 03, 09:00 am-09:50 am

  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.

  • Meeting 12 : Tue, Feb 04, 08:00 am-08:50 am

  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.

  • Meeting 13 : Wed, Feb 05, 12:00 pm-12:50 pm

  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.

  • Meeting 14 : Fri, Feb 07, 11:00 am-11:50 am

  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.

  • Meeting 15 : Mon, Feb 10, 09:00 am-09:50 am

  Edge coloring Delta + 1 approximation.

  References	Shmoys and Williamson Chapter 2.
  Exercises
  Reading

  Edge coloring Delta + 1 approximation.
  

  References:

  Shmoys and Williamson Chapter 2.

  • Meeting 16 : Tue, Feb 11, 08:00 am-08:50 am

  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.

  • Meeting 17 : Wed, Feb 12, 12:00 pm-12:50 pm

  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.

  • Meeting 18 : Fri, Feb 14, 11:00 am-11:50 am

  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.

  • Meeting 19 : Mon, Feb 17, 09:00 am-09:50 am

  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.

  • Meeting 20 : Tue, Feb 18, 08:00 am-08:50 am

  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.

  • Meeting 21 : Wed, Feb 19, 06:00 am-06:00 am

  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 theorem
  

  References:	section 3.7 of Approximating covering and packing problems. Book by Dorit Hochbaum
  Reading:	Section 3.7.1 of Hochbaum

  • Meeting 22 : Fri, Feb 21, 11:00 am-11:50 am

  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.

  • Meeting 23 : Mon, Feb 24, 09:00 am-09:50 am

  No class.

  References
  Exercises
  Reading

  No class.
  

  References:

  None

  • Meeting 24 : Tue, Feb 25, 08:00 am-08:50 am

  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.

  • Meeting 25 : Wed, Feb 26, 06:00 am-06:00 am

  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

  • Meeting 26 : Fri, Feb 28, 11:00 am-11:50 am

  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.

  • Meeting 27 : Mon, Mar 03, 09:00 am-09:50 am

  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.

  • Meeting 28 : Tue, Mar 04, 08:00 am-08:50 am

  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.

  • Meeting 29 : Wed, Mar 05, 06:00 am-06:00 am

  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.

  • Meeting 30 : Fri, Mar 07, 11:00 am-11:50 am

  No class.

  References
  Exercises
  Reading

  No class.
  

  References:

  None

  • Meeting 31 : Mon, Mar 10, 09:00 am-09:50 am

  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.

  • Meeting 32 : Tue, Mar 11, 08:00 am-08:50 am

  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.

  • Meeting 33 : Wed, Mar 12, 06:00 am-06:00 am

  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.

  • Meeting 34 : Fri, Mar 14, 11:00 am-11:50 am

  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.

  • Meeting 35 : Mon, Mar 17, 09:00 am-09:50 am

  References
  Exercises
  Reading

  
  

  References:

  None

  • Meeting 36 : Tue, Mar 18, 08:00 am-08:50 am

  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.

  • Meeting 37 : Wed, Mar 19, 06:00 am-06:00 am

  No Class.

  References
  Exercises
  Reading

  No Class.
  

  References:

  None

  • Meeting 38 : Fri, Mar 21, 11:00 am-11:50 am

  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.

  • Meeting 39 : Mon, Mar 24, 09:00 am-09:50 am

  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.

  • Meeting 40 : Tue, Mar 25, 08:00 am-08:50 am

  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.

  • Meeting 41 : Wed, Mar 26, 06:00 am-06:00 am

  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.

  • Meeting 42 : Fri, Mar 28, 11:00 am-11:50 am

  Guarding a set of Line Segments.

  References	Will be provided.
  Exercises
  Reading

  Guarding a set of Line Segments.
  

  References:

  Will be provided.

  • Meeting 43 : Mon, Mar 31, 09:00 am-09:50 am

  No Class -- Ugadi.

  References
  Exercises
  Reading

  No Class -- Ugadi.
  

  References:

  None

  • Meeting 44 : Mon, Apr 14, 09:00 am-09:50 am

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • Meeting 45 : Tue, Apr 15, 08:00 am-08:50 am

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • Meeting 46 : Wed, Apr 16, 12:00pm-12:50pm

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • Meeting 47 : Fri, Apr 18, 11:00 am-11:50 am

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • Meeting 48 : Mon, Apr 21, 09:00 am-09:50 am

  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.

  • Meeting 49 : Tue, Apr 22, 08:00 am-08:50 am

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • Meeting 50 : Wed, Apr 23, 12:00pm-12:50pm

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • Meeting 51 : Fri, Apr 25, 11:00 am-11:50 am

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • Meeting 52 : Mon, Apr 28, 09:00 am-09:50 am

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • Meeting 53 : Tue, Apr 29, 08:00 am-08:50 am

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • Meeting 54 : Wed, Apr 30, 12:00pm-12:50pm

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • Meeting 55 : Fri, May 02, 11:00 am-11:50 am

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • Meeting 56 : Mon, May 05, 09:00 am-09:50 am

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • Meeting 57 : Tue, May 06, 08:00 am-08:50 am

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • Meeting 58 : Wed, May 07, 12:00pm-12:50pm

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • Meeting 59 : Fri, May 09, 11:00 am-11:50 am

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

• Theme 4 : Algorithms for Matchings. - 7 meetings

  • Meeting 60 : Tue, Apr 01, 08:00 am-08: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

  • Meeting 61 : Wed, Apr 02, 12:00 pm-12:50 pm

  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.

  • Meeting 62 : Fri, Apr 04, 11:00 am-11:50 am

  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.

  • Meeting 63 : Mon, Apr 07, 09:00 am-09:50 am

  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.

  • Meeting 64 : Tue, Apr 08, 08:00 am-08:50 am

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • Meeting 65 : Wed, Apr 09, 06:00 am-06:00 am

  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

  • Meeting 66 : Fri, Apr 11, 11:00 am-11:50 am

  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.