CS6841 - Advanced Algorithms

Meetings  

• Theme 1 : Flows and NP-Completeness - 7 meetings

  • Meeting 01 : Mon, Jan 12, 09:00 am-09:50 am -

  Introduction to Course contents. Need for approximation algorithms. A simple example of Job scheduling on 2 processors. Minimize Makespan. Introduction of a lower bound for minimization problem.

  References	Shmoys and Williamson.
  Exercises
  Reading

  Introduction to Course contents. Need for approximation algorithms. A simple example of Job scheduling on 2 processors. Minimize Makespan. Introduction of a lower bound for minimization problem.
  

  References:

  Shmoys and Williamson.

  • Meeting 02 : Tue, Jan 13, 08:00 am-09:00 am -

  Max-Flow problem: definition. Capacity and Flow conservation constraints. Definition of value of flow. Examples of simple reductions.

  References	CLRS Chapter 26.
  Exercises
  Reading

  Max-Flow problem: definition. Capacity and Flow conservation constraints. Definition of value of flow. Examples of simple reductions.
  

  References:

  CLRS Chapter 26.

  • Meeting 03 : Wed, Jan 14, 12:00 pm-12:50 pm -

  Ford Fulkerson Method for Max flows. Residual network, augmenting paths.

  References
  Exercises
  Reading

  Ford Fulkerson Method for Max flows. Residual network, augmenting paths.
  

  References:

  None

  • Meeting 04 : Fri, Jan 16, 11:00 am-11:50 am -

  Max Flow Min Cut theorem. Edmonds Karp implementation of Ford Fulkerson Method.

  References	CLRS Chapter 26.
  Exercises
  Reading

  Max Flow Min Cut theorem. Edmonds Karp implementation of Ford Fulkerson Method.
  

  References:

  CLRS Chapter 26.

  • Meeting 05 : Mon, Jan 19, 09:00 am-09:50 am -

  Completed proof of strongly polynomial time running time of Edmonds Karp Algorithm. <br> Defined Escape Problem on Grid (Exercise 26-1, CLRS) and Maximum Bipartite matching problem. The reductions from these to a network flow problem was given as an exercise.

  References	CLRS Chapter 26.
  Exercises
  Reading	CLRS Section 26.3.

  Completed proof of strongly polynomial time running time of Edmonds Karp Algorithm.
  Defined Escape Problem on Grid (Exercise 26-1, CLRS) and Maximum Bipartite matching problem. The reductions from these to a network flow problem was given as an exercise.
  

  References:	CLRS Chapter 26.
  Reading:	CLRS Section 26.3.

  • Meeting 06 : Tue, Jan 20, 08:00 am-08:50 am -

  Decision vs. Optimization Problems. Verification vs. Solving. Classes P and NP. Polynomial time verification. Class co-NP. Notion of reductions.

  References	CLRS Chapter 34.
  Exercises
  Reading

  Decision vs. Optimization Problems. Verification vs. Solving. Classes P and NP. Polynomial time verification. Class co-NP. Notion of reductions.
  

  References:

  CLRS Chapter 34.

  • Meeting 07 : Wed, Jan 21, 06:00 am-06:00 am -

  Reductions continued. 3SAT to Clique. VC to Ham-cycle [Gadget reduction].

  References	CLRS Chapter 34.
  Exercises
  Reading

  Reductions continued. 3SAT to Clique. VC to Ham-cycle [Gadget reduction].
  

  References:

  CLRS Chapter 34.

