ORIE 7391: Topics in Mathematical Programming

Spring 2013


The course meets Fridays, 1:30-3:30, in Rhodes 261.

This course will read recent papers in combinatorial optimization, with a focus on approximation algorithms. Each student will be responsible for presenting 1-2 papers during the term. All attendees are responsible for reading the paper for the week.


Below are some of the papers that we might read for the semester.


Jan 25 Course organization.
Feb 1 No class.
Feb 8 David Shmoys An, Kleinberg, and Shmoys, Improving Christofides' Algorithm for the s-t Path TSP
Feb 15 Eoin and Ashwinkumar Li and Svensson, Approximating k-Median via Pseudo-Approximation
Feb 22 Daniel and Jake Nagarajan, Schieber, and Shachnai, The Euclidean k-Supplier Problem
Mar 1 James and Alice Sebő, Eight-Fifth Approximation for TSP Paths
Mar 8 No class.
Mar 15 No class.
Mar 22 No class.
Mar 29 Anna and VasilisMömke and Svensson, Approximating Graphic TSP by Matchings
Apr 5 No class.
Apr 12 Chaoxu and NimaRothvoß, A Simpler Proof for O(Congestion + Dilation) Packet Routing
Apr 19 Pat and Soroush Rothvoß, Approximating Bin Packing within O(log OPT loglog OPT) Bins
Apr 26 Lior and JerryBuchbinder, Feldman, Naor, and Schwartz, A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization
May 3 Hedyeh, Pooya, and RadVishnoi, A Permanent Approach to the Traveling Salesman Problem
May 7 Alex, Yang, and ChenLovett and Meka, Constructive Discrepancy Minimization by Walking on the Edges