CS 598 TMC, Fall 2018

Presentation and Project Guidelines


Present one paper on geometric approximation algorithms (20 minutes), in the last 2 classes (Dec 7 and 12). The format should be similar to a conference talk. Spend sufficient time on the introduction (problem statement, motivation, comparison of previous vs. new results). Then describe the key ideas of the new method(s). You will not have time to cover all the technical details; pick the part(s) you find most interesting. Point out connection (if any) with techniques we have seen from class. Close with open questions (from the paper, or which you think of yourself).


Due date: Dec 17 Monday.

Option 1: Write a report of about 10-12 pages (single-column, single-spaced), comparing 2 or more papers that address a common problem in geometric approximation algorithms. One of the papers may be the paper you have used for your presentation.

Begin with an introduction of the problem and a general survey. Then describe the key ideas of the new methods in your selected papers. Again, you are not supposed to explain all the technical details. Present your own (hopefully easier-to-understand) interpretation, in your own words (do not copy or just paraphrase the descriptions from the papers). Point out similarities and differences between the papers, and their strengths and weaknesses. Point out connections (if any) with techniques from class. Close with open questions, as well as your thoughts on future work and any ideas you may have regarding possible further improvements.

Option 2: do original research! This option is riskier, but even if you do not succeed in solving an open problem, you could still write a general survey of prior work, and explain your failed attempts, partial results on special cases, new variations of the problem, etc. in your report.

Option 3: implement some existing geometric approximation algorithms (from class or from papers) and report on your experimental results.

Send me an e-mail by Nov 7 Wednesday on your tentative proposed topic/papers.


Below are just some random examples. Feel free to find a topic/papers on your own, or ask me for advice.