I sometimes link to a preprint version for simplicity. You should search to see where it appeared
(e.g. conference and/or journal).

While this class has focussed primarily on polynomial-time algorithms for solving problems exactly,
there are many good project topics on approximation algorithms that require strong knowledge of
combinatorial optimization.

Max flows in O(nm) time, or better,
J. B. Orlin,
https://dspace.mit.edu/openaccess-disseminate/1721.1/88020
(even covering the previous work that gets faster algorithms than the Goldberg-Tarjan push relabel method we saw would be a good topic)

Perfect matchings in O(n log n) time in regular bipartite graphs,
A. Goel, M. Kapralov, and S. Khanna,
https://arxiv.org/abs/0909.3346

Faster shortest-path algorithms for planar graphs,
M. R. Henzinger, P. Klein, S. Rao, and S. Subramanian,
http://www.sciencedirect.com/science/article/pii/S0022000097914938

An O(n log n) algorithm for maximum st-flow in a directed planar graph,
G. Borradaile and P. Klein,
https://www.cs.princeton.edu/courses/archive/fall07/cos521/handouts/maxflowfull.pdf

Approximating undirected maximum flows in O(m polylog(n)) time,
R. Peng,
https://arxiv.org/abs/1411.7631
(you may need to consult some related work on "sparsifiers", but don't worry about going too deep with those details,
other related or even previous work would be a great project topic as well)

Finding small stabilizers for unstable graphs,
A. Bock, K. Chandrasekaran, J. Konemann, B. Pies, and L. Sanita,
http://www.math.uwaterloo.ca/~jochen/docs/stab_jour.pdf
(search Konemann's page for related papers on stabilizing graphs and network bargaining)

Entropy, Optimization, and Counting
M. Singh and N. Vishnoi,
https://arxiv.org/abs/1304.8108
It's a bit long, but focusing on key ideas would still make for a good presentation.

Computing maximum flow with augmenting electrical flows,
A. Madry,
https://people.csail.mit.edu/madry/docs/aug_flow.pdf

The multiplicative weights method and applications to linear programming, comb. opt.
Not a title, but see the following nice (but slightly incomplete)
paper by S. Arora, E. Hazan, and S. Kale for ideas on what to study
https://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf

Some appropriate approximation algorithms that have a strong foundation in CO:

From stars to comets: Improved local search for universal facility location,
J. Vygen
http://www.sciencedirect.com/science/article/pii/S0167637706001003
(many related "local search" papers would also be appropriate)

Approximating minimum-cost k-node connected subgraphs via independence-free graphs
J. Cheriyan and L. A. Vegh,
http://personal.lse.ac.uk/veghl/papers/cheriyan-vegh-connectivity.pdf
(again, many similar papers exist on robust network design via iterated rounding)

More to follow