Combinatorial Optimization: Exact and Approximate Algorithms Luca Trevisan Stanford University March 19, 2011 Foreword These are minimally edited lecture notes from the class CS261: Optimization and Algorith- mic ParadigmsthatItaughtatStanfordintheWinter2011term. Thefollowing18lectures cover topics in approximation algorithms, exact optimization, and online algorithms. I gratefully acknowledge the support of the National Science Foundation, under grant CCF 1017403. Any opinions, findings and conclusions or recommendations expressed in these notesaremyownanddonotnecessarilyreflecttheviewsoftheNationalScienceFoundation. Luca Trevisan, San Francisco, March 19, 2011. (cid:13)c 2011 by Luca Trevisan This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License. To view a copy of this license, visit http://creativecommons.org/ licenses/by-nc-nd/3.0/ or send a letter to Creative Commons, 171 Second Street, Suite 300, San Francisco, California, 94105, USA. i ii Contents Foreword i 1 Introduction 1 1.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 The Vertex Cover Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.2 The Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2 Steiner Tree Approximation 7 2.1 Approximating the Metric Steiner Tree Problem . . . . . . . . . . . . . . . 7 2.2 Metric versus General Steiner Tree . . . . . . . . . . . . . . . . . . . . . . . 10 3 TSP and Eulerian Cycles 13 3.1 The Traveling Salesman Problem . . . . . . . . . . . . . . . . . . . . . . . . 13 3.2 A 2-approximate Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.3 Eulerian Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.4 Eulerian Cycles and TSP Approximation . . . . . . . . . . . . . . . . . . . 19 4 TSP and Set Cover 21 4.1 Better Approximation of the Traveling Salesman Problem . . . . . . . . . . 21 4.2 The Set Cover Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 4.3 Set Cover versus Vertex Cover . . . . . . . . . . . . . . . . . . . . . . . . . 29 5 Linear Programming 31 5.1 Introduction to Linear Programming . . . . . . . . . . . . . . . . . . . . . . 31 5.2 A Geometric Interpretation . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 5.2.1 A 2-Dimensional Example . . . . . . . . . . . . . . . . . . . . . . . . 32 iii iv CONTENTS 5.2.2 A 3-Dimensional Example . . . . . . . . . . . . . . . . . . . . . . . . 34 5.2.3 The General Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 5.2.4 Polynomial Time Algorithms for LInear Programming . . . . . . . . 37 5.2.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 5.3 Standard Form for Linear Programs . . . . . . . . . . . . . . . . . . . . . . 39 6 Linear Programming Duality 41 6.1 The Dual of a Linear Program . . . . . . . . . . . . . . . . . . . . . . . . . 41 7 Rounding Linear Programs 47 7.1 Linear Programming Relaxations . . . . . . . . . . . . . . . . . . . . . . . . 47 7.2 The Weighted Vertex Cover Problem . . . . . . . . . . . . . . . . . . . . . . 48 7.3 A Linear Programming Relaxation of Vertex Cover . . . . . . . . . . . . . . 50 7.4 The Dual of the LP Relaxation . . . . . . . . . . . . . . . . . . . . . . . . . 51 7.5 Linear-Time 2-Approximation of Weighted Vertex Cover . . . . . . . . . . . 52 8 Randomized Rounding 57 8.1 A Linear Programming Relaxation of Set Cover . . . . . . . . . . . . . . . . 57 8.2 The Dual of the Relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 9 Max Flow 65 9.1 Flows in Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 10 The Fattest Path 73 10.1 The “fattest” augmenting path heuristic . . . . . . . . . . . . . . . . . . . . 74 10.1.1 Dijkstra’s algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 10.1.2 Adaptation to find a fattest path . . . . . . . . . . . . . . . . . . . . 76 10.1.3 Analysis of the fattest augmenting path heuristic . . . . . . . . . . . 77 11 Strongly Polynomial Time Algorithms 79 11.1 Flow Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 11.2 The Edmonds-Karp Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 81 12 The Push-Relabel Algorithm 83 12.1 The Push-Relabel Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 12.2 Analysis of the Push-Relabel Algorithm . . . . . . . . . . . . . . . . . . . . 85 CONTENTS v 12.3 Improved Running Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 13 Edge Connectivity 91 13.1 Global Min-Cut and Edge-Connectivity . . . . . . . . . . . . . . . . . . . . 91 13.1.1 Reduction to Maximum Flow . . . . . . . . . . . . . . . . . . . . . . 93 13.1.2 The Edge-Contraction Algorithm . . . . . . . . . . . . . . . . . . . . 94 14 Algorithms in Bipartite Graphs 99 14.1 Maximum Matching in Bipartite Graphs . . . . . . . . . . . . . . . . . . . . 100 14.2 Perfect Matchings in Bipartite Graphs . . . . . . . . . . . . . . . . . . . . . 102 14.3 Vertex Cover in Bipartite Graphs . . . . . . . . . . . . . . . . . . . . . . . . 104 15 The Linear Program of Max Flow 105 15.1 The LP of Maximum Flow and Its Dual . . . . . . . . . . . . . . . . . . . . 105 16 Multicommodity Flow 113 16.1 Generalizations of the Maximum Flow Problem . . . . . . . . . . . . . . . . 113 16.2 The Dual of the Fractional Multicommodity Flow Problem . . . . . . . . . 116 16.3 The Sparsest Cut Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 17 Online Algorithms 121 17.1 Online Algorithms and Competitive Analysis . . . . . . . . . . . . . . . . . 121 17.2 The Secretary Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 17.3 Paging and Caching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 18 Using Expert Advice 127 18.1 A Simplified Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 18.2 The General Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 18.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 Lecture 1 Introduction Inwhichwedescribewhatthiscourseisaboutandgiveasimpleexampleofanapproximation algorithm 1.1 Overview In this course we study algorithms for combinatorial optimization problems. Those are the type of algorithms that arise in countless applications, from billion-dollar operations to everyday computing task; they are used by airline companies to schedule and price their flights, by large companies to decide what and where to stock in their warehouses, by delivery companies to decide the routes of their delivery trucks, by Netflix to decide which movies to recommend you, by a gps navigator to come up with driving directions and by word-processors to decide where to introduce blank spaces to justify (align on both sides) a paragraph. In this course we will focus on general and powerful algorithmic techniques, and we will apply them, for the most part, to highly idealized model problems. Some of the problems that we will study, along with several problems arising in practice, are NP-hard, and so it is unlikely that we can design exact efficient algorithms for them. For such problems, we will study algorithms that are worst-case efficient, but that output solutions that can be sub-optimal. We will be able, however, to prove worst-case bounds to the ratio between the cost of optimal solutions and the cost of the solutions provided by our algorithms. Sub-optimal algorithms with provable guarantees about the quality of their output solutions are called approximation algorithms. The content of the course will be as follows: • Simple examples of approximation algorithms. We will look at approximation algo- rithms for the Vertex Cover and Set Cover problems, for the Steiner Tree Problem and for the Traveling Salesman Problem. Those algorithms and their analyses will 1 2 LECTURE 1. INTRODUCTION be relatively simple, but they will introduce a number of key concepts, including the importance of getting upper bounds on the cost of an optimal solution. • Linear Programming. A linear program is an optimization problem over the real numbers in which we want to optimize a linear function of a set of real variables subject to a system of linear inequalities about those variables. For example, the following is a linear program: maximize x +x +x 1 2 3 Subject to : 2x +x ≤ 2 1 2 x +2x ≤ 1 2 3 (A linear program is not a program as in computer program; here programming is used to mean planning.) An optimum solution to the above linear program is, for example, x = 1/2, x = 1, x = 0, which has cost 1.5. One way to see that it is an optimal 1 2 3 solution is to sum the two linear constraints, which tells us that in every admissible solution we have 2x +2x +2x ≤ 3 1 2 3 that is, x +x +x ≤ 1.5. The fact that we were able to verify the optimality of a 1 2 3 solution by summing inequalities is a special case of the important theory of duality of linear programming. A linear program is an optimization problem over real-valued variables, while this course is about combinatorial problems, that is problems with a finite number of discrete solutions. The reasons why we will study linear programming are that 1. Linearprogramscanbesolvedinpolynomialtime,andveryefficientlyinpractice; 2. All the combinatorial problems that we will study can be written as linear pro- grams, providedthatoneaddstheadditionalrequirementthatthevariablesonly take integer value. This leads to two applications: 1. If we take the integral linear programming formulation of a problem, we remove the integrality requirement, we solve it efficient as a linear program over the real numbers, and we are lucky enough that the optimal solution happens to have integer values, then we have the optimal solution for our combinatorial problem. For some problems, it can be proved that, in fact, this will happen for every input. 2. If we take the integral linear programming formulation of a problem, we remove the integrality requirement, we solve it efficient as a linear program over the real numbers, we find a solution with fractional values, but then we are able to “round” the fractional values to integer ones without changing the cost of the 1.2. THE VERTEX COVER PROBLEM 3 solution too much, then we have an efficient approximation algorithm for our problem. • Approximation Algorithms via Linear Programming. We will give various examples in which approximation algorithms can be designed by “rounding” the fractional optima of linear programs. • Exact Algorithms for Flows and Matchings. We will study some of the most elegant and useful optimization algorithms, those that find optimal solutions to “flow” and “matching” problems. • Linear Programming, Flows and Matchings. We will show that flow and matching problems can be solved optimally via linear programming. Understanding why will make us give a second look at the theory of linear programming duality. • Online Algorithms. An online algorithm is an algorithm that receives its input as a stream, and, at any given time, it has to make decisions only based on the partial amount of data seen so far. We will study two typical online settings: paging (and, in general, data transfer in hierarchical memories) and investing. 1.2 The Vertex Cover Problem 1.2.1 Definitions Given an undirected graph G = (V,E), a vertex cover is a subset of vertices C ⊆ V such that for every edge (u,v) ∈ E at least one of u or v is an element of C. In the minimum vertex cover problem, we are given in input a graph and the goal is to find a vertex cover containing as few vertices as possible. The minimum vertex cover problem is very related to the maximum independent set prob- lem. In a graph G = (V,E) an independent set is a subset I ⊆ V of vertices such that there is no edge (u,v) ∈ E having both endpoints u and v contained in I. In the maximum independent set problem the goal is to find a largest possible independent set. It is easy to see that, in a graph G = (V,E), a set C ⊆ V is a vertex cover if and only if its complement V −C is an independent set, and so, from the point of view of exact solutions, the two problems are equivalent: if C is an optimal vertex cover for the graph G then V −C is an optimal independent set for G, and if I is an optimal independent set then V −I is an optimal vertex cover. Fromthepointofviewofapproximation, however, thetwoproblemsarenotequivalent. We are going to describe a linear time 2-approximate algorithm for minimum vertex cover, that is an algorithm that finds a vertex cover of size at most twice the optimal size. It is known, however, that no constant-factor, polynomial-time, approximation algorithms can exist for the independent set problem. To see why there is no contradiction (and how the notion of approximation is highly dependent on the cost function), suppose that we have a graph with n vertices in which the optimal vertex cover has size .9·n, and that our algorithm 4 LECTURE 1. INTRODUCTION finds a vertex cover of size n−1. Then the algorithm finds a solution that is only about 11% larger than the optimum, which is not bad. From the point of view of independent set size, however, we have a graph in which the optimum independent set has size n/10, and our algorithm only finds an independent set of size 1, which is terrible 1.2.2 The Algorithm The algorithm is very simple, although not entirely natural: • Input: graph G = (V,E) • C := ∅ • while there is an edge (u,v) ∈ E such that u (cid:54)∈ C and v (cid:54)∈ C – C := C ∪{u,v} • return C We initialize our set to the empty set, and, while it fails to be a vertex cover because some edge is uncovered, we add both endpoints of the edge to the set. By the time we are finished with the while loop, C is such that for every edge (u,v) ∈ E, either u ∈ C or v ∈ C (or both), that is, C is a vertex cover. To analyze the approximation, let opt be the number of vertices in a minimal vertex cover, then we observe that • If M ⊆ E is a matching, that is, a set of edges that have no endpoint in common, then we must have opt ≥ |M|, because every edge in M must be covered using a distinct vertex. • The set of edges that are considered inside the while loop form a matching, because if (u,v) and (u(cid:48),v(cid:48)) are two edges considered in the while loop, and (u,v) is the one that is considered first, then the set C contains u and v when (u(cid:48),v(cid:48)) is being considered, and hence u,v,u(cid:48),v(cid:48) are all distinct. • If we let M denote the set of edges considered in the while cycle of the algorithm, and we let C be the set given in output by the algorithm, then we have out |C | = 2·|M| ≤ 2·opt out As we said before, there is something a bit unnatural about the algorithm. Every time we find an edge (u,v) that violates the condition that C is a vertex cover, we add both vertices u and v to C, even though adding just one of them would suffice to cover the edge (u,v). Isn’t it an overkill? Consider the following alternative algorithm that adds only one vertex at a time: