description: NP-hard problem in combinatorial optimization
201 results
by William J. Cook · 1 Jan 2011 · 245pp · 12,162 words
we were mathematicians in need of a speedy computer, he looked us in the eye and warned, “You guys aren’t trying to solve that traveling salesman problem, are ya?" Quite a bit of foresight there. This was the first of many computers we ground to a halt, spending the better
…
that are very easy to solve and yet have far more candidate solutions than the number of ways to route a salesman. What sets the traveling salesman problem apart is the fact that despite decades of research by top applied mathematicians around the world, in general it is not known how
…
an efficient method or prove that this is impossible. The complexity question that is the subject of the Clay Prize is the Holy Grail of traveling-salesman-problem research and we may be far from seeing its resolution. But this is not to say mathematicians have thus far come away empty-
…
used to compute optimal or near-optimal tours for a host of applied models on a daily basis. One of the enduring strengths of the traveling salesman problem has been its remarkable success as an engine of discovery in applied mathematics and its fields of operations research and mathematical programming. And many
…
all, I thank my comrades David Applegate, Robert Bixby, and Vašek Chvátal, for over twenty years of fun and work toward unraveling part of the traveling salesman mystery. I also thank Michel Balinsky, Mark Baruch, Robert Bland, Sylvia Boyd, William Cunningham, Michel Goemans, Timothy Gowers, Nick Harvey, Keld Helsgaun, Alan Hoffman,
…
School of Industrial and Systems Engineering at Georgia Tech and the Department of Operations Research and Financial Engineering at Princeton University. My work on the traveling salesman problem is funded by grants from the National Science Foundation (CMMI-0726370) and the Office of Naval Research (N00014-09-1-0048), and by
…
Chicago, Illinois. Police officers Toody and Muldoon navigated Car 54 in a popular American television series. Their 33-city task is an instance of the traveling salesman problem, or TSP for short. In its general form, we are given a collection of cities and the distance to travel between each pair of
…
challenge had been circulating through the mathematics community since the mid-1930s. Its solution was reported in Newsweek.5 Finding the shortest route for a traveling salesman—starting from a given city, visiting each of a series of other cities, and then returning to his original point of departure—is more than
…
for treating the problem and impossibility results would also be valuable.’ —Merrill Flood, 1956.8 ‘I conjecture that there is no good algorithm for the traveling salesman problem.’ —Jack Edmonds, 1967.9 ‘In this paper we give theorems which strongly suggest, but do not imply, that these problems, as well as
…
many others, will remain intractable perpetually.’ —Richard Karp, 1972.10 Challenges The authors of these remarks are three giants of traveling-salesman research. Merrill Flood rallied support for the problem in the 1940s; more than anyone else, Flood is responsible for the emergence of the TSP as
…
It appears to have been discussed informally by mathematicians at mathematics meetings for many years. —George Dantzig, Ray Fulkerson, and Selmer Johnson, 1954.1 he traveling salesman problem is known far and wide, but the path it has taken to such mathematical prominence is somewhat obscure. For example, we cannot say for
…
both in the south of the state. 21 22 Chapter 2 person making the rounds. Timothy Spears’s book 100 Years on the Road: The Traveling Salesman in American Culture cites an 1883 estimate by Commercial Travelers Magazine of 200,000 traveling salesmen working in the United States, and a further estimate
…
the 1832 German handbook Der Handlungsreisende—Von einem alten Commis-Voyageur.3 The Commis-Voyageur describes the need for good tours.4 Business leads the traveling salesman here and there, and there is not a good tour for all occurring cases; but through an expedient choice and division of the tour
…
always to visit as many localities as possible without having to touch them twice. This is an explicit description of the TSP, made by a traveling salesman himself! The Commis-Voyageur book presents five routes through regions of Germany and Switzerland. Four of these routes include return visits to an earlier city
…
time. Numerous volumes written later in the century describe well-chosen routes in the United States, Britain, and other countries. The romantic image of the traveling salesman is captured, too, in stage, film, literature, Halle Sondershausen Leipzig Muehlhausen Dresden Eisenach Freiberg Chemnitz Salzungen Fulda Plauen Gelnhausen Frankfurt Hof Hanau Aschaffenburg Baireuth Bamberg
…
sciences. Two of the leading figures of the era did, however, explore aspects of the TSP, and they are rightly viewed as the grandfathers of traveling-salesman research. Graph Theory and the Bridges of Königsberg The great Leonhard Euler wrote the most important of all early mathematical papers describing touring problems. The
…
in the following passage from Dantzig, Fulkerson, and Johnson’s classic paper.19 Merrill Flood (Columbia University) should be credited with stimulating interest in the traveling-salesman problem in many quarters. As early as 1937, he tried to obtain near optimal solutions in reference to routing of school buses. Both Flood and
…
to RAND, coinciding with Flood’s relocation to California. Princeton University’s Harold Kuhn writes the following in a December 2008 e-mail letter. The traveling salesman problem was known by name around Fine Hall by 1949. For instance, it was one of a number of problems for which the RAND corporation
…
her contributions to the salesman provided the background for the RAND breakthrough several years later. Whence the TSP? In a 1949 research paper, Robinson uses “traveling salesman problem” in an offhand way, suggesting it was a familiar concept at the time. In fact, until a copy of the RAND prize list is
…
person to have this information, but unfortunately he does not, as he explained to Albert Tucker. “I don’t know who coined the peppier name Traveling Salesman Problem for Whitney’s problem, but that name certainly caught on, and the problem has turned out to be of very fundamental importance.” Whatever the
…
origin, except for small variations in spelling and punctuation, “traveling” versus “travelling,” “salesman” versus “salesman’s,” etc., by the mid-1950s the TSP name was in wide use, and the problem was beginning to pick up its notorious
…
t make it less interesting to me—just the other way around. —George Dantzig, 1986.1 he name itself announces the applied nature of the traveling salesman problem. This has surely contributed to a focus on computational issues, keeping the research topic well away from perils famously described in John von Neumann
…
13 cities in three weeks. When my publisher gave me the list of cities, I realized something amazing. I was actually going to live the Traveling Salesman Problem! I tried conveying my excitement to the publicity department, tried explaining to them the mathematical significance of all this, and how we could perhaps
…
a tour depends on the direction of travel. And More The areas of application we have described by no means exhaust the reach of the traveling salesman. Indeed, intriguing new uses for the model appear regularly in the applied mathematics literature. Successful projects that have been reported include the following:12 •
…
editor who went ahead and shifted the locations of the cities over to the 48 state capitals. The Discover caption is as follows. “The traveling salesman problem is one of math’s most enduring unsolved puzzles. Here’s the shortest route for a salesman—or 75 76 Chapter 4 Figure 4
…
). We were both keenly aware of the fact that, although the complete set of faces (or constraints) in the linear programming formulation of the Traveling Salesman Problem was enormous, if you could find an optimal solution to a relaxed problem with a subset of the faces that is a tour, then
…
you had solved the underlying Traveling Salesman Problem. What we need is a good understanding of how to work with the inequalities, that is, how to produce an inequality when it
…
to face the possibility that billions of cuts might be needed. —Alan Hoffman and Philip Wolfe, 1985.1 he linear-programming relaxations associated with the traveling salesman problem are wildly complex: the simplex method is no match for problems with constraints numbering in the billions. Fortunately, Dantzig, Fulkerson, and Johnson put
…
number, and thus the facets might too have a simple characterization. He writes: “At least we should hope they have, because finding a really good traveling salesman algorithm is undoubtedly equivalent to finding such a characterization.”22 This is a bold statement, but his insight was right on the money. Indeed, the
…
-cut. Their paper concludes with the optimistic note, “the problem with 2392 cities should not be the end of the ongoing saga of the symmetric traveling salesman.” Figure 8.6 Top: Optimal tour of a 2,392-hole printed circuit board. Bottom: Manfred Padberg and Giovanni Rinaldi, 1985. Courtesy of Manfred
…
do. We take a group of talented young people, and we expose them to the history and theory of some famous N P problem. The traveling salesman problem will do nicely. —Charles Sheffield, 1996.1 alesmen, lawyers, preachers, authors, and tourists have been plotting tours for years, not to mention all
…
some cases successfully capturing the mathematical essence that has brought so much attention to the salesman. W Julian Lethbridge I was delighted to discover the Traveling Salesman paintings by Julian Lethbridge. Lethbridge is a celebrated contemporary artist, whose work is included in collections of the National Gallery of Art in Washington,
…
York Times, 1995.2 Lethbridge’s abstraction is cerebral, often based on mathematical or natural principles. —ULAE, 1997.3 200 Chapter 11 Figure 11.1 Traveling Salesman, Julian Lethbridge, 1995, lithograph, 43.75 × 42 inches. Image courtesy of Julian Lethbridge and United Limited Art Editions. His vocabulary often originates from random
…
of his artwork, but moved quickly to general mathematics, where Lethbridge has interest in, and intuition for, the aesthetics of our discipline. When discussing his Traveling Salesman series, Lethbridge explained that he came upon a description of the TSP in a journal and was struck immediately by the economy of thought and
…
compare these to the map paintings of Jasper Johns and to Jean Dubuffet’s Compagnie Fallacieuse.6 Such references would be Aesthetics Figure 11.2 Traveling Salesman 4, Julian Lethbridge, 1995, oil on linen, 72 × 72 inches. The Robert and Jane Meyerhoff Collection, photograph by Adam Reich. disappointing to fans of
…
and music. Concerning his TSP pieces, Galanter made the following comments in an introduction to his work at an exhibition in Lima, Peru.10 The Traveling Salesman mural series explores emergence in a different way. The design for each mural is uniquely generated for each specific wall. A large number of random
…
even philosophy. It is no wonder that the interplay of these activities displays some affinity to artistic works. We can express similar feelings for the traveling salesman problem, and hope to see further connections between the TSP and art, as progress is made in understanding the problem’s fundamental complexity. 12:
…
he beauty of the TSP will no doubt continue to attract mathematicians and computer scientists for years to come. Christos Papadimitriou told me that the traveling salesman problem is not a problem, it’s an addiction. —Jon Bentley, 1991.2 It’s addictive. No matter how much progress you make, you
…
the study of the TSP, both with an eye on the million-dollar complexity prize and on the practical, step-by-step, computational attack. The traveling salesman problem is as tough as it gets, but, as Rashers Ronald would say, bash on regardless. Notes Chapter 1. Challenges 1. IBM Corporation press
…
release from January 2, 1964, describing a new computer program for solving small instances of the traveling salesman problem. The computer program was developed by Michael Held, Richard Karp, and Richard Shareshian. 2. Menger (1931). 3. T0P500 Supercomputer List, June 2009. 4.
…
software/TSPLIB95/. http://www2.research.att.com/∼dsj/chtsp/about.html. Johnson, D. S., L. A. McGeogh. 2002. In: G. Gutin, A. Punnen, eds. The Traveling Salesman Problem and Its Variations. Kluwer, Boston, MA. 369–443. http://www.tsp.gatech.edu/vlsi/index.html. http://www.tsp.gatech.edu/world/countries.html
…
is, a onedimensional plane. Grötschel, M., M. W. Padberg. 1979. Math. Program. 16, 265–80. Naddef, D. 2002. In: G. Gutin, A. Punnen, eds. The Traveling Salesman Problem and Its Variations. Kluwer, Boston, Massachusetts. 29–116. Schrijver, A. 2002. Math. Program. 91, 437–45. The subtour inequality for S is identical to
…
The father of linear programming. The College Mathematics Journal 17, 293–314. [2] Applegate, D. L., R. E. Bixby, V. Chvátal, W. Cook. 2006. The Traveling Salesman Problem: A Computational Study. Princeton University Press, Princeton, New Jersey. [3] Arora, S., B. Barak. 2009. Computational Complexity: A Modern Approach. Cambridge University Press, New
…
D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco, California. [13] Gomory, R. E. 1966. The traveling salesman problem. Proceedings of the IBM Scientific Computing Symposium on Combinatorial Problems. IBM, White Plains, New York. 93–121. [14] Grötschel, M., O. Holland. 1991. Solution
…
D.C. [25] Schrijver, A. 2003. Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin, Germany. [26] Spears, T. B. 1994. 100 Years on the Road: The Traveling Salesman in American Culture. Yale University Press, New Haven, Connecticut. Index Aaronson, Scott, 189 Adams, Douglas, 178 Adleman, Leonard, 184–186 Agarwala, Richa, 50 algorithm, 6
by Brian Christian and Tom Griffiths · 4 Apr 2016 · 523pp · 143,139 words
. Though he is largely unheard of outside mathematics, Flood’s influence on computer science is almost impossible to avoid. He’s credited with popularizing the traveling salesman problem (which we discuss in more detail in chapter 8), devising the prisoner’s dilemma (which we discuss in chapter 11), and even with possibly
…
“the delivery drone problem.” But like the secretary problem, it emerged in the mid-twentieth century, a period unmistakably evoked by its canonical name: “the traveling salesman problem.” The problem of route planning didn’t get the attention of the mathematics community until the 1930s, but then it did so with a
…
grew in notoriety. Many of the greatest minds of the time obsessed over it, and no one seemed able to make real headway. In the traveling salesman problem, the question isn’t whether a computer (or a mathematician) could find the shortest route: theoretically, one can simply crank out a list of
…
until they happen to land in order. The question is: is there any hope of doing better? Decades of work did little to tame the traveling salesman problem. Flood, for instance, wrote in 1956, more than twenty years after first encountering it: “It seems very likely that quite a different approach from
…
also be valuable.” Another decade later, the mood was only more grim. “I conjecture,” wrote Jack Edmonds, “that there is no good algorithm for the traveling salesman problem.” These words would prove prophetic. Defining Difficulty In the mid-1960s, Edmonds, at the National Institute of Standards and Technology, along with Alan Cobham
…
the difficulty of a problem. And some problems are just … hard. Where does this leave the traveling salesman problem? Curiously enough, we are still not quite sure. In 1972, Berkeley’s Richard Karp demonstrated that the traveling salesman problem is linked to a controversially borderline class of problems that have not yet been definitively
…
those problems—making them effectively intractable—and most computer scientists believe that there aren’t any to be found. So the “impossibility result” for the traveling salesman problem that Flood imagined in the 1950s is likely to be its ultimate fate. What’s more, many other optimization problems—with implications for everything
…
constraints back in. That is, they make the problem temporarily easier to handle before bringing it back to reality. For instance, you can relax the traveling salesman problem by letting the salesman visit the same town more than once, and letting him retrace his steps for free. Finding the shortest route under
…
think of the minimum spanning tree as the fewest miles of road needed to connect every town to at least one other town. The shortest traveling salesman route and the minimum spanning tree for Lincoln’s judicial circuit are shown below.) As it turns out, solving this looser problem takes a computer
…
on the reality. If we calculate that the spanning tree distance for a particular set of towns is 100 miles, we can be sure the traveling salesman distance will be no less than that. And if we find, say, a 110-mile route, we can be certain it is at most 10
…
are to the real answer even without knowing what it is. Figure 8.1 The shortest traveling salesman route (top) and minimum spanning tree (bottom) for Lincoln’s 1855 judicial circuit. Even better, in the traveling salesman problem it turns out that the minimum spanning tree is actually one of the best starting points
…
from which to begin a search for the real solution. Approaches like these have allowed even one of the largest traveling salesman problems imaginable—finding the shortest route that visits every single town on Earth—to be solved to within less than 0.05% of the (unknown
…
real-world implications for everything from city planning and disease control to the cultivation of athletic rivalries. Uncountably Many Shades of Gray: Continuous Relaxation The traveling salesman problem, like Meghan Bellows’s search for the best seating arrangement, is a particular kind of optimization problem known as “discrete optimization”—that is, there
…
even at a steep cost—problems become tractable that weren’t tractable before. Lagrangian Relaxations are a huge part of the theoretical literature on the traveling salesman problem and other hard problems in computer science. They’re also a critical tool for a number of practical applications. For instance, recall Carnegie Mellon
…
itself to be a powerful weapon for solving discrete optimization problems, like assembling the calendar for NCAA basketball or finding the shortest route for a traveling salesman. In the previous chapter we saw how relaxation can play a big role in cutting such problems down to size, but the tactical use of
…
has emerged as an arguably even more important technique. Imagine you’re putting together a globe-trotting ten-city vacation, your own version of the traveling salesman problem: you’ll start and finish in San Francisco and visit Seattle, Los Angeles, New York, Buenos Aires, London, Amsterdam, Copenhagen, Istanbul, Delhi, and Kyoto
…
instance, always doing the shortest job available, without looking or planning beyond—can sometimes be all that a problem requires. In this case, for the traveling salesman problem, the solution given by the greedy algorithm probably isn’t terrible, but it’s likely to be far from the best you can do
…
-cent pieces—and no quarters at all. In fact, Shallit observed that ungainly denominations turn change-making into something “at least as hard … as the traveling salesman problem.” That’s a lot to ask of a cashier. If ease of computation is taken into account, Shallit found, then what the US money
…
of Rutgers wrote: Letter from Roger Pinkham to Martin Gardner, January 29, 1960. Flood’s influence on computer science: See Cook, In Pursuit of the Traveling Salesman; Poundstone, Prisoner’s Dilemma; and Flood, “Soft News.” considering the problem since 1949: Flood made this claim in a letter he wrote to Gardner on
…
problem”: Menger, “Das botenproblem,” contains a lecture given by Menger on the subject in Vienna on February 5, 1930. For a fuller history of the traveling salesman problem see Schrijver, “On the History of Combinatorial Optimization,” as well as Cook’s very readable book In Pursuit of the
…
.” iconic name first appeared in print: Robinson, On the Hamiltonian Game. “impossibility results would also be valuable”: Flood, “The Traveling-Salesman Problem.” “no good algorithm for the traveling salesman problem”: Edmonds, “Optimum Branchings.” what makes a problem feasible: Cobham, “The Intrinsic Computational Difficulty of Functions,” explicitly considers the question of what should be considered
…
is itself in NP is known as “NP-complete.” See Karp, “Reducibility Among Combinatorial Problems,” for the classic result showing that a version of the traveling salesman problem is NP-complete, and Fortnow, The Golden Ticket: P, NP, and the Search for the Impossible, for an accessible introduction to P and NP
…
’re lucky, linearithmic if you’re not. Pettie and Ramachandran, “An Optimal Minimum Spanning Tree Algorithm.” the spanning tree, with its free backtracking: Approaching the traveling salesman problem via the minimum spanning tree is discussed in Christofides, Worst-Case Analysis of a New Heuristic. visits every single town on Earth: For more
…
on the state of the art in the all-world-cities traveling salesman problem (the so-called “World TSP”), an up-to-date report can be found at http://www.math.uwaterloo.ca/tsp/world/. For more on
…
the traveling salesman problem in general, Cook, In Pursuit of the Traveling Salesman, is a good general reference, and Lawler et al., The Traveling Salesman Problem, will satisfy those who want to go deeper. finding the minimal set of locations: This
…
in the work of Michael Held (of IBM) and Richard Karp (of UC Berkeley) on the traveling salesman problem in 1970—see Held and Karp, “The Traveling-Salesman Problem and Minimum Spanning Trees,” and Held and Karp, “The Traveling-Salesman Problem and Minimum Spanning Trees: Part II.” Earlier precursors, however, also exist—for instance, Lorie and
…
’ve already encountered one of the ways that this concept became central to theoretical computer science in our discussion of the complexity class of the traveling salesman problem in chapter 8; Rabin’s notion of “nondeterministic” computing is the “N” of NP. “one of the most obviously useless branches”: The quote is
…
et al., Algorithmic Game Theory, p. 30. “the prisoner’s dilemma”: The prisoner’s dilemma was first conceived by Merrill Flood (of secretary problem and traveling salesman problem fame) and Melvin Drescher at RAND Corporation. In January 1950, they staged a game between UCLA’s Armen Alchian and RAND’s John D
…
of Theorem-Proving Procedures.” In Proceedings of the Third Annual ACM Symposium on Theory of Computing, 1971, 151–158. Cook, William. In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation. Princeton, NJ: Princeton University Press, 2012. Covey, Stephen R. How to Succeed with People. Salt Lake City: Shadow Mountain
…
, Merrill M. “Soft News.” Datamation 30, no. 20 (1984): 15–16. ______. “Some Experimental Games.” In Research Memorandum RM-789. Santa Monica, CA: RAND, 1952. ______. “The Traveling-Salesman Problem.” Operations Research 4, no. 1 (1956): 61–75. ______. “What Future Is There for Intelligent Machines?” Audio Visual Communication Review 11, no. 6 (1963): 260
…
Justice. 2009. http://www.ncjrs.gov/pdffiles1/nij/grants/229023.pdf. Held, Michael, and Richard M. Karp. “The Traveling-Salesman Problem and Minimum Spanning Trees.” Operations Research 18, no. 6 (1970): 1138–1162. ______. “The Traveling-Salesman Problem and Minimum Spanning Trees: Part II.” Mathematical Programming 1, no. 1 (1971): 6–25. Henderson, T. Discrete
…
: Logistics of Production and Inventory, edited by S. S. Graves, A. H. G. Rinnooy Kan, and P. Zipkin, 445–522. Amsterdam: North Holland, 1993. ______. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. New York: Wiley, 1985. Lazzarini, Mario. “Un’applicazione del calcolo della probabilità alla ricerca sperimentale di un valore
…
. “Some Aspects of the Sequential Design of Experiments.” Bulletin of the American Mathematical Society 58 (1952): 527–535. Robinson, Julia. On the Hamiltonian Game (a Traveling Salesman Problem). Technical report RAND/RM-303. Santa Monica, CA: RAND, 1949. Rogerson, Richard, Robert Shimer, and Randall Wright. Search-Theoretic Models of the Labor Market
…
, Julia robustness rock band set list rock-paper-scissors Rogers, Kenny Romney, Mitt Rosenbaum, David Roughgarden, Tim Round-Robin Rousso, Vanessa route planning. See also traveling salesman problem; vacation, itinerary of rule bending Rush, Barbara Russell, Bertrand Russian oligarchs Rybka chess program Sagan, Carl sampling. See also randomness San Francisco Sartre, Jean
…
gondii traffic tragedy of the commons training scars transit systems Transmission Control Protocol (TCP) ACKs and backchannels and flow control and price of anarchy and traveling salesman problem Treat, Tyler “Treatise on the Probability of the Causes of Events” (Laplace) Tree, Jean Fox Trick, Michael triple handshake triple-or-nothing game trip
…
planning. See also traveling salesman problem Turing, Alan Turing machine turn-taking Tuskegee Syphilis Study Tversky, Amos Twain, Mark twin primes Twitter two-factor models two-machine scheduling UC Berkeley
by Richard Kluger · 1 Jan 1996 · 1,157pp · 379,558 words
stint at the Upmann cigar factory in Cuba, learning the leaf and manufacturing end of the trade, followed by a more intensive spell as a traveling salesman for the Webster-Eisenlohr company, peddling their line of cigars on the East Coast. Although the Cullmans sold the Webster people the tobacco they used
by Thomas H. Cormen · 15 Jan 2013
the cities with the shortest possible tour. No algorithm that runs in time O.nc /, for any constant c, has ever been found for the traveling-salesman problem. We don’t know of an algorithm that, given the intercity distances among n cities, finds the best possible order to visit the n
…
problems has been around since the early 1970s, and people were trying to solve problems that turned out to be NP-complete (such as the traveling-salesman problem) well before then. To date, we 2 So named because the mathematician Leonhard Euler proved in 1736 that it was not possible to tour
…
family tree of reductions that we’ll see: Mother Problem: boolean formula satisfiability 3-CNF satisfiability clique subset sum vertex cover partition hamiltonian cycle knapsack traveling salesman hamiltonian path longest acyclic path I won’t show all the reductions in this family tree, because some of them are rather long and involved
…
the NP-completeness family tree on page 190, you can see that we use this problem to show that the traveling-salesman problem is NP-complete, and we’ve seen how the traveling-salesman problem comes up in practice. A closely related problem is the hamiltonian-path problem, which asks whether the graph contains
…
former is NPcomplete, so is the latter. Moreover, knowing the edges in the hamiltonian path gives the edges in the hamiltonian cycle. Traveling salesman In the decision version of the traveling-salesman problem, we are given a complete undirected graph with a nonnegative integer weight on each edge, and a nonnegative integer k. A
…
polynomial time whether the edges on this cycle visit all the vertices and have a total weight of k or less. To show that the traveling-salesman problem is NP-hard, we reduce from the hamiltonian-cycle problem, another simple reduction. Given a graph G as input to the hamiltonian-cycle problem
…
reduce one problem to another in order to prove NP-hardness. Some reductions are pretty simple, such as reducing the hamiltonian-cycle problem to the traveling-salesman problem, and some are extremely complicated. Here are a few things to remember and some strategies that often help. 206 Chapter 10: Hard? Problems Go
…
formulas when reducing. Likewise, it’s usually more straightforward to reduce from the hamiltonian-cycle problem than from the traveling-salesman problem, even though they are so similar. That’s because in the traveling-salesman problem, the edge weights can be any positive integers, not just the 0 or 1 that we required when
…
from the clique problem—also a graph problem. From there, the NP-completeness family tree showed that we reduced to the hamiltonian-cycle, hamiltonian-path, traveling-salesman, and longest-acyclic-path problems, all of which are on graphs. Sometimes, however, it’s best to leap from one domain to another, such as
…
graph G to the hamiltonian-cycle problem to the weighted graph G 0 as input to the traveling-salesman problem, we really wanted to encourage using edges present in G when choosing edges for the traveling-salesman tour. We did so by giving these edges a very low weight: 0. In other words, we
…
approach and given each edge in G a weight of W , then we would have had to set the target weight k of the entire traveling-salesman tour to nW . Design widgets I didn’t go into widget design, because widgets can get complicated. Widgets can be useful for enforcing certain properties
…
news goes beyond such pathological special cases. From here on, let’s focus on optimization problems whose decision variants are NP-complete, such as the traveling-salesman problem. Some fast methods give good, and often very good, results. The technique of branch and bound organizes a search for an optimal solution into
…
of approximation algorithms give results that are guaranteed to be within a certain factor of the optimal value. For example, if the input to the traveling-salesman problem obeys the triangle inequality—for all vertices u, v, and x, the weight of edge .u; v/ is at most the sum of the
…
weights of edges .u; x/ and .x; v/—then there is a simple approximation algorithm that always finds a traveling-salesman tour whose total weight is at most twice that of the lowest, and this algorithm runs in time linear in the size of the input
…
of longest acyclic path, 199 of partition, 203–205 perspective on, 208–211 of subset sum, 199–203 of 3-CNF satisfiability, 190–191 of traveling salesman, 198–199 of vertex cover, 194–196 NP-hard, 184 number composite, 148 Erdős, 91 Erdős-Bacon, 91 Kevin Bacon, 90–91 prime
…
ORT , 77 topological sorting, 75–80 running time of, 80 transforming strings, 121–126 by dynamic programming, 123–126 running time of, 126 transitive, 71 traveling-salesman problem, 181, 198–199 tree binary, 98, 161 trie, 177 triangle inequality, 209 trie, 177 2-opt, 209 undecidable problem, 210 undirected edge, 182 undirected
by Studs Terkel · 1 Jan 1974 · 926pp · 312,419 words
enough. Sometimes he has a chip on his shoulder. The big topic at sea is still exploits with women. Because there’s always loneliness. A traveling salesman, he has a means of picking up a phone. But a seaman is one month, two, three months before he’ll get a letter from
…
in the early fifties, after flunking out of college. I worked for a bank, sold insurance . . . I ended up with a good job as a traveling salesman for a business machine company. I was twenty-three years old and making ten thousand dollars a year. I probably could have made it seventeen
by David Nasaw · 15 Nov 2007 · 1,230pp · 357,848 words
authorizing the construction of seven bridges across the Mississippi River and one across the Missouri River at Kansas City.12 Carnegie refashioned himself into a traveling salesman for Keystone Bridge, hawking his wares to local boosters, bankers, promoters, and politicians up and down the Mississippi, Missouri, and Ohio Rivers who hoped to
by Daniel Reingold and Jennifer Reingold · 1 Jan 2006 · 506pp · 146,607 words
to Denver to run its cable business. We met with Chuck and his team two days before Christmas to display our wares, much as a traveling salesman would sell pots and pans. Only what we were essentially selling was the ability to sell. Most of the pitch meetings I’ve ever been
by William D. Cohan · 11 Apr 2011 · 1,073pp · 302,361 words
of Harvard without a degree because he had trouble seeing, had a vision of Goldman Sachs as a leading securities underwriter. He had been a traveling salesman after leaving Harvard but had joined the family business at age twenty-eight and would help lead a transformation of the firm into the underwriting
by Mark Pendergrast · 2 Jan 2000 · 564pp · 153,720 words
—at his tender age he has more sense than most of us.” Soon, however, Folger sold out and rejoined Bovee, now as a clerk and traveling salesman. The same miner’s 1858 diary entry noted that Folger was “in business for himself down in Frisco and selling coffee to every damned diggings
…
. While still in his teens he started a hardware store in Independence, Kansas, selling it a year later for a profit. He worked as a traveling salesman of farm implements, then invented and manufactured farm equipment on his own, obtaining patents for a seed planter, sulky plow, harrow, hay stacker, and various
…
triple. Joel Cheek Creates Maxwell House After attending college, Joel Owsley Cheek went to Nashville, Tennessee, in 1873 to seek his fortune. Hired as a traveling salesman, or drummer, for a wholesale grocery firm there, he moved back to his home state of Kentucky to open new territory, generally riding on horseback
…
the moral in it on my part to profit him, is an immoral transaction.” He conveyed what appeared to be a real concern for the traveling salesman, explaining that he had been on the road himself for twenty-eight years. “Bear with him in his weaknesses and shortcomings. Encourage him as much
by Michael Gross · 18 Dec 2007 · 601pp · 193,225 words
Kentucky-born James Bruce Quigley, a tall, handsome redheaded Confederate veteran. He’d hit Greenville six months earlier behind a fine set of trotters. A traveling salesman for a Connecticut shoe maker, he opened a shoe store in Greenville with his younger brother, but that didn’t carry much weight with Williams
…
office in 1911 and, after failing in a bid for the Senate, went back into the railroad and oil businesses with Harry Sinclair, a former traveling salesman who’d made millions exploiting Oklahoma’s oil deposits. To give an idea of the company Haskell was keeping: Sinclair later set off the Teapot
by Rick Perlstein · 17 Aug 2020
by Roger Lowenstein · 24 Jul 2013 · 612pp · 179,328 words
by Ron Chernow · 1 Jan 1997 · 1,106pp · 335,322 words
by Paulina Rowinska · 5 Jun 2024 · 361pp · 100,834 words
by Selina Todd · 11 Feb 2021 · 598pp · 150,801 words
by George Orwell · 3 Jun 2009 · 1,497pp · 492,782 words
by Paul Carroll · 19 Sep 1994
by Christopher Andrew · 2 Aug 2010 · 1,744pp · 458,385 words
by Peter W. Bernstein · 17 Dec 2008 · 538pp · 147,612 words
by J.D. Roth · 18 Mar 2010 · 519pp · 118,095 words
by Lance Fortnow · 30 Mar 2013 · 236pp · 50,763 words
by Steven Johnson · 329pp · 88,954 words
by William Cronon · 2 Nov 2009 · 918pp · 260,504 words
by Anthony Sattin · 25 May 2022 · 412pp · 121,164 words
by Rick Perlstein · 1 Jan 2008 · 1,351pp · 404,177 words
by Susan Orlean · 1 Jan 1998
by Regina O. Obe and Leo S. Hsu · 2 May 2015
by Ben Smith · 2 May 2023
by Diana B. Henriques · 1 Aug 2011 · 598pp · 169,194 words
by James Ashton · 11 May 2023 · 401pp · 113,586 words
by Stephen Fried · 23 Mar 2010 · 603pp · 186,210 words
by Michael Wooldridge · 2 Nov 2018 · 346pp · 97,890 words
by Rachel Botsman and Roo Rogers · 2 Jan 2010 · 411pp · 80,925 words
by Stuart Russell and Peter Norvig · 14 Jul 2019 · 2,466pp · 668,761 words
by Regina O. Obe and Leo S. Hsu · 2 May 2015
by Isabel Wilkerson · 6 Sep 2010 · 740pp · 227,963 words
by Bhu Srinivasan · 25 Sep 2017 · 801pp · 209,348 words
by James Andrew Miller · 8 Aug 2016 · 790pp · 253,035 words
by Elizabeth Williamson · 8 Mar 2022 · 574pp · 148,233 words
by Dominic Sandbrook · 29 Sep 2010 · 932pp · 307,785 words
by Kai Bird and Martin J. Sherwin · 18 Dec 2007 · 1,041pp · 317,136 words
by Mehmed Kantardzić · 2 Jan 2003 · 721pp · 197,134 words
by Mario Livio · 6 Jan 2009 · 315pp · 93,628 words
by Jon Gertner · 15 Mar 2012 · 550pp · 154,725 words
by Dennis W. Cox and Michael A. A. Cox · 30 Apr 2006 · 312pp · 35,664 words
by Lydia Kang and Nate Pedersen · 16 Oct 2017
by Jack Kerouac · 1 Jan 1957 · 330pp · 117,313 words
by James Bridle · 6 Apr 2022 · 502pp · 132,062 words
by Ellen Ruppel Shell · 2 Jul 2009 · 387pp · 110,820 words
by Ken Auletta · 28 Sep 2015 · 349pp · 104,796 words
by Leo Hollis · 31 Mar 2013 · 385pp · 118,314 words
by John D. Kasarda and Greg Lindsay · 2 Jan 2009 · 603pp · 182,781 words
by Clark Blaise · 27 Oct 2000 · 240pp · 75,304 words
by Earl Swift · 8 Jun 2011 · 423pp · 129,831 words
by Edwin Lefèvre and William J. O'Neil · 14 May 1923 · 650pp · 204,878 words
by Robert Stone and Alan Andres · 3 Jun 2019
by Robert Coram · 21 Nov 2002 · 548pp · 174,644 words
by Tom Wolfe · 4 Mar 2008
by William D. Cohan · 15 Nov 2009 · 620pp · 214,639 words
by Paul Theroux · 1 Jan 1975 · 383pp · 118,458 words
by Vauhini Vara · 8 Apr 2025 · 301pp · 105,209 words
by Bennett Alan Weinberg and Bonnie K. Bealer · 5 Dec 2000 · 559pp · 174,054 words
by Hervey Cleckley · 1 Jan 1955 · 612pp · 206,792 words
by Cory Efram Doctorow, Jonathan Coulton and Russell Galen · 7 Dec 2010 · 549pp · 116,200 words
by Stross, Charles · 1 Jan 2002
by Susan Cain · 24 Jan 2012 · 377pp · 115,122 words
by Doug Stanhope · 5 Dec 2017 · 323pp · 100,923 words
by Merve Emre · 16 Aug 2018 · 384pp · 112,971 words
by Robert Elliott Smith · 26 Jun 2019 · 370pp · 107,983 words
by Guy Hands · 4 Nov 2021 · 341pp · 107,933 words
by Alex Moazed and Nicholas L. Johnson · 30 May 2016 · 324pp · 89,875 words
by Chris Hayes · 28 Jan 2025 · 359pp · 100,761 words
by James O'Toole · 29 Dec 2018 · 716pp · 192,143 words
by Edward W. Said · 29 May 1994 · 549pp · 170,495 words
by Christian Wolmar · 9 Jun 2014 · 523pp · 159,884 words
by Ken Jennings · 19 Sep 2011 · 367pp · 99,765 words
by Donovan Hohn · 1 Jan 2010 · 473pp · 154,182 words
by Timothy Cresswell · 21 May 2006
by Ted Conover · 14 Jun 1984 · 318pp · 99,881 words
by Timothy Egan · 4 Apr 2023
by Kaiser Fung · 25 Jan 2010 · 227pp · 62,177 words
by Margaret Macmillan; Richard Holbrooke; Casey Hampton · 1 Jan 2001
by James M. Tabor · 15 Aug 2026
by Johnjoe McFadden and Jim Al-Khalili · 14 Oct 2014 · 476pp · 120,892 words
by Bruce Schneier · 10 Nov 1993
by Colin Ellard · 6 Jul 2009 · 293pp · 97,431 words
by Terrence J. Sejnowski · 27 Sep 2018
by Johann Hari · 20 Jan 2015 · 513pp · 141,963 words
by Winifred Gallagher · 7 Jan 2016 · 431pp · 106,435 words
by Wolfram Eilenberger · 14 Sep 2020
by Michael Chabon · 29 May 2017 · 517pp · 155,209 words
by Doug Stanton · 2 May 2003 · 364pp · 93,033 words
by Ed Finn · 10 Mar 2017 · 285pp · 86,853 words
by Christopher Mims · 13 Sep 2021 · 385pp · 112,842 words
by John Markoff · 22 Mar 2022 · 573pp · 142,376 words
by Kate Kelly · 14 Apr 2009 · 258pp · 71,880 words
by Frankie Boyle · 30 Sep 2009
by Jake Bernstein · 14 Oct 2019 · 470pp · 125,992 words
by Kim Stanley Robinson · 6 Jul 2015 · 488pp · 148,340 words
by Andrew McAfee and Erik Brynjolfsson · 26 Jun 2017 · 472pp · 117,093 words
by Sebastian Mallaby · 24 Apr 2006 · 605pp · 169,366 words
by Matthew Syed · 9 Sep 2019 · 280pp · 76,638 words
by Jimmy Soni and Rob Goodman · 17 Jul 2017 · 415pp · 114,840 words
by Lucy Lethbridge · 18 Nov 2013 · 457pp · 128,640 words
by Felix Gillette and John Koblin · 1 Nov 2022 · 575pp · 140,384 words
by Robert J. Shiller · 14 Oct 2019 · 611pp · 130,419 words
by Freeman Dyson · 1 Jan 2006 · 332pp · 109,213 words
by Charles R. Morris · 1 Jan 2012 · 456pp · 123,534 words
by Toby Wilkinson · 19 Oct 2020
by Nik Halik and Garrett B. Gunderson · 5 Mar 2018 · 290pp · 72,046 words
by Tom Baldwin and Marc Stears · 24 Apr 2024 · 357pp · 132,377 words
by Patricia Schultz · 13 May 2007 · 2,323pp · 550,739 words
by Federico Biancuzzi and Shane Warden · 21 Mar 2009 · 496pp · 174,084 words
by Paul Volcker and Christine Harper · 30 Oct 2018 · 363pp · 98,024 words
by John M. Barry · 9 Feb 2004 · 667pp · 186,968 words
by Henry Petroski · 2 Jan 1992 · 307pp · 97,677 words
by Matt Taibbi · 7 Oct 2019 · 357pp · 99,456 words
by Michael Pye · 4 Aug 2021 · 409pp · 107,511 words
by Kurt Vonnegut · 15 Mar 1999 · 209pp · 58,466 words
by Ben Tarnoff · 20 Mar 2014 · 404pp · 118,759 words
by Judith Flanders · 14 Oct 2012 · 683pp · 203,624 words
by Sharon Bertsch McGrayne · 16 May 2011 · 561pp · 120,899 words
by Andrew Martin · 13 Nov 2012 · 326pp · 93,522 words
by Alan Rusbridger · 14 Oct 2018 · 579pp · 160,351 words
by Michael Bar-Zohar and Nissim Mishal · 1 Jan 2010 · 427pp · 127,496 words
by Robert J. Gordon · 12 Jan 2016 · 1,104pp · 302,176 words
by Lonely Planet, Alex Egerton and Greg Benchwick · 30 Jun 2013
by William Poundstone · 18 Sep 2006 · 389pp · 109,207 words
by Lonely Planet · 1,410pp · 363,093 words
by Gary Ginsberg · 14 Sep 2021 · 418pp · 134,401 words
by Merlin Sheldrake · 11 May 2020
by Erik Larson · 14 Jun 2020
by Paul Sen · 16 Mar 2021 · 444pp · 111,837 words
by Frederick Kempe · 30 Apr 2011 · 762pp · 206,865 words
by Lloyd, John and Mitchinson, John · 7 Oct 2010 · 469pp · 97,582 words
by Oliver Burkeman · 1 Jul 2012 · 211pp · 69,380 words
by Simon Winchester · 1 Jan 2001 · 361pp · 105,938 words
by Iain Gately · 30 Jun 2008 · 686pp · 201,972 words
by David Robson · 7 Mar 2019 · 417pp · 103,458 words
by Daniel Markovits · 14 Sep 2019 · 976pp · 235,576 words
by Michael Beschloss · 8 Oct 2018
by Michael J. Mauboussin · 1 Jan 2006 · 348pp · 83,490 words
by Kevin Birmingham · 16 Nov 2021 · 559pp · 155,777 words
by Jodi Berg · 12 Oct 2015 · 423pp · 87,285 words
by Danielle Evans · 12 Nov 2020 · 201pp · 67,053 words
by Rob Reich, Mehran Sahami and Jeremy M. Weinstein · 6 Sep 2021
by Kevin Roose · 481pp · 151,124 words
by Commander R 'Mike' Crosley Dsc Rn · 5 Aug 2014 · 473pp · 156,146 words
by Robert Sedgewick · 2 Jan 1992
by Gavin Francis · 28 Apr 2015 · 226pp · 66,188 words
by Jennifer Niven · 1 Jan 1990
by Christopher Hitchens · 14 Jun 2007 · 740pp · 236,681 words
by John Cassidy · 12 May 2025 · 774pp · 238,244 words
by Christopher Summerfield · 11 Mar 2025 · 412pp · 122,298 words
by Robert Altemeyer · 2 Jan 2007 · 298pp · 87,023 words
by Alex Bellos · 3 Apr 2011 · 437pp · 132,041 words
by Pankaj Mishra · 26 Jan 2017 · 410pp · 106,931 words
by Witold Rybczynski · 27 Mar 2000 · 151pp · 30,411 words
by Adrian Johns · 5 Jan 2010 · 636pp · 202,284 words
by Steven Levy · 12 Apr 2011 · 666pp · 181,495 words
by Robert M. Sapolsky · 1 May 2017 · 1,261pp · 294,715 words
by Dan Lyons · 22 Oct 2018 · 252pp · 78,780 words
by Hunter S. Thompson · 1 Jan 1966 · 308pp · 103,890 words
by Ben Goertzel and Pei Wang · 1 Jan 2007 · 303pp · 67,891 words
by Howard P. Segal · 20 May 2012 · 299pp · 19,560 words
by Rory Carroll · 15 Mar 2023 · 456pp · 128,481 words
by Lance Armstrong · 1 Sep 2001 · 304pp · 97,991 words
by Nick Bilton · 5 Nov 2013 · 304pp · 93,494 words
by Chris Hughes · 20 Feb 2018 · 173pp · 53,564 words
by John MacCormick and Chris Bishop · 27 Dec 2011 · 250pp · 73,574 words
by Thomas E. Ricks · 14 Oct 2009 · 509pp · 153,061 words
by Tom Wilkinson · 21 Jul 2014 · 341pp · 89,986 words
by James Barrat · 30 Sep 2013 · 294pp · 81,292 words
by Stross, Charles · 12 Jan 2006
by Mike Birbiglia · 11 Oct 2010 · 162pp · 51,978 words
by Jane Gleeson-White · 14 May 2011 · 274pp · 66,721 words
by Luke Johnson · 31 Aug 2011 · 166pp · 49,639 words
by Vivek Ramaswamy · 16 Aug 2021 · 344pp · 104,522 words
by Anya Kamenetz · 23 Aug 2022 · 347pp · 103,518 words
by Ray Kurzweil · 31 Dec 1998 · 696pp · 143,736 words
by Grace Blakeley · 11 Mar 2024 · 371pp · 137,268 words
by David Sumpter · 18 Jun 2018 · 276pp · 81,153 words
by Madeline Ashby · 28 Jul 2012 · 343pp · 93,544 words
by Daniel Sokatch · 18 Oct 2021 · 556pp · 95,955 words
by Alexander Elder · 28 Sep 2014 · 464pp · 117,495 words
by Irvin D. Yalom and Molyn Leszcz · 1 Jan 1967
by Robert Verkaik · 14 Apr 2018 · 419pp · 119,476 words
by Darrin M. McMahon · 14 Nov 2023 · 534pp · 166,876 words
by Joseph Burgo · 239pp · 73,178 words
by Martin Gurri · 13 Nov 2018 · 379pp · 99,340 words
by Thomas H. Davenport and Jeanne G. Harris · 6 Mar 2007 · 233pp · 67,596 words
by Francis Fukuyama · 1 Jan 1995 · 585pp · 165,304 words
by Sharon Beder · 30 Sep 2006 · 273pp · 34,920 words
by Michael Fogus and Chris Houser · 28 Nov 2010 · 706pp · 120,784 words
by Marcos Lopez de Prado · 2 Feb 2018 · 571pp · 105,054 words
by Vibrant Publishers · 24 Jan 2011 · 120pp · 17,504 words
by Drew Conway and John Myles White · 10 Feb 2012 · 451pp · 103,606 words
by Diomidis Spinellis and Georgios Gousios · 30 Dec 2008 · 680pp · 157,865 words
by Matthew A. Russell · 15 Jan 2011 · 541pp · 109,698 words
by Stephen King · 1 Jan 2000 · 244pp · 85,379 words
by Andrew Hunt and Dave Thomas · 19 Oct 1999 · 509pp · 92,141 words