At the 2016 International Computer Symposium, held December 15-17, 2016 in Chiayi, Taiwan, Professor Emeritus Teofilo Gonzalez will give the opening keynote presentation titled, "Approximation Algorithms: Methodologies, Applications and Empirical Evaluation." The biennial symposium provides a forum for researchers, educators, and professionals to exchange their discoveries and practices, and to explore future trends and applications in computer technologies.
Approximation Algorithms: Methodologies, Applications and Empirical Evaluation
We discuss the basic methodologies to design approximation algorithms. These include: Restriction (structural and algorithmic), Relaxation (structural and numerical), Rounding, Transformation, Local Search, and Metaheuristics. As an example of a hybrid technique we apply the Restriction-Relaxation technique to design a set of algorithms for the problem of finding minimum edge-length corridors. We discuss several different design choices some of which provide constant ratio approximations, while others can be shown to allow for arbitrarily bad solutions. We outline the proof techniques to establish our results. An extensive empirical evaluation of our algorithms is discussed. Several open problems and the difficulty encountered when trying to solve them will be discussed.