{"id":653,"date":"2011-05-18T16:25:15","date_gmt":"2011-05-18T23:25:15","guid":{"rendered":"http:\/\/www.glencora.org\/?p=653"},"modified":"2011-05-18T16:25:15","modified_gmt":"2011-05-18T23:25:15","slug":"lecture-notes-for-bakers-technique-for-ptases-in-planar-graphs","status":"publish","type":"post","link":"https:\/\/blogs.oregonstate.edu\/glencora\/2011\/05\/18\/lecture-notes-for-bakers-technique-for-ptases-in-planar-graphs\/","title":{"rendered":"Lecture notes for Baker&#039;s technique for PTASes in planar graphs"},"content":{"rendered":"<p>In teaching so far, I have relied almost exclusively on textbooks and other people&#8217;s lecture notes (Jeff Erickson comes to mind, again and again) for providing materials to my students. \u00a0Yes, I would recommend this to anyone who has not been teaching for too long. \u00a0Preparing lecture notes that are hand-out-to-your-students worthy is time consuming! \u00a0Especially when you are a perfectionist.<\/p>\n<p>I&#8217;m teaching a grad course on approximation algorithms right now, using Vijay Vazirani&#8217;s book. \u00a0(Yes. \u00a0Those of us on the quarter system are still teaching.) \u00a0I wanted to teach Baker&#8217;s technique for giving PTASes on planar graphs as it is beautiful and close to my heart. \u00a0By heart, I mean brain. \u00a0I only wanted to spend a lecture or two on it and my students don&#8217;t know what treewidth is. \u00a0 The only lecture notes on this that I know of are <a href=\"http:\/\/www.cs.brown.edu\/courses\/cs250\/lectures\/19.pdf\">Philip<\/a> <a href=\"http:\/\/www.cs.brown.edu\/courses\/cs250\/lectures\/20.pdf\">Klein&#8217;s<\/a> and (stubbornly), I needed something more self-contained &#8211; that didn&#8217;t build on a course&#8217;s worth of notation and background.<\/p>\n<p>So, I prepared <a href=\"http:\/\/teach.glencora.org\/index.php?title=Baker%27s_technique:_Designing_approximation_schemes_for_planar_graphs\">these notes<\/a> on my wiki teaching page. \u00a0I don&#8217;t prove that k-outerplanar graphs have treewidth 3k-1 or even define treewidth, but I show a simpler version of solving maximum-weight independent set on something I call k-innerplanar graphs. \u00a0I think it gives the intuition and ingredients of the full picture without getting caught up in too many details. \u00a0If anyone spots a bug, inconsistency, etc, please let me know.<\/p>\n<p>So, yes, basically I am announcing &#8220;Ooooh look at me! \u00a0I&#8217;m doing something everyone else has already done time and time again!&#8221;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>In teaching so far, I have relied almost exclusively on textbooks and other people&#8217;s lecture notes (Jeff Erickson comes to mind, again and again) for providing materials to my students. \u00a0Yes, I would recommend this to anyone who has not been teaching for too long. \u00a0Preparing lecture notes that are hand-out-to-your-students worthy is time consuming! [&hellip;]<\/p>\n","protected":false},"author":3747,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[106166,106170,106178,106190],"class_list":["post-653","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-grad-algorithms","tag-lecture-notes","tag-planar-graphs","tag-tcs"],"_links":{"self":[{"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/posts\/653","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/users\/3747"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/comments?post=653"}],"version-history":[{"count":0,"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/posts\/653\/revisions"}],"wp:attachment":[{"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/media?parent=653"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/categories?post=653"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/tags?post=653"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}