Glencora Borradaile






         Associate Professor & College of Engineering Dean's Professor, School of Electrical Engineering and Computer Science, Oregon State University

May 18, 2011

Lecture notes for Baker's technique for PTASes in planar graphs

In teaching so far, I have relied almost exclusively on textbooks and other people’s lecture notes (Jeff Erickson comes to mind, again and again) for providing materials to my students.  Yes, I would recommend this to anyone who has not been teaching for too long.  Preparing lecture notes that are hand-out-to-your-students worthy is time consuming!  Especially when you are a perfectionist.

I’m teaching a grad course on approximation algorithms right now, using Vijay Vazirani’s book.  (Yes.  Those of us on the quarter system are still teaching.)  I wanted to teach Baker’s technique for giving PTASes on planar graphs as it is beautiful and close to my heart.  By heart, I mean brain.  I only wanted to spend a lecture or two on it and my students don’t know what treewidth is.   The only lecture notes on this that I know of are Philip Klein’s and (stubbornly), I needed something more self-contained – that didn’t build on a course’s worth of notation and background.

So, I prepared these notes on my wiki teaching page.  I don’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.  I think it gives the intuition and ingredients of the full picture without getting caught up in too many details.  If anyone spots a bug, inconsistency, etc, please let me know.

So, yes, basically I am announcing “Ooooh look at me!  I’m doing something everyone else has already done time and time again!”

Print Friendly, PDF & Email


3 Comments

  1.   Claire Mathieu — June 1, 2011 @ 6:29 am    

    Very nice! Thank you!
    What do you think of the wikipedia entry on tree width etc?
    http://en.wikipedia.org/wiki/Tree_decomposition

  2.   Glencora — June 6, 2011 @ 9:02 am    

    Those are great notes on treewidth – it’s nice to be able to increasingly depend on wikipedia. I initially considered writing up these notes for a wiki entry on PTASes in planar graphs, but didn’t think the level of detail would be appropriate for lecture notes.

  3.   Bala Krishnamoorthy — June 15, 2011 @ 5:28 pm    

    Talking about lecture notes, I’ve been following the model of Robert Ghrist (http://www.math.upenn.edu/~ghrist/notes.html) for a while now. I write on a tablet PC in class (instead of writing on the board), polish to a small extend the scribes after the lectures, and post them as “class notes”. Of course, they’re not as professional as TeX-ed up notes, but they do save me a lot of time. They work okay even when I’m not following a prescribed textbook, e.g., here are the scribes from my graduate level course on integer optimization: http://www.math.wsu.edu/faculty/bkrishna/FilesMath567/S11/LecNotes/welcome.html.

RSS feed for comments on this post.

Sorry, the comment form is closed at this time.

© 2018 Glencora Borradaile   Powered by WordPress MU    Hosted by blogs.oregonstate.edu