This wiki is for materials related to Samir Khuller's algorithms reading group. Anyone who attends the group is welcome to add related materials.
If you are going to give a talk, please add it to the list below and announce it a few days in advance on the mailing list.
- 2008-08-29: Jian presents a constant factor approximation for l-diversity clustering with outliers, improving on the algorithm from last week's paper.
- 2008-08-22: Jian presents "Approximation algorithms for a clustering problem motivated by anonymizing databases", which he submitted to ICDT 2009. Here is the draft submission.
- 2008-08-15: Matt presents Streaming algorithms for <math>k</math>-center clustering with outliers and with anonymity by Matt and Samir as practice for APPROX 2008. (Here are the revised slides used at the conference.) Samir goes over some parts of Peter's talk from last week in more detail. He also discusses the offline algorithm for <math>k</math>-center clustering with outliers but not the proof of correctness. Here is Matt's simplified proof of correctness.
- 2008-08-08: Peter presents An <math>O(\log^* n)</math> approximation algorithm for the asymmetric p-center problem by Panigrahy and Vishwanathan.
- 2008-08-01: Matt reviews and finishes A constant-factor approximation algorithm for the k-median problem by Charikar et al. (<math>(6+2/3)</math>-approximation algorithm using LP rounding); rounding summary table.
- 2008-07-25: Samir presents Improved approximation algorithms for uncapacitated facility location by Chudak (clustering and rounding); Jian's inequality.
- 2008-07-11: Martin and Mohammad present An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem (link doesn't work from Matt's home) by Byrka.
- 2008-07-03: Jian presents Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP by Jain and Mahdian.
- 2008-06-27: Sam presents A general approach for incremental approximation and hierarchical clustering by Lin, Nagarajan, Rajaraman, and Williamson.
- 2008-06-20: Mohammad presents the <math>k</math>-median chapter from Vazirani's book. We cover the basic primal-dual 3-approximation algorithm for facility location and a way to apply it to <math>k</math>-medians by searching for the facility cost (equal for each facility) that yields the desired number of open facilities and combining two nearby solutions if necessary.
- 2008-06-13: Samir presents Local search heuristics for <math>k</math>-median and facility location problems by Arya et al.
- 2008-06-06: Matt starts A constant-factor approximation algorithm for the k-median problem by Charikar et al. (<math>(6+2/3)</math>-approximation algorithm using LP rounding).