• Theme 2 : Approximation algorithms (Combinatorial Techniques) - 19 meetings

  • Meeting 08 : Fri, Jan 23, 11:00 am-11:50 am -

  Approximation algorithm definition. Vertex cover, matching lower bound. A simple 2 approximation. Can the analysis be improved? Can the algorithm using this lower bound be improved?

  References	Vazirani, Chapter 1.
  Exercises
  Reading

  Approximation algorithm definition. Vertex cover, matching lower bound. A simple 2 approximation. Can the analysis be improved? Can the algorithm using this lower bound be improved?
  

  References:

  Vazirani, Chapter 1.

  • Meeting 09 : Mon, Jan 26, 09:00 am-09:50 am -

  Republic Day !

  References
  Exercises
  Reading

  Republic Day !
  

  References:

  None

  • Meeting 10 : Tue, Jan 27, 08:00 am-08:50 am -

  Unweighted Max-Cut, simple 1/2 approximation. Emphasise idea of using lower/upper bounds. TSP, inapproximability in general case. MST lower bound.

  References	Vazirani Chapter 3.
  Exercises
  Reading

  Unweighted Max-Cut, simple 1/2 approximation. Emphasise idea of using lower/upper bounds. TSP, inapproximability in general case. MST lower bound.
  

  References:

  Vazirani Chapter 3.

  • Meeting 11 : Wed, Jan 28, 12:00 pm-12:50 pm -

  2-approx for TSP, 3/2 approx. for TSP. Stiener tree.

  References
  Exercises
  Reading

  2-approx for TSP, 3/2 approx. for TSP. Stiener tree.
  

  References:

  None

  • Meeting 12 : Fri, Jan 30, 11:00 am-11:50 am -

  Steiner tree. Approximation preserving reduction from general case to metric case. A quick sketch of 2-approx for metric case.

  References	Vazirani Chapter 3. Also see Appendix of Vazirani for definition of approximation preserving reductions.
  Exercises
  Reading

  Steiner tree. Approximation preserving reduction from general case to metric case. A quick sketch of 2-approx for metric case.
  

  References:

  Vazirani Chapter 3. Also see Appendix of Vazirani for definition of approximation preserving reductions.

  • Meeting 13 : Mon, Feb 02, 09:00 am-09:50 am -

  Steiner tree, metric case, 2-approximation, 2(1-1/|R|) factor approximation. <br> Introduction to weighted set-cover problem. Greedy strategy outline. Definition of price of an element.

  References	Vazirani Chapter 3 and Chapter 1.
  Exercises
  Reading

  Steiner tree, metric case, 2-approximation, 2(1-1/|R|) factor approximation.
  Introduction to weighted set-cover problem. Greedy strategy outline. Definition of price of an element.
  

  References:

  Vazirani Chapter 3 and Chapter 1.

  • Meeting 14 : Tue, Feb 03, 08:00 am-08:50 am -

  Weighted set cover ln(n) approximation algorithm.

  References	Vazirani Chapter 2.
  Exercises
  Reading

  Weighted set cover ln(n) approximation algorithm.
  

  References:

  Vazirani Chapter 2.

  • Meeting 15 : Wed, Feb 04, 12:00 pm-12:50 pm -

  Tutorial class.

  References
  Exercises
  Reading

  Tutorial class.
  

  References:

  None

  • Meeting 16 : Fri, Feb 06, 11:00 am-11:50 am -

  Class canceled.

  References
  Exercises
  Reading

  Class canceled.
  

  References:

  None

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

  Metric k-center problem. 2-approximation. Inapproximability for 2-epsilon.

  References	Shmoys and Williamsons, chapter 2.
  Exercises
  Reading

  Metric k-center problem. 2-approximation. Inapproximability for 2-epsilon.
  

  References:

  Shmoys and Williamsons, chapter 2.

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

  Job scheduling on identical parallel machines. Minimizing makespan. 2-approximation. 4/3-appoximation.

  References	Shmoys and Williamson, Chapter 2.
  Exercises
  Reading

  Job scheduling on identical parallel machines. Minimizing makespan. 2-approximation. 4/3-appoximation.
  

  References:

  Shmoys and Williamson, Chapter 2.

  • Meeting 19 : Wed, Feb 11, 12:00 pm-12:50 pm -

  Makespan 4/3 approx continued. Examples of Local search.

  References
  Exercises
  Reading

  Makespan 4/3 approx continued. Examples of Local search.
  

  References:

  None

  • Meeting 20 : Fri, Feb 13, 11:00 am-11:50 am -

  Edge Coloring Delta+ 1 approximation, Vizing's theorem.

  References	Shmoys and Williamsons, Chapter 2.
  Exercises
  Reading

  Edge Coloring Delta+ 1 approximation, Vizing's theorem.
  

  References:

  Shmoys and Williamsons, Chapter 2.

  • Meeting 21 : Mon, Feb 16, 09:00 am-09:50 am -

  Edge coloring continued.

  References	Shmoys and Williamson Chapter 2.
  Exercises
  Reading

  Edge coloring continued.
  

  References:

  Shmoys and Williamson Chapter 2.

  • Meeting 22 : Tue, Feb 17, 08:00 am-08:50 am -

  Minimum Degree Spanning tree. Local search technique. Defined the criteria for local move.

  References	Shmoys and Williamson Chapter 2.
  Exercises
  Reading

  Minimum Degree Spanning tree. Local search technique. Defined the criteria for local move.
  

  References:

  Shmoys and Williamson Chapter 2.

  • Meeting 23 : Wed, Feb 18, 12:00 pm-12:50 pm -

  Minimum Degree spanning tree, lower bound on OPT, approximation factor and running time.

  References	Shmoys and Williamson, Chapter 2.
  Exercises
  Reading

  Minimum Degree spanning tree, lower bound on OPT, approximation factor and running time.
  

  References:

  Shmoys and Williamson, Chapter 2.

  • Meeting 24 : Fri, Feb 20, 11:00 am-11:50 am -

  Minimizing max-degree spanning tree: running time analysis.

  References
  Exercises
  Reading

  Minimizing max-degree spanning tree: running time analysis.
  

  References:

  None

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

  0/1 Knapsack. FPTAS. Emphasis on how the parameter mu was chosen.

  References
  Exercises
  Reading

  0/1 Knapsack. FPTAS. Emphasis on how the parameter mu was chosen.
  

  References:

  None

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

  Dynamic Programming for Knapsack. Introduction to LPs.

  References
  Exercises
  Reading

  Dynamic Programming for Knapsack. Introduction to LPs.
  

  References:

  None

