Local Search Techniques
Instructors Anup Bhattacharya, Gopinath Mishra, and Arijit Ghosh
Description Recently, local search techniques have been used to obtain a number of important results, most notably the PTAS for k-means problem in fixed dimensions. In this lecture series, we will review some of these results. Roughly, we will have 8 to 10 lectures, with two introductory lectures in the beginning. We have compiled an initial list of papers of interest. Please feel free to suggest relevant papers in this area. Let us know if you want to volunteer to present any paper.
Prerequisites Undergraduate level Algorithms, Discrete Mathematics, and Probability Theory.
References
V. Cohen-Addad: A Fast Approximation Scheme for Low-Dimensional k-Means. SODA, pp. 430-440, 2018. [DOI, arXiv]
V. Cohen-Addad and C. Schwiegelshohn: On the Local Structure of Stable Clustering Instances. FOCS, pp. 49-60, 2017. [DOI, arXiv]
V. Cohen-Addad and C. Mathieu: Effectiveness of Local Search for Geometric Optimization. SoCG, pp. 329-343, 2015. [DOI]
V. Cohen-Addad, A. de Mesmay, E. Rotenberg and A. Roytman: The Bane of Low-Dimensionality Clustering. SODA, pp. 441-456, 2018. [DOI, arXiv]
N. Bus, S. Garg, N. H. Mustafa, and S. Ray: Limits of Local Search: Quality and Efficiency. Discrete & Computational Geometry, 57(3): 607–624, 2017. [DOI, Draft]
D. Antunes, C. Mathieu, and N. H. Mustafa: Combinatorics of Local Search: An Optimal 4-Local Hall’s Theorem for Planar Graphs. ESA, pp. 48:1-48:10, 2017. [DOI]
N. H. Mustafa and S. Ray: Improved Results on Geometric Hitting Set Problems. Discrete & Computational Geometry, 44(4): 883–895, 2010.. [DOI, Draft]
U. Feige, V. S. Mirrokni, J. Vondrák: Maximizing Non-monotone Submodular Functions. SIAM Journal on Computing, 40(4): 1133-1153, 2011. [DOI, Draft]
V. Cohen-Addad, P. N. Klein, and C. Mathieu: Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics. FOCS, pp. 353-364, 2016. [DOI, arXiv]
A. Cevallos, F. Eisenbrand, and R. Zenklusen: Local Search for Max-Sum Diversification. SODA, pp. 130-142, 2017. [DOI, arXiv]
V. V. S. P. Bhattiprolu and S. Har-Peled: Separating a Voronoi Diagram via Local Search. SoCG, pp. 18:1-18:16, 2016. [DOI, arXiv]
D. P. Williamson and D. B. Shmoys: The Design of Approximation Algorithms. Cambridge Univ. Press, 2011. [LINK]
M. Groß, A. Gupta, A. Kumar, J. Matuschke, D. R. Schmidt, M. Schmidt, and J. Verschae: A Local-Search Algorithm for Steiner Forest. ITCS, volume 94, pp. 31:1-31:17, 2018. [DOI]
Lecture details
Topics covered in Lectures 1 and 2 (Lecturer: Arijit Ghosh)
A general overview of the lecture series.
Local search algorithms for Max-Cut and Maximising Submodular Functions.
Reading materials:
http://pages.cs.wisc.edu/~shuchi/courses/880-S07/scribe-notes/lecture07.pdf
https://courses.engr.illinois.edu/cs598csc/sp2011/Lectures/lecture_12.pdf
Read the following paper: Maximizing Non-Monotone Submodular Functions [Draft]
Topics covered in Lecture 3 (Lecturer: Anup Bhattacharya)
Local search algorithm for the k-Median Problem
Reading material:
Section 9.2 from Chapter 9 of "The Design of Approximation Algorithms" book by Williamson and Shmoys.
Topics covered in Lecture 4 (Lecturer: Anup Bhattacharya)
Bicriteria for k-Median problem in Euclidean space
Reading material:
Topics covered in Lecture 5 (Lecturer: Gopinath Mishra)
Local search algorithm for the hitting set problem on set systems induced by points and half-spaces in 3D.
Reading material:
Topics covered in Lectures 6 & 7 (Lecturer: Sameer Desai)
Quality and efficiency of (3,2)-local search algorithm for hitting set problems.
Reading material:
Topics covered in Lecture 8 (Lecturer: Dibyayan Chakraborty)
An Optimal 4-Local Hall’s Theorem for Planar Graphs
Reading material:
http://drops.dagstuhl.de/opus/volltexte/2017/7829/