Cut problems and their application to divide-and-conquer
David B. Shmoys · 1996
INTRODUCTION 5.1 One of the most important paradigms in the design and analysis of algorithms is the notion of a divide-and-conquer algorithm. Every undergraduate course on algorithms teaches this method as one of its staples: to solve a problem quickly, one carefully splits the problem into two subproblems, each substantially smaller than the original, recursively solves each of these, and then pieces together the solution to each part into the overall solution desired. This approach has also been used in the design of heuristics for NP-hard optimization problems, but until recently, the heuristics designed in this way were either too complicated to analyze, or had extremely poor performance guarantees. In one of the most important breakthroughs in the design and analysis of approximation algorithms in the past decade, Leighton and Rao [LR88, LR94] devised an elegant approach for using 1 2 CHAPTER 5 CUT PROBLEMS AND D