• Theme 3 : Approximation Algorithms (LP and SDP based) - 37 meetings

  • Meeting 27 : Wed, Feb 25, 12:00 pm-12:50 pm -

  Set Cover LP and f-approximation for weighted set cover via deterministic rounding. Notion of dual. Exercises -- formulate VC, Knapsack as Linear Programs. Construct the duals.

  References	Chapter 12 of Vazirani. Chapter 1 of Shmoys and Williamsons.
  Exercises
  Reading

  Set Cover LP and f-approximation for weighted set cover via deterministic rounding. Notion of dual. Exercises -- formulate VC, Knapsack as Linear Programs. Construct the duals.
  

  References:

  Chapter 12 of Vazirani. Chapter 1 of Shmoys and Williamsons.

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

  More on Duality. Proof of Weak duality and statement of strong duality. Complementary slackness conditions. Examples and proof of one direction (if primal and dual solutions are optimal, then they satisfy complementary slackness).

  References	Chapter 12, Vazirani.
  Exercises
  Reading

  More on Duality. Proof of Weak duality and statement of strong duality. Complementary slackness conditions. Examples and proof of one direction (if primal and dual solutions are optimal, then they satisfy complementary slackness).
  

  References:

  Chapter 12, Vazirani.

  • Meeting 29 : Mon, Mar 02, 11:00 am-11:50 am -

  1/2 integrality of vertex cover. Linear programs with exponentially many constraints. Warm-up exercise s-t shortest paths. Prize Collecting Steiner Tree.

  References	Chapter 14 Vazirani (1/2 integrality of VC) and Chapter 4, Shmoys and Williamsons.
  Exercises
  Reading

  1/2 integrality of vertex cover. Linear programs with exponentially many constraints. Warm-up exercise s-t shortest paths. Prize Collecting Steiner Tree.
  

  References:

  Chapter 14 Vazirani (1/2 integrality of VC) and Chapter 4, Shmoys and Williamsons.

  • Meeting 30 : Tue, Mar 03, 08:00 am-08:50 am -

  Prize Collecting Steiner tree.

  References	Chapter 4, Shmoys and Williamsons.
  Exercises
  Reading

  Prize Collecting Steiner tree.
  

  References:

  Chapter 4, Shmoys and Williamsons.

  • Meeting 31 : Wed, Mar 04, 12:00 pm-12:50 pm -

  Prize Collecting Steiner tree.

  References
  Exercises
  Reading

  Prize Collecting Steiner tree.
  

  References:

  None

  • Meeting 32 : Fri, Mar 06, 11:00 am-11:50 am -

  Non-Instructional Day (Holi).

  References
  Exercises
  Reading

  Non-Instructional Day (Holi).
  

  References:

  None

  • Meeting 33 : Mon, Mar 09, 09:00 am-09:50 am - Narayanaswamy

  Discussion about generic framework of casting combinatorial problems as LPs and Vector programs. How does one round in this setting of vector programs? Choose a random hyperplane passing through the origin. How does one choose this plane? <br> Vertex cover LP. Recall 1/2 integrality of Vertex cover LP. Nemhauser Trotter theorem and its proof.

  References	Hochbaum's book
  Exercises
  Reading

  Discussion about generic framework of casting combinatorial problems as LPs and Vector programs. How does one round in this setting of vector programs? Choose a random hyperplane passing through the origin. How does one choose this plane?
  Vertex cover LP. Recall 1/2 integrality of Vertex cover LP. Nemhauser Trotter theorem and its proof.
  

  References:

  Hochbaum's book

  • Meeting 34 : Tue, Mar 10, 08:00 am-08:50 am -

  MAX SAT and MAX CUT: randomized rounding. A simple 1/2 approximation using randomized rounding for both problems. Derandomization.

  References	Chapter 5 (Sections 5.1, 5.2, 5.3) Shmoys and Williamsons.
  Exercises
  Reading

  MAX SAT and MAX CUT: randomized rounding. A simple 1/2 approximation using randomized rounding for both problems. Derandomization.
  

  References:

  Chapter 5 (Sections 5.1, 5.2, 5.3) Shmoys and Williamsons.

  • Meeting 35 : Wed, Mar 11, 12:00 pm-12:50 pm -

  MAX SAT continued. Randomized rounding. Choosing the better of the 2 solutions. A 3/4 approximation algorithm.

  References	Chapter 5 (Sections 5.3, 5.4) Shmoys and Williamsons.
  Exercises
  Reading

  MAX SAT continued. Randomized rounding. Choosing the better of the 2 solutions. A 3/4 approximation algorithm.
  

  References:

  Chapter 5 (Sections 5.3, 5.4) Shmoys and Williamsons.

  • Meeting 36 : Fri, Mar 13, 11:00 am-11:50 am -

  Prize collecting Steiner tree. Randomized Rounding approach. (Recall deterministic rounding gives 3-approx). Goal to improve the approx. guarantee.

  References	Chapter 5 (Section 5.7) Shmoys and Williamsons.
  Exercises
  Reading

  Prize collecting Steiner tree. Randomized Rounding approach. (Recall deterministic rounding gives 3-approx). Goal to improve the approx. guarantee.
  

  References:

  Chapter 5 (Section 5.7) Shmoys and Williamsons.

  • Meeting 37 : Mon, Mar 16, 09:00 am-09:50 am -

  Prize collecting Steiner Tree: randomized rounding analysis completed. <br> Vertex coloring. Promise problems -- 3 colorable graphs. A simple O(sqrt(n)) algorithm using the following 2 observations -- i) every graph is vertex colorable using Delta+1 colors. ii) If a graph is 3-colorable, then for every vertex its neighbourhood is 2-colorable.

  References	Chapter 5 (section 5.12) Shmoys and Williamsons.
  Exercises
  Reading

  Prize collecting Steiner Tree: randomized rounding analysis completed.
  Vertex coloring. Promise problems -- 3 colorable graphs. A simple O(sqrt(n)) algorithm using the following 2 observations -- i) every graph is vertex colorable using Delta+1 colors. ii) If a graph is 3-colorable, then for every vertex its neighbourhood is 2-colorable.
  

  References:

  Chapter 5 (section 5.12) Shmoys and Williamsons.

  • Meeting 38 : Tue, Mar 17, 08:00 am-08:50 am - Narayanaswamy

  Application of chernoff bounds to 3 colouring dense graphs - a random sample of vertices with a good probabiliyt is a small dominating set. Two events here - Small set and Dominating set. In both chernoff bound used to bound deviations from expectation.

  References	Shmoys and WIlliamson, chapter 5.
  Exercises
  Reading

  Application of chernoff bounds to 3 colouring dense graphs - a random sample of vertices with a good probabiliyt is a small dominating set. Two events here - Small set and Dominating set. In both chernoff bound used to bound deviations from expectation.
  

  References:

  Shmoys and WIlliamson, chapter 5.

  • Meeting 39 : Wed, Mar 18, 06:00 am-06:00 am - Narayanaswamy

  Summarizing the line of thought in Randomised Rounding- a. Design probability distributions and get a handle on expectation and derandomize using conditional probability. b. For distributions, get a handle for expectation, and bound deviation, and get a good running time with high probability. c. Where do distributions come from: use LP optimum points a probability distributions (carefully), like in MAXSAT, and then take better of two distributions. d. There are better distributions- sneak preview into MAXCUT, assign vectors to vertices and design a cost function, and use a nice rounding technique. Summary, there are better distributions!! for MAXCUT. How good can these distributions become?

  References	Shmoys and WIlliamson - Chapter 6 and Chapter 5
  Exercises
  Reading

  Summarizing the line of thought in Randomised Rounding- a. Design probability distributions and get a handle on expectation and derandomize using conditional probability. b. For distributions, get a handle for expectation, and bound deviation, and get a good running time with high probability. c. Where do distributions come from: use LP optimum points a probability distributions (carefully), like in MAXSAT, and then take better of two distributions. d. There are better distributions- sneak preview into MAXCUT, assign vectors to vertices and design a cost function, and use a nice rounding technique. Summary, there are better distributions!! for MAXCUT. How good can these distributions become?
  

  References:

  Shmoys and WIlliamson - Chapter 6 and Chapter 5

  • Meeting 40 : Fri, Mar 20, 11:00 am-11:50 am - Meghana

  Discussion of quiz sheets

  References
  Exercises
  Reading

  Discussion of quiz sheets
  

  References:

  None

  • Meeting 41 : Mon, Mar 23, 09:00 am-09:50 am - Narayanaswamy

  Application of Chernoff Bounds to Integer Multicommodity Flow.

  References	Shmoys and Williamson, Chapter 5.
  Exercises
  Reading

  Application of Chernoff Bounds to Integer Multicommodity Flow.
  

  References:

  Shmoys and Williamson, Chapter 5.

  • Meeting 42 : Tue, Mar 24, 08:00 am-08:50 am - Narayanaswamy

  Introduction to the geometry of Linear programming and its application in approximation algorithms.

  References	Geometric Algorithms and Combinatorial Optimisation : preliminaries chapter, and chapter on ellipsoid method.
  Exercises
  Reading

  Introduction to the geometry of Linear programming and its application in approximation algorithms.
  

  References:

  Geometric Algorithms and Combinatorial Optimisation : preliminaries chapter, and chapter on ellipsoid method.

  • Meeting 43 : Wed, Mar 25, 06:00 am-06:00 am -

  Discussion of the ellipsoid method and ellipsoid template. The role of the separation oracle to find violated inequalities.

  References	Groetschel Lovasz Schrijver, Chapter on the Ellipsoid method.
  Exercises
  Reading

  Discussion of the ellipsoid method and ellipsoid template. The role of the separation oracle to find violated inequalities.
  

  References:

  Groetschel Lovasz Schrijver, Chapter on the Ellipsoid method.

  • Meeting 44 : Fri, Mar 27, 11:00 am-11:50 am -

  Introduction to positive semidefinite matrices. The structure of symmetric matrices with real valued entries. Decomposing the range of the linear transformation into eigen spaces. Characterisation of positive semidefinite real symmetric matrices. The usage in vector programs

  References	Chapter 6 of SHmoys and Williamson
  Exercises
  Reading

  Introduction to positive semidefinite matrices. The structure of symmetric matrices with real valued entries. Decomposing the range of the linear transformation into eigen spaces. Characterisation of positive semidefinite real symmetric matrices. The usage in vector programs
  

  References:

  Chapter 6 of SHmoys and Williamson

  • Meeting 45 : Mon, Mar 30, 09:00 am-09:50 am -

  Vector program relaxation of max-cut. Rounding using the solution to the vector program. Derandomizing using a random hyperplane containing the origin. How to sample a random hyperplane? What is the probability that the vectors given to end points of an edge fall on different sides of the hyperplane.

  References	Shmoys and williamson chapter 6
  Exercises
  Reading

  Vector program relaxation of max-cut. Rounding using the solution to the vector program. Derandomizing using a random hyperplane containing the origin. How to sample a random hyperplane? What is the probability that the vectors given to end points of an edge fall on different sides of the hyperplane.
  

  References:

  Shmoys and williamson chapter 6

  • Meeting 46 : Tue, Mar 31, 08:00 am-08:50 am -

  Completing the vector program analysis of max-cut. Introduction to approximate quadratic programming

  References	shmoys and williamson chapter 6
  Exercises
  Reading

  Completing the vector program analysis of max-cut. Introduction to approximate quadratic programming
  

  References:

  shmoys and williamson chapter 6

  • Meeting 47 : Wed, Apr 01, 06:00 am-06:00 am -

  Vector programs for approximate quadratic programming in which coefficients can be of arbitrary value, but the coefficient matrix is semidefinite. Using mclaurin's series to give a good approximation to arcsin(x), and application of the pointwise product operator on positive semidefinite matrices. Setting up the approximation

  References	Shmoys and williamson, 6th chapter.
  Exercises
  Reading

  Vector programs for approximate quadratic programming in which coefficients can be of arbitrary value, but the coefficient matrix is semidefinite. Using mclaurin's series to give a good approximation to arcsin(x), and application of the pointwise product operator on positive semidefinite matrices. Setting up the approximation
  

  References:

  Shmoys and williamson, 6th chapter.

  • Meeting 48 : Fri, Apr 03, 11:00 am-11:50 am -

  holiday

  References
  Exercises
  Reading

  holiday
  

  References:

  None

  • Meeting 49 : Mon, Apr 06, 09:00 am-09:50 am -

  SDP study of colouring 3 colourable graphs.

  References	Shmoys and williamson chapter 6
  Exercises
  Reading

  SDP study of colouring 3 colourable graphs.
  

  References:

  Shmoys and williamson chapter 6

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

  SDP for 3 coloring and subsequent randomised rounding

  References	shmoys and williamson chapter 6
  Exercises
  Reading

  SDP for 3 coloring and subsequent randomised rounding
  

  References:

  shmoys and williamson chapter 6

  • Meeting 51 : Wed, Apr 08, 06:00 am-06:00 am -

  SDP for coloring 3 colorable graphs. Introduction to role of complementary slackness, and the Primal-Dual template

  References	Chapter 7 Shmoys and Williamson
  Exercises
  Reading

  SDP for coloring 3 colorable graphs. Introduction to role of complementary slackness, and the Primal-Dual template
  

  References:

  Chapter 7 Shmoys and Williamson

  • Meeting 52 : Fri, Apr 10, 11:00 am-11:50 am -

  Class cancelled due to Biplav visit

  References
  Exercises
  Reading

  Class cancelled due to Biplav visit
  

  References:

  None

  • Meeting 53 : Mon, Apr 13, 09:00 am-09:50 am -

  Primal dual for set cover.

  References	shmoys and williamson chapter 7
  Exercises
  Reading

  Primal dual for set cover.
  

  References:

  shmoys and williamson chapter 7

  • Meeting 54 : Tue, Apr 14, 08:00 am-08:50 am -

  Primal Dual for set cover, mention of special kinds of set cover restrictions that this could be used for. Cycle hitting sets - feedback vertex cover introduced

  References	shmoys and williamson
  Exercises
  Reading

  Primal Dual for set cover, mention of special kinds of set cover restrictions that this could be used for. Cycle hitting sets - feedback vertex cover introduced
  

  References:

  shmoys and williamson

  • Meeting 55 : Wed, Apr 15, 06:00 am-06:00 am -

  Feedback vertex set primal -dual, logn approximation. careful choice of cycle whose corresponding dual variable need to be increased. Introduction to the s-t shortest path LP, and suggestion of understanding Dijkstra as primal dual. Introduction to Generalized steiner tree

  References	shmoys and williamson
  Exercises
  Reading

  Feedback vertex set primal -dual, logn approximation. careful choice of cycle whose corresponding dual variable need to be increased. Introduction to the s-t shortest path LP, and suggestion of understanding Dijkstra as primal dual. Introduction to Generalized steiner tree
  

  References:

  shmoys and williamson

  • Meeting 56 : Fri, Apr 17, 11:00 am-11:50 am -

  class cancelled due to unforeseen circumstances

  References
  Exercises
  Reading

  class cancelled due to unforeseen circumstances
  

  References:

  None

  • Meeting 57 : Mon, Apr 20, 09:00 am-09:50 am -

  Primal-Dual generalized steiner tree

  References	Shmoys and wiliamsson
  Exercises
  Reading

  Primal-Dual generalized steiner tree
  

  References:

  Shmoys and wiliamsson

  • Meeting 58 : Tue, Apr 21, 08:00 am-08:50 am -

  Primal Dual Generalized Steiner tree

  References	shmoys and williamson
  Exercises
  Reading

  Primal Dual Generalized Steiner tree
  

  References:

  shmoys and williamson

  • Meeting 59 : Wed, Apr 22, 06:00 am-06:00 am -

  Primal dual - Geoemetric set cover, hardness of setcover with intersections 1.

  References	shmoys and williamson
  Exercises
  Reading

  Primal dual - Geoemetric set cover, hardness of setcover with intersections 1.
  

  References:

  shmoys and williamson

  • Meeting 60 : Fri, Apr 24, 11:00 am-11:50 am -

  Line segment cover- lp formulation

  References	Meggido and Tamir - google key word
  Exercises
  Reading

  Line segment cover- lp formulation
  

  References:

  Meggido and Tamir - google key word

  • Meeting 61 : Mon, Apr 27, 09:00 am-09:50 am -

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • Meeting 62 : Tue, Apr 28, 08:00 am-08:50 am -

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • Meeting 63 : Wed, Apr 29, 12:00pm-12:50pm -

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None