Spring c Jon Kleinberg andÉva Tardos Much of the course is concerned with techniques for designing algorithms, and graphs will be a ubiquitous. Algorithm Design - John Kleinberg - Éva soundofheaven.info - Ebook download as PDF File .pdf), Text File .txt) or read book online. best instructor manual. These are a revised version of the lecture slides that accompany the textbook Algorithm Design by Jon Kleinberg and Éva Tardos. Here are the original and.
|Language:||English, Spanish, French|
|ePub File Size:||18.36 MB|
|PDF File Size:||16.14 MB|
|Distribution:||Free* [*Regsitration Required]|
Kleinberg, Jon. Algorithm design / Jon Kleinberg, Éva Tardos.—1st ed. p. cm. Includes bibliographical references and index. ISBN (alk. paper). 1. Kleinberg, Jon. Algorithm design / Jon Kleinberg, l~va Tardoslst ed. p. cm. Includes bibliographical references and index. ISBN (alk. paper). 1. Algorithm Analysis. Contribute to davie/CSAlgorithm-Analysis development by creating an account on GitHub.
It is known that. It is not hard to do this. This example illustrates a very common way in which a rtmning time of O n2 arises: Multiplying these two together. Chapter 8 NP and Computational Intractability. Given the schedule for each ship.
We include extensive coverage of each of these three approaches. Problems and Solved Exercises An important feature of the book is the collection of problems.
Across all chapters, the book includes over problems, almost a! We view the problems as a crucial component of the book, and they are structured in keeping with our overall approach to the material. Most of them consist of extended verbal descriptions of a problem arising in an application area in computer science or elsewhere out in the world, and part of the problem is to practice what we discuss in the text: We view a complete answer to one of these problems as consisting of all these components: To help with the process of working on these problems, we include in each chapter a section entitled "Solved Exercises," where we take one or more problems and describe how to go about formulating a solution.
The discussion devoted to each solved exercise is therefore significantly longer than what would be needed simply to write a complete, correct solution in other words,. This material can thus be treated either as a review or as new material; by including it, we hope the book can be used in a broader array of courses, and with more flexibility in the prerequisite knowiedge that is assumed. In keeping with the approach outlined above, we develop the basic algorithm design techniques by drawing on problems from across many areas of computer science and related fields.
To mention a few representative examples here, we include fairly detailed discussions of applications from systems and networks caching, switching, interdomain routing on the Internet , artificial.
Pedagogical Features and Supplements In addition to the Problems and solved exercises. It begins with an informal overview of what it means for a problem to be computationally tractable.
It then discusses growth rates of functions and asymptotic analysis more formally. In cases where extensions to the problem or further analysis of the algorithm is pursued. The remainder of Chapter 1 discusses a list of five "representative problems" that foreshadow topics from the remainder of the course. As noted earlier.
In particular. We begin immediately with the Stable Matching Problem. To reflect this style. Chapter-by-Chapter Synopsis Chapter I starts by introducing some representative algorithmic problems. The fact that closely related problems can vary greatly in complexity is an important theme of the book. A number of supplements are available in support of the book itself. For instructions on obtaining a professor. These files are available at wunv.
A set of lecture slides. In our undergraduate class. Comments and reports of errors can be sent to us by e-mail. These subsections are highlighted in the text with an icon depicting a feather. It is worth mentioning two points concerning the use of these problems as homework in a course.
Chapter 3 covers the basic definitions and algorithmic primitives needed for working with graphs. The goal of this structure is to offer a relatively uniform style of presentation that moves from the initial discussion of a problem arising in a computing application through to the detailed analysis of a method to solve it.
Chapter 2 introduces the key mathematical definitions and notations used for analyzing algorithms. Our approach to data structures is to introduce them as they are needed for the implementation of the algorithms being developed in the book.
To the extent that network flow is covered in algorithms courses. When we use the book at the undergraduate level. Our chapter on approximation algorithms discusses both the process of designing effective algorithms and the task of understanding the optimal solution well enough to obtain good bounds on it.
Next we develop dynamic programming by starting with the recursive intuition behind it. We also consider types of computational hardness beyond NPcompleteness. Chapters 8 and 9 cover computational intractability. This chapter concludes with some of the main applications of greedy algorithms. This chapter concludes with extended discussions of the dynamic programming approach to two fundamental problems: Preface Preface Chapters 2 and 3 also present many of the basic data structures that will be used for implementing algorithms throughout the book.
We devote most of our attention to NP-completeness. Chapters 4 through 7 cover four major algorithm design techniques: As design techniques for approximation algorithms. Use of the Book The book is primarily designed for use in a first undergraduate course on algorithms. Our goal here is to provide a more compact introduction to some of the ways in which students can apply randomized techniques using the kind of background in probability one typically gains from an undergraduate discrete math course.
This is a topic on which several nice graduate-level books have been written. Our chapter on tractable special cases emphasizes that instances of NP-complete problems arising in practice may not be nearly as hard as worst-case instances. We build up to some fairly complex proofs of NPcompleteness. Chapter 13 covers the use of randomization in the design of algorithms. This topic is often missing from undergraduate algorithms courses. Chapters 10 through 12 cover three maior techniques for dealing with computationally intractable problems: For divide and conquer.
We illustrate how NP-complete problems are often efficiently solvable when restricted to tree-structured inputs. While this topic is more suitable for a graduate course than for an undergraduate one. With greedy algorithms. Aravind Srinivasan. Leonid Meyerguz. Siddharth Alexander. Joe Polastre. Steve Baker. Chapter Mike Priscott. We thank our undergraduate and graduate teaching assistants.
We skip the starred sections. Shan-Leung Maverick Woo. Our own undergraduate course involves material from all these chapters. Nadya Travinin.
Tina Nolte. Sections Shanghua Teng. Justin Yang. Many of them have provided valuable insights. Matthew Wachs. Ara Hayrapetyan. John Bicket. Amit Kumar.
The book also naturally supports an introductory graduate course on algorithms. We also tend to skip one or two other sections per chapter in the first half of the book for example.
Jon Peress. Sebastian Sllgardo. David Richardson. Bill McCloskey. Sasha Evfimievski. Dexter Kozen.! This last point is worth emphasizing: Mike Connor. Dieter van Melkebeek. Yeongwee Lee. John Hopcroft. Dexter Kozen. Ralph Benzinger. Tim Roughgarden. Preface Preface might be able to use particular algorithm design techniques in the context of their own work. Lars Backstrom. Yuval Rabani. Although our focus in an introductory graduate course is on the more advanced sections.
Monika Henzinger. For this type of course. Alexander Druyan. Allan Borodin. Paul Beame. Venu Ramasubramanian. Tom Wexler. Gene Kleinberg. Travis Ortogero. Igor Kats. Matt Piotrowski. Brian Kulis. Chris Jeuell. Here we find the emphasis on formulating problems to be useful as well. Ashwin Machanavajjhala. Henry Lin. Rachit Siamwalla. Mike Molloy. Shaddin Doghmi. Chapters excluding 4. Xin Qi. Rie Ando. We cover roughly half of each of Chapters The resulting syllabus looks roughly as follows: Chapter 1.
Doug Burdick. A number of graduate students and colleagues have used portions of the book in this way. Ayan Mandal.
Chaitanya Swamy. Kevin Wayne. Alex Slivkins. We also thank all the students in these classes who have provided comments and feedback on early drafts of the book over the years. Vladimir Dizhoor. Chapter 9 briefly. Brian Sabino. Our view of such a course is that it should introduce students destined for research in all different areas to the important current themes in algorithm design. Bowei Du. For the past several years. Devdatt Dubhashi. These courses have grown.
David Kempe. Ronitt Rubinfeld. Elliot Anshelevich. Sergei Vassilvitskii. Niranjan Nagarajan. Evan Moran. Alexa Sharp. Alexei Kopylov. More generally. Aditya Rao. Perry Tam. It was probably iust in our imaginations. Jon Kleinberg gva Tardos Ithaca. Many of these contributions have undoubtedly escaped our notice. Bart Selman. Duncan Watts. Lillian Lee. Dan Huttenlocher. Mark Newman. Baltimore County. Edgar Ramos University of Illinois.
We thank Anselm Blumer Tufts University. It has been a pleasure working with Addison Wesley over the past year. Leon Reznik Rochester Institute of Technology. Maite Suarez-Rivas at Addison Wesley. Dieter van Melkebeek University of Wisconsin.
Stephan Olariu Old Dominion University. First and foremost. Sanjeev Khanna University of Pennsylvania.
Sariel Har-Peled University of Illinois. Sanjay Ranka University of Florida. David Shmoys. Patty Mahtani. Ted Laux for the indexing. Marilyn Lloyd. Nancy Murphy of Dartmouth Publishing for her work on the figures. Prabhakar Raghavan. We thank Matt and Susan. This book was begun amid the irrational exuberance of the late nineties.
We appreciate their support. We deeply appreciate their input and advice. Evie Kleinberg. Richard Chang University of Maryland. Philip Klein Brown University. We thank Joyce Wells for the cover design. We would like to additionally thank Kevin Wayne for producing supplementary material associated with the book. Kevin Compton University of Michigan.
And so to all students of the subject. Bobby Kleinberg. David Matthias Ohio State University. Ron Elber. Our early conversations about the book with Susan Hartman were extremely valuable as well. In a number of other cases. David McAllester. Diane Cook University of Texas. We fln-ther thank Paul and Jacqui for their expert composition of the book. Michael Mitzenmacher Harvard University. Olga Veksler. Each applicant has a preference ordering on companies.
The crux of the application process is the interplay between two different types of parties: The problem itself--the Stable Matching Problem--has several origins. The algorithm to solve the problem is very clean as well. Stable Matching As an opening topic.
Could one design a college admissions process. What did they mean by this? To set up the question. It is motivated by some very natural and practical concerns. Based on these preferences. In this case. If this holds.
The world of companies and applicants contains some distracting asymmetries. CluNet offers a job to one of its wait-listed applicants. And from the point of view of this book. Before doing this. We might well prefer the following. Gale and Shapley proceeded to develop a striking algorithmic solution to this problem.
But in this case. It turns out that for a decade before the work of Gale and Shapley. Matching Gale and Shapley considered the sorts of things that could start going wrong with this process. Suddenly down one summer intern. Rai actually prefers WebExodus to CluNet--won over perhaps by the laid-back. Following Gale and Shapley. Consider another student.
What has gone wrong? One basic problem is that the process is not self-enforcing--if people are allowed to act in their self-interest. Things look just as bad. It is useful. A few days later. Situations like this can rapidly generate a lot of chaos. Formulating the Problem To get at the essence of this concept. A First Problem: We will see that doing this preserves the fundamental issues inherent in the problem. This is motivated by related applications.
So this is the question Gale and Shapley asked: Given a set of preferences among employers and applicants. Each applicant is looking for a single company. Some Representative Problems 1. Guided by our initial motivation in terms of employers and applicants. A matching S is a set of ordered pairs. We will refer to the ordered ranking of m as his preference list.
On the other hand. Given a perfect matching S. There is a unique stable matching here. Can we declare immediately that m. There are two pairs m. Some Examples To illustrate these definitions. The preference lists are as follows: Both m and Iv would want to leave their respective partners and pair up..
Iv would form an instability with respect to this matching. The other perfect matching. We wil! Let us consider some of the basic ideas that.. Let M x W denote the set of all possible ordered pairs of the form m. Iv wii1 be one of the pairs in our final stable matching?
Not necessarily: Suppose an unmarried man m chooses the woman Iv who ranks highest on his preference list and proposes to her. Each woman.. Two questions spring immediately to mind: Does there exist a stable matching for every set of preference lists? Given a set of preference lists. Now we can add the notion of preferences to this setting.
If we think about this set of preference lists intuitively. Some Representative Problems!. Matchings and perfect matchings are objects that will recur frequently throughout the book. Figure 1. The matching consisting of the pairs m.
Iv and m. In this second example. In the present situation. Our goal.. Here is a concrete description of the Gale-Shapley algorithm. For a while. He is free until he proposes to the highest-ranked woman on his list. An arbitrary flee man m chooses the highest-ranked woman w to whom he has not yet proposed. As time goes on. In the case of the present algorithm. A useful strategy for upper-bounding the running time of an algorithm.
If w is also free. Then a man m may propose to her. Now we show that the algorithm terminates. We proceed to prove this now.
But there are only n2 possible pairs of men and women in total. So a natural idea would be to have the pair m. So we discover the following. The view of a man m during the execution of the algorithm is rather different.
It follows that there can be at most n2 iterations. The next step could look like this. Then by 1. Now we ask: At termination. Let us suppose that the algorithm terminates with a flee man m.! But there are only n men total. So the main thing we need to show is the following.
This example shows a certain "unfairness" in the G-S algorithm. And in larger examples. Why is this not immediately obvious? Suppose there comes a point when m is flee but has already proposed to every woman. If he did. We have already seen. We now consider some further questions about the behavior of the G-S algorithm and its relation to the properties of different stable matchings. Since the set of engaged pairs forms a matching. It follows that S is a stable matching. Stable Matching 9 iteration.
For example. As defined earlier. So this simple set of preference lists compactly summarizes a world in which someone is destined to end up unhappy: The set S is a stable matching. The set of engaged pairs always forms a matching. To recap. Let us now establish that the set S returned at the termination of the algorithm is in fact a perfect matching.
But this contradicts 1. Let us suppose. Recall that this is true if all men prefer different women. Different choices specify different executions of the algprithm. Stable Matching 11 To begin With. We will say that iv is the best valid partner of m if iv is a valid parmer of m. For a woman w. Despite all this. This statement is surprising at a number of levels. In the present context. Since iv is a valid parmer of m. But either way. We will prove the folloWing fact. We will use best m to denote the best valid partner of m.
All Executions Yield the Same Matching There are a number of possible ways to prove a statement such as this. So consider the first moment during the execution g in which some man.
It turns out that the easiest and most informative approach for us will be to uniquely characterize the matching that is obtained and then show that al! After all. Suppose there were a pair m.
First of all. Do all executions of the G-S algorithm yield the same matching? This is a genre of question that arises in many settings in computer science: We say that m is the ivorst valid partner of iv if m is a valid partner of w. What is the characterization? Since men propose in decreasing order of preference. To consider a very different kind of example.
Since he proposed in decreasing order of preference. And finally. The goal is to maximize the number of requests accepted. E --a collection V of nodes and a collection E of edges. G consists of a pair of sets V. This high-level strategy is carried out in practice with the help of a few fundamental design techniques.
The goal is to select a compatible subset of requests of maximum possible size. Two requests i andj are compatible if the requested intervals do not overlap: To talk about some of them.
We illustrate an instance of this Interual Scheduling Problem in Figure 1. We typica! You have a resource-. The problems are self-contained and are al! As in any area. Note that there is a single compatible set of size 4. For the discussion here. A scheduler wants to accept a subset of these requests.
The first three will be solvable efficiently by a sequence of increasingly subtle algorithmic techniques. To get this discussion started. A request takes the form: Can I reserve the resource starting at time s. For many problems. We will assume that the resource can be used by at most one person at a time. Interval Scheduling Consider the following very simple scheduling problem.
But from this it follows that m. While graphs are a common topic in earlier computer Figure 1. More formally. In the spring. A perfect matching in this graph consists of an assignment of each professor to a course that he or she can teach.
We can express these concepts more generally in terms of graphs. But notice. We will find that the algorithmic techniques discussed earlier do not seem adequate. M is a perfect matching if every node appears in exactly one edge of M. So any algorithm for this problem must be very sensitive to the values. A perfect matching is then a way of assigning each job to a machine that can process it. In other words. Do you see it? Matchings in bipartite graphs can model situations in which objects are being assigned to other objects.
A bipartite graph is pictured in Figure 1. We typically learn something about the structure of the underlying problem from the fact that such a simple approach can be optimal. When a greedy algorithm can be shown to find an optimal solution for al! There appears to be no simple greedy rule that walks through the intervals one at a time. We say that a graph G Some Representative Problems We will see shortly that this problem can be solved by a very natural algorithm that orders the set of requests according to a certain heuristic and then "greedily" processes them in one pass.
To see that this does capture the same notion we encountered in the Stable Matching Problem. Y is the set of offered courses. This will be.
We then defined a perfect matching to be a matching in which every man and every woman belong to some pair. In the case of bipartite graphs. Our goal will be to find a compatible subset of intervals of maximum total value. Thus the Bipartite Matching Problem is the following: Given an arbitrary bipartite graph G. Some Representative Problems The Independent Set Problem encodes any situation in which you are trying to choose from among a collection of objects and there are pairwise conflicts among some of the objects.
No efficient algorithm is known for any of them. Who will win?
There is. The Independent Set Problem is. First JavaPlanet opens a franchise. E in which the nodes are the intervals and there is an edge between each pair of them that overlap..
This is simply the largest independent set in the graph whose nodes are your friends. Competitive Facility Location Finally. Is there anything good we can say about the complexity of the Independent Set Problem? One positive thing is the following: If we have a graph G on 1. The current status of Independent Set is this: While it is not complicated to check this.
Each zone i has a 2 For those who are curious. For Interval Scheduling. The graph in Figure 1. Given the generality of the Independent Set Problem. We will see later in the book that Independent Set is one of a large class of problems that are termed NP-compIete.
Say you have n friends. It is possible that this is close to the best we can do on this problem. Bipartite Matching.
We simply show you the graph G. Suppose they must deal with zoning regulations that require no two franchises be located too close together. This may look like a very basic observation--and it is--but it turns out to be crucial in understanding this class of problems.
The geographic region in question is divided into n zones. Given G. The obvious brute-force algorithm would try all subsets of the nodes.
Encoding Bipartite Matching as a special case of Independent Set is a little trickier to see. It would have to implicitly contain algorithms for Interval Scheduling. So there really seems to be a great difference in difficulty between checking that something is a large independent set and actually finding a large independent set. This process is called augmeritation. Everyone would rather marry any good person than any bad person.
They also prevent two franchises from being opened in the same zone. At all times. Suppose that for some number k. Each man has a preference list that ranks all the women. The notion of PSPACE-completeness turns out to capture a large collection of problems involving game-playing and planning.
One can work this out by looking at the figure for a while. It is now easy to identify an instability in M: Show that in every stable matching. There does not seem to be a short proof we could present. This is in contrast to the Independent Set Problem. What would it mean for the claim to be false? There would exist some stable matching M in which a good man m was married to a bad woman w. Solved Exercise 2 We can think about a generalization of the Stable Matching Problem in which certain man-woman pairs are explicitly forbidden..
So even if all of them were married to good women. In the case of employers and applicants. Solution A natural way to get started thinking about this problem is to assume the claim is false and try to work toward obtaining a contradiction.
This contradicts our assumption that M is stable. The set of all 2n people is divided into two categories: P2 will be able to select a set of nodes with a total value of at least B? We will call this an instance of the Competitive Facility Location Problem. Could it be the case that every good woman is married to a good man in this matching M? Thus our game consists of two players.. There are k good men and k good women.
Each is good. P1 and P2.
Using the analogy to marriage between men and women. Suppose that player P2 has a target bound B. Then P2 does have a winning strategy. Solved Exercise 1 Consider a town with n men and n women seeking to get married to one another. Location Problem. The difficulty. The usual kind of instability. Now we can ask: For every set of preference lists and every set of forbidden pairs.
To begin with. Here is the algorithm in full. We now prove that this yields a stable matching. In this more general setting. We also notice an additional pairs of facts. Resolve this question by doing one of the following two things: To do this. A single woman is more desirable and not forbidden. We will show that there is always a stable matching. Each man m ranks all th6 women w for which m. There are two single people with nothing preventing them from getting married to each other.
That turns out to be the case here. A single man is more desirable and not forbidden. Each show has a fixed rating. On the basis of this pair of schedules. T than it did with the pair S. We will assume that there were more students graduating than there were slots available in the m hospitals.
Here is the way we determine how well the two networks perform relative to each other. T is stable if neither network can unilaterally change its own schedule and win more time slots. There are n prime-time programming slots. A network wins a given time slot if the show that it schedules for the time slot has a larger rating than the show the other network schedules for that time slot.
Each hospital had a ranking of the students in order of preference. True or false? In every instance of the Stable Matching Problem. Gale and Shapley published their paper on the Stable Matching Problem in Suppose in the opening week of the fall season. There were m hospitals. If it is true. But for ra to be single. Our general definition of instability has four parts: This means that we have to make sure that none of the four bad things happens.
For every set of TV shows and ratings. Each network wants to devise a schedule--an assignment of each show to a distinct slot--so as to attract as much market share as possible. Consider an instance of the Stable Matching Problem in which there exists a man m and a woman w such that m is ranked first on the preference list of w and w is ranked first on the preference list of m.
There are many other settings in which we can ask questions related to some type of "stability" principle. There were n medical students graduating in a given year. If it is false. The goal of each network is to win as many time slots as possible. That is. Some Representative Problems Exercises Suppose we have two television networks. Then in every stable matching S for this instance. Decide whether you think the following statement is true or false. The Stable Matching Problem.
For safety reasons. With indifferences in the ranldngs. Algorithm Design introduces algorithms by looking at the real-world problems that motivate them. The book teaches students a range of design and analysis techniques for problems that arise in computing applications. The text encourages an understanding of the algorithm design process and an appreciation of the role of algorithms in the broader field of computer science.
Chapter 1 Introduction: Some Representative Problems. Chapter 2 Basics of Algorithm Analysis. Chapter 3 Graphs. Chapter 4 Greedy Algorithms. Chapter 5 Divide and Conquer. Chapter 6 Dynamic Programming. Chapter 7 Network Flow. Chapter 8 NP and Computational Intractability.
A Class of Problems beyond NP. Chapter 10 Extending the Limits of Tractability. Chapter 11 Approximation Algorithms. Chapter 12 Local Search.