Survey on the approximation techniques for network design and multiple tool milling problems

Abstract

Most of the optimization problems are known to be NP-hard. Designing approximation algorithms for these NP-hard problems is of great interest these days. In this dissertation, we present a survey of generalized approximation algorithms for various constrained forest problems. We first describe the Goemans and Williamson technique, which is a very general and elegant technique for designing approximation algorithms for constrained forest problems. As an application of this technique, we discuss Naveen Grimi's 2-approximation algorithm for the k-Minimum Spanning Tree problem in a more detailed way. We will also discuss further extensions to this algorithm to get a better approximation, by Sunil Arya & Ramesh Hariharan and later by Sanjeev Arora & George Karakostas.

Our intention behind describing the Goemans and Williamson’s technique is that we expect it will be a useful technique in designing approximation algorithms for the Multiple Tool Milling Problem. Only O(logn) factor approximations are known for this problem and the existence of constant factor approximation is an open problem. We will give a proof showing the generalized multiple tool milling problem is NP-complete. We will also design an exact algorithm for the multiple tool milling problem on a straight line. Then, we will provide a constant factor approximation algorithm for this straight-line version of the problem with the hope that the framework generalizes to other metric spaces. We have been unable to show this yet, but we propose an approach, based on the Goemans and Williamson technique, to design an approximation algorithm for the multiple tool milling problem on a tree.