CS 598 TMC, Fall 2018
Presentation and Project Guidelines
Presentation:
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).
Project:
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.
Suggestions/Examples:
Below are just some random examples. Feel free to find a topic/papers on your own, or ask me for advice.
- Arya and Mount (SODA'16) on approximate EMST with better epsilon-dependencies (open: can this be made dynamic?)
- Arya, da Fonseca, and Mount's
series of papers on approximate polytope membership queries (related to approximate nearest neighbor queries and epsilon-kernels)
-
Bringman, Cabello, and Emmerich (SoCG'18)
on a PTAS for choosing a subset of anchored boxes to maximize volume
- Chan et al.'13
on a problem about noncrossing drawing of matchings, using shifted quadtrees
(open: better than sqrt{n} approximation?)
- Bonamy et al. (FOCS'18) on a PTAS for
max
clique in disk graphs
- Bar-Yehuda et al. (ESA'10)
on vertex cover in rectangle intersection graphs
- Chuzhoy and Ene (FOCS'16)
on the latest quasi-PTAS for independent set in rectangle intersection graphs
(looks complicated)
- Agarwal and Pan (SoCG'14)
on improving the runtime of approximation algorithms for geometric set cover/hitting set
- Aronov et al.'18 on dominating sets for pseudo-disks
- Bonnet and Miltzow (SoCG'17) on
the art gallery problem (which can be viewed as a geometric set cover problem)
- Cohen-Addad et al. (FOCS'16)
on a PTAS for k-means and k-median clustering (via local search)
- Huang et al. (ESA'16)
on epsilon-kernels for "stochastic" point sets
- Badanidiyuru et al. (SoCG'12)
on geometric max coverage problems
- Arora and Chang'04
on quasi-PTAS for bounded-degree EMST (open: is there a PTAS?)
- Raghvendra and Wessels (SODA'18)
on minimum weight triangulation
- Euclidean minimum bipartite matching, e.g., Agarwal and Sharathkumar (STOC'14)
- Separator theorems on string graphs, e.g., Lee'17 and earlier papers by
Fox and Pach, and Matousek, with applications to independent sets
- Search for papers
with Google Scholar
- Browse through recent conferences
SoCG, SODA, FOCS, STOC, ICALP, ESA, WADS, SWAT, CCCG, ISAAC, COCOON, etc.,
with DBLP
- Check out latest papers on the arxiv
-
Note: many papers may have both a conference and a journal version; use
the more up-to-date journal version if available