traveling salesman

back to index

description: NP-hard problem in combinatorial optimization

201 results

In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation

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

Algorithms to Live By: The Computer Science of Human Decisions

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

Ashes to Ashes: America's Hundred-Year Cigarette War, the Public Health, and the Unabashed Triumph of Philip Morris

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

Algorithms Unlocked

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

Working: People Talk About What They Do All Day and How They Feel About What They Do

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

Andrew Carnegie

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

Confessions of a Wall Street Analyst: A True Story of Inside Information and Corruption in the Stock Market

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

Money and Power: How Goldman Sachs Came to Rule the World

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

Uncommon Grounds: The History of Coffee and How It Transformed Our World

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

740 Park: The Story of the World's Richest Apartment Building

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

Reaganland: America's Right Turn 1976-1980

by Rick Perlstein  · 17 Aug 2020

Buffett

by Roger Lowenstein  · 24 Jul 2013  · 612pp  · 179,328 words

Titan: The Life of John D. Rockefeller, Sr.

by Ron Chernow  · 1 Jan 1997  · 1,106pp  · 335,322 words

Mapmatics: How We Navigate the World Through Numbers

by Paulina Rowinska  · 5 Jun 2024  · 361pp  · 100,834 words

Snakes and Ladders: The Great British Social Mobility Myth

by Selina Todd  · 11 Feb 2021  · 598pp  · 150,801 words

The Complete Novels Of George Orwell

by George Orwell  · 3 Jun 2009  · 1,497pp  · 492,782 words

Big Blues: The Unmaking of IBM

by Paul Carroll  · 19 Sep 1994

The Defence of the Realm

by Christopher Andrew  · 2 Aug 2010  · 1,744pp  · 458,385 words

All the Money in the World

by Peter W. Bernstein  · 17 Dec 2008  · 538pp  · 147,612 words

Your Money: The Missing Manual

by J.D. Roth  · 18 Mar 2010  · 519pp  · 118,095 words

The Golden Ticket: P, NP, and the Search for the Impossible

by Lance Fortnow  · 30 Mar 2013  · 236pp  · 50,763 words

Emergence

by Steven Johnson  · 329pp  · 88,954 words

Nature's Metropolis: Chicago and the Great West

by William Cronon  · 2 Nov 2009  · 918pp  · 260,504 words

Nomads: The Wanderers Who Shaped Our World

by Anthony Sattin  · 25 May 2022  · 412pp  · 121,164 words

Nixonland: The Rise of a President and the Fracturing of America

by Rick Perlstein  · 1 Jan 2008  · 1,351pp  · 404,177 words

The Orchid Thief: A True Story of Beauty and Obsession

by Susan Orlean  · 1 Jan 1998

PostGIS in Action

by Regina O. Obe and Leo S. Hsu  · 2 May 2015

Traffic: Genius, Rivalry, and Delusion in the Billion-Dollar Race to Go Viral

by Ben Smith  · 2 May 2023

Bernie Madoff, the Wizard of Lies: Inside the Infamous $65 Billion Swindle

by Diana B. Henriques  · 1 Aug 2011  · 598pp  · 169,194 words

The Everything Blueprint: The Microchip Design That Changed the World

by James Ashton  · 11 May 2023  · 401pp  · 113,586 words

Appetite for America: Fred Harvey and the Business of Civilizing the Wild West--One Meal at a Time

by Stephen Fried  · 23 Mar 2010  · 603pp  · 186,210 words

The Road to Conscious Machines

by Michael Wooldridge  · 2 Nov 2018  · 346pp  · 97,890 words

What's Mine Is Yours: How Collaborative Consumption Is Changing the Way We Live

by Rachel Botsman and Roo Rogers  · 2 Jan 2010  · 411pp  · 80,925 words

Artificial Intelligence: A Modern Approach

by Stuart Russell and Peter Norvig  · 14 Jul 2019  · 2,466pp  · 668,761 words

PostGIS in Action, 2nd Edition

by Regina O. Obe and Leo S. Hsu  · 2 May 2015

The Warmth of Other Suns: The Epic Story of America's Great Migration

by Isabel Wilkerson  · 6 Sep 2010  · 740pp  · 227,963 words

Americana: A 400-Year History of American Capitalism

by Bhu Srinivasan  · 25 Sep 2017  · 801pp  · 209,348 words

Powerhouse: The Untold Story of Hollywood's Creative Artists Agency

by James Andrew Miller  · 8 Aug 2016  · 790pp  · 253,035 words

Sandy Hook: An American Tragedy and the Battle for Truth

by Elizabeth Williamson  · 8 Mar 2022  · 574pp  · 148,233 words

State of Emergency: The Way We Were

by Dominic Sandbrook  · 29 Sep 2010  · 932pp  · 307,785 words

American Prometheus: The Triumph and Tragedy of J. Robert Oppenheimer

by Kai Bird and Martin J. Sherwin  · 18 Dec 2007  · 1,041pp  · 317,136 words

Data Mining: Concepts, Models, Methods, and Algorithms

by Mehmed Kantardzić  · 2 Jan 2003  · 721pp  · 197,134 words

Is God a Mathematician?

by Mario Livio  · 6 Jan 2009  · 315pp  · 93,628 words

The Idea Factory: Bell Labs and the Great Age of American Innovation

by Jon Gertner  · 15 Mar 2012  · 550pp  · 154,725 words

The Mathematics of Banking and Finance

by Dennis W. Cox and Michael A. A. Cox  · 30 Apr 2006  · 312pp  · 35,664 words

Quackery: A Brief History of the Worst Ways to Cure Everything

by Lydia Kang and Nate Pedersen  · 16 Oct 2017

On the Road

by Jack Kerouac  · 1 Jan 1957  · 330pp  · 117,313 words

Ways of Being: Beyond Human Intelligence

by James Bridle  · 6 Apr 2022  · 502pp  · 132,062 words

Cheap: The High Cost of Discount Culture

by Ellen Ruppel Shell  · 2 Jul 2009  · 387pp  · 110,820 words

Greed and Glory on Wall Street: The Fall of the House of Lehman

by Ken Auletta  · 28 Sep 2015  · 349pp  · 104,796 words

Cities Are Good for You: The Genius of the Metropolis

by Leo Hollis  · 31 Mar 2013  · 385pp  · 118,314 words

Aerotropolis

by John D. Kasarda and Greg Lindsay  · 2 Jan 2009  · 603pp  · 182,781 words

Time Lord: Sir Sandford Fleming and the Creation of Standard Time

by Clark Blaise  · 27 Oct 2000  · 240pp  · 75,304 words

The Big Roads: The Untold Story of the Engineers, Visionaries, and Trailblazers Who Created the American Superhighways

by Earl Swift  · 8 Jun 2011  · 423pp  · 129,831 words

Reminiscences of a Stock Operator

by Edwin Lefèvre and William J. O'Neil  · 14 May 1923  · 650pp  · 204,878 words

Chasing the Moon: The People, the Politics, and the Promise That Launched America Into the Space Age

by Robert Stone and Alan Andres  · 3 Jun 2019

Boyd: The Fighter Pilot Who Changed the Art of War

by Robert Coram  · 21 Nov 2002  · 548pp  · 174,644 words

The Bonfire of the Vanities

by Tom Wolfe  · 4 Mar 2008

House of Cards: A Tale of Hubris and Wretched Excess on Wall Street

by William D. Cohan  · 15 Nov 2009  · 620pp  · 214,639 words

The Great Railway Bazaar

by Paul Theroux  · 1 Jan 1975  · 383pp  · 118,458 words

Searches: Selfhood in the Digital Age

by Vauhini Vara  · 8 Apr 2025  · 301pp  · 105,209 words

The World of Caffeine: The Science and Culture of the World's Most Popular Drug

by Bennett Alan Weinberg and Bonnie K. Bealer  · 5 Dec 2000  · 559pp  · 174,054 words

The Mask of Sanity: An Attempt to Clarify Some Issues About the So Called Psychopathic Personality

by Hervey Cleckley  · 1 Jan 1955  · 612pp  · 206,792 words

With a Little Help

by Cory Efram Doctorow, Jonathan Coulton and Russell Galen  · 7 Dec 2010  · 549pp  · 116,200 words

Toast

by Stross, Charles  · 1 Jan 2002

Quiet: The Power of Introverts in a World That Can't Stop Talking

by Susan Cain  · 24 Jan 2012  · 377pp  · 115,122 words

This Is Not Fame: A "From What I Re-Memoir"

by Doug Stanhope  · 5 Dec 2017  · 323pp  · 100,923 words

What’s Your Type?

by Merve Emre  · 16 Aug 2018  · 384pp  · 112,971 words

Rage Inside the Machine: The Prejudice of Algorithms, and How to Stop the Internet Making Bigots of Us All

by Robert Elliott Smith  · 26 Jun 2019  · 370pp  · 107,983 words

The Dealmaker: Lessons From a Life in Private Equity

by Guy Hands  · 4 Nov 2021  · 341pp  · 107,933 words

Modern Monopolies: What It Takes to Dominate the 21st Century Economy

by Alex Moazed and Nicholas L. Johnson  · 30 May 2016  · 324pp  · 89,875 words

The Sirens' Call: How Attention Became the World's Most Endangered Resource

by Chris Hayes  · 28 Jan 2025  · 359pp  · 100,761 words

The Enlightened Capitalists

by James O'Toole  · 29 Dec 2018  · 716pp  · 192,143 words

Culture and Imperialism

by Edward W. Said  · 29 May 1994  · 549pp  · 170,495 words

The Great Railroad Revolution

by Christian Wolmar  · 9 Jun 2014  · 523pp  · 159,884 words

Maphead: Charting the Wide, Weird World of Geography Wonks

by Ken Jennings  · 19 Sep 2011  · 367pp  · 99,765 words

Moby-Duck: The True Story of 28,800 Bath Toys Lost at Sea and of the Beachcombers, Oceanographers, Environmentalists, and Fools, Including the Author, Who Went in Search of Them

by Donovan Hohn  · 1 Jan 2010  · 473pp  · 154,182 words

On the Move: Mobility in the Modern Western World

by Timothy Cresswell  · 21 May 2006

Rolling Nowhere

by Ted Conover  · 14 Jun 1984  · 318pp  · 99,881 words

A Fever in the Heartland: The Ku Klux Klan's Plot to Take Over America, and the Woman Who Stopped Them

by Timothy Egan  · 4 Apr 2023

Numbers Rule Your World: The Hidden Influence of Probability and Statistics on Everything You Do

by Kaiser Fung  · 25 Jan 2010  · 227pp  · 62,177 words

Paris 1919: Six Months That Changed the World

by Margaret Macmillan; Richard Holbrooke; Casey Hampton  · 1 Jan 2001

Lightning Beneath the Sea

by James M. Tabor  · 15 Aug 2026

Life on the Edge: The Coming of Age of Quantum Biology

by Johnjoe McFadden and Jim Al-Khalili  · 14 Oct 2014  · 476pp  · 120,892 words

Applied Cryptography: Protocols, Algorithms, and Source Code in C

by Bruce Schneier  · 10 Nov 1993

You Are Here: Why We Can Find Our Way to the Moon, but Get Lost in the Mall

by Colin Ellard  · 6 Jul 2009  · 293pp  · 97,431 words

The Deep Learning Revolution (The MIT Press)

by Terrence J. Sejnowski  · 27 Sep 2018

Chasing the Scream: The First and Last Days of the War on Drugs

by Johann Hari  · 20 Jan 2015  · 513pp  · 141,963 words

How the Post Office Created America: A History

by Winifred Gallagher  · 7 Jan 2016  · 431pp  · 106,435 words

Time of the Magicians: Wittgenstein, Benjamin, Cassirer, Heidegger, and the Decade That Reinvented Philosophy

by Wolfram Eilenberger  · 14 Sep 2020

Kingdom of Olives and Ash: Writers Confront the Occupation

by Michael Chabon  · 29 May 2017  · 517pp  · 155,209 words

In Harm's Way: The Sinking of the U.S.S. Indianapolis and the Extraordinary Story of Its Survivors

by Doug Stanton  · 2 May 2003  · 364pp  · 93,033 words

What Algorithms Want: Imagination in the Age of Computing

by Ed Finn  · 10 Mar 2017  · 285pp  · 86,853 words

Arriving Today: From Factory to Front Door -- Why Everything Has Changed About How and What We Buy

by Christopher Mims  · 13 Sep 2021  · 385pp  · 112,842 words

Whole Earth: The Many Lives of Stewart Brand

by John Markoff  · 22 Mar 2022  · 573pp  · 142,376 words

Street Fighters: The Last 72 Hours of Bear Stearns, the Toughest Firm on Wall Street

by Kate Kelly  · 14 Apr 2009  · 258pp  · 71,880 words

My Shit Life So Far

by Frankie Boyle  · 30 Sep 2009

The Laundromat : Inside the Panama Papers, Illicit Money Networks, and the Global Elite

by Jake Bernstein  · 14 Oct 2019  · 470pp  · 125,992 words

Aurora

by Kim Stanley Robinson  · 6 Jul 2015  · 488pp  · 148,340 words

Machine, Platform, Crowd: Harnessing Our Digital Future

by Andrew McAfee and Erik Brynjolfsson  · 26 Jun 2017  · 472pp  · 117,093 words

The World's Banker: A Story of Failed States, Financial Crises, and the Wealth and Poverty of Nations

by Sebastian Mallaby  · 24 Apr 2006  · 605pp  · 169,366 words

Rebel Ideas: The Power of Diverse Thinking

by Matthew Syed  · 9 Sep 2019  · 280pp  · 76,638 words

A Mind at Play: How Claude Shannon Invented the Information Age

by Jimmy Soni and Rob Goodman  · 17 Jul 2017  · 415pp  · 114,840 words

Servants: A Downstairs History of Britain From the Nineteenth Century to Modern Times

by Lucy Lethbridge  · 18 Nov 2013  · 457pp  · 128,640 words

It's Not TV: The Spectacular Rise, Revolution, and Future of HBO

by Felix Gillette and John Koblin  · 1 Nov 2022  · 575pp  · 140,384 words

Narrative Economics: How Stories Go Viral and Drive Major Economic Events

by Robert J. Shiller  · 14 Oct 2019  · 611pp  · 130,419 words

The Scientist as Rebel

by Freeman Dyson  · 1 Jan 2006  · 332pp  · 109,213 words

The Dawn of Innovation: The First American Industrial Revolution

by Charles R. Morris  · 1 Jan 2012  · 456pp  · 123,534 words

A World Beneath the Sands: The Golden Age of Egyptology

by Toby Wilkinson  · 19 Oct 2020

5 Day Weekend: Freedom to Make Your Life and Work Rich With Purpose

by Nik Halik and Garrett B. Gunderson  · 5 Mar 2018  · 290pp  · 72,046 words

England: Seven Myths That Changed a Country – and How to Set Them Straight

by Tom Baldwin and Marc Stears  · 24 Apr 2024  · 357pp  · 132,377 words

1,000 Places to See in the United States and Canada Before You Die, Updated Ed.

by Patricia Schultz  · 13 May 2007  · 2,323pp  · 550,739 words

Masterminds of Programming: Conversations With the Creators of Major Programming Languages

by Federico Biancuzzi and Shane Warden  · 21 Mar 2009  · 496pp  · 174,084 words

Keeping at It: The Quest for Sound Money and Good Government

by Paul Volcker and Christine Harper  · 30 Oct 2018  · 363pp  · 98,024 words

The Great Influenza: The Story of the Deadliest Pandemic in History

by John M. Barry  · 9 Feb 2004  · 667pp  · 186,968 words

The Evolution of Useful Things

by Henry Petroski  · 2 Jan 1992  · 307pp  · 97,677 words

Hate Inc.: Why Today’s Media Makes Us Despise One Another

by Matt Taibbi  · 7 Oct 2019  · 357pp  · 99,456 words

Antwerp: The Glory Years

by Michael Pye  · 4 Aug 2021  · 409pp  · 107,511 words

Breakfast of Champions

by Kurt Vonnegut  · 15 Mar 1999  · 209pp  · 58,466 words

The Bohemians: Mark Twain and the San Francisco Writers Who Reinvented American Literature

by Ben Tarnoff  · 20 Mar 2014  · 404pp  · 118,759 words

The Victorian City: Everyday Life in Dickens' London

by Judith Flanders  · 14 Oct 2012  · 683pp  · 203,624 words

The Theory That Would Not Die: How Bayes' Rule Cracked the Enigma Code, Hunted Down Russian Submarines, and Emerged Triumphant From Two Centuries of Controversy

by Sharon Bertsch McGrayne  · 16 May 2011  · 561pp  · 120,899 words

Underground, Overground

by Andrew Martin  · 13 Nov 2012  · 326pp  · 93,522 words

Breaking News: The Remaking of Journalism and Why It Matters Now

by Alan Rusbridger  · 14 Oct 2018  · 579pp  · 160,351 words

Mossad: The Greatest Missions of the Israeli Secret Service

by Michael Bar-Zohar and Nissim Mishal  · 1 Jan 2010  · 427pp  · 127,496 words

The Rise and Fall of American Growth: The U.S. Standard of Living Since the Civil War (The Princeton Economic History of the Western World)

by Robert J. Gordon  · 12 Jan 2016  · 1,104pp  · 302,176 words

Lonely Planet Nicaragua (Travel Guide)

by Lonely Planet, Alex Egerton and Greg Benchwick  · 30 Jun 2013

Fortune's Formula: The Untold Story of the Scientific Betting System That Beat the Casinos and Wall Street

by William Poundstone  · 18 Sep 2006  · 389pp  · 109,207 words

Lonely Planet Brazil

by Lonely Planet  · 1,410pp  · 363,093 words

First Friends: The Powerful, Unsung (And Unelected) People Who Shaped Our Presidents

by Gary Ginsberg  · 14 Sep 2021  · 418pp  · 134,401 words

Entangled Life: How Fungi Make Our Worlds, Change Our Minds & Shape Our Futures

by Merlin Sheldrake  · 11 May 2020

The Splendid and the Vile: A Saga of Churchill, Family, and Defiance During the Blitz

by Erik Larson  · 14 Jun 2020

Einstein's Fridge: How the Difference Between Hot and Cold Explains the Universe

by Paul Sen  · 16 Mar 2021  · 444pp  · 111,837 words

Berlin 1961: Kennedy, Khrushchev, and the Most Dangerous Place on Earth

by Frederick Kempe  · 30 Apr 2011  · 762pp  · 206,865 words

QI: The Second Book of General Ignorance

by Lloyd, John and Mitchinson, John  · 7 Oct 2010  · 469pp  · 97,582 words

The Antidote: Happiness for People Who Can't Stand Positive Thinking

by Oliver Burkeman  · 1 Jul 2012  · 211pp  · 69,380 words

The Map That Changed the World

by Simon Winchester  · 1 Jan 2001  · 361pp  · 105,938 words

Drink: A Cultural History of Alcohol

by Iain Gately  · 30 Jun 2008  · 686pp  · 201,972 words

The Intelligence Trap: Revolutionise Your Thinking and Make Wiser Decisions

by David Robson  · 7 Mar 2019  · 417pp  · 103,458 words

The Meritocracy Trap: How America's Foundational Myth Feeds Inequality, Dismantles the Middle Class, and Devours the Elite

by Daniel Markovits  · 14 Sep 2019  · 976pp  · 235,576 words

Presidents of War

by Michael Beschloss  · 8 Oct 2018

More Than You Know: Finding Financial Wisdom in Unconventional Places (Updated and Expanded)

by Michael J. Mauboussin  · 1 Jan 2006  · 348pp  · 83,490 words

The Sinner and the Saint: Dostoevsky and the Gentleman Murderer Who Inspired a Masterpiece

by Kevin Birmingham  · 16 Nov 2021  · 559pp  · 155,777 words

The Vitamix Cookbook: 250 Delicious Whole Food Recipes to Make in Your Blender

by Jodi Berg  · 12 Oct 2015  · 423pp  · 87,285 words

The Office of Historical Corrections: A Novella and Stories

by Danielle Evans  · 12 Nov 2020  · 201pp  · 67,053 words

System Error: Where Big Tech Went Wrong and How We Can Reboot

by Rob Reich, Mehran Sahami and Jeremy M. Weinstein  · 6 Sep 2021

The AGI Chronicles

by Kevin Roose  · 481pp  · 151,124 words

They Gave Me a Seafire

by Commander R 'Mike' Crosley Dsc Rn  · 5 Aug 2014  · 473pp  · 156,146 words

Algorithms in C++ Part 5: Graph Algorithms

by Robert Sedgewick  · 2 Jan 1992

Adventures in Human Being (Wellcome)

by Gavin Francis  · 28 Apr 2015  · 226pp  · 66,188 words

Ada BlackJack: A True Story of Survival in the Arctic

by Jennifer Niven  · 1 Jan 1990

The Portable Atheist: Essential Readings for the Nonbeliever

by Christopher Hitchens  · 14 Jun 2007  · 740pp  · 236,681 words

Capitalism and Its Critics: A History: From the Industrial Revolution to AI

by John Cassidy  · 12 May 2025  · 774pp  · 238,244 words

These Strange New Minds: How AI Learned to Talk and What It Means

by Christopher Summerfield  · 11 Mar 2025  · 412pp  · 122,298 words

The Authoritarians

by Robert Altemeyer  · 2 Jan 2007  · 298pp  · 87,023 words

Alex's Adventures in Numberland

by Alex Bellos  · 3 Apr 2011  · 437pp  · 132,041 words

Age of Anger: A History of the Present

by Pankaj Mishra  · 26 Jan 2017  · 410pp  · 106,931 words

One Good Turn: A Natural History of the Screwdriver and the Screw

by Witold Rybczynski  · 27 Mar 2000  · 151pp  · 30,411 words

Piracy : The Intellectual Property Wars from Gutenberg to Gates

by Adrian Johns  · 5 Jan 2010  · 636pp  · 202,284 words

In the Plex: How Google Thinks, Works, and Shapes Our Lives

by Steven Levy  · 12 Apr 2011  · 666pp  · 181,495 words

Behave: The Biology of Humans at Our Best and Worst

by Robert M. Sapolsky  · 1 May 2017  · 1,261pp  · 294,715 words

Lab Rats: How Silicon Valley Made Work Miserable for the Rest of Us

by Dan Lyons  · 22 Oct 2018  · 252pp  · 78,780 words

Hell's Angels: A Strange and Terrible Saga

by Hunter S. Thompson  · 1 Jan 1966  · 308pp  · 103,890 words

Advances in Artificial General Intelligence: Concepts, Architectures and Algorithms: Proceedings of the Agi Workshop 2006

by Ben Goertzel and Pei Wang  · 1 Jan 2007  · 303pp  · 67,891 words

Utopias: A Brief History From Ancient Writings to Virtual Communities

by Howard P. Segal  · 20 May 2012  · 299pp  · 19,560 words

Killing Thatcher: The IRA, the Manhunt and the Long War on the Crown

by Rory Carroll  · 15 Mar 2023  · 456pp  · 128,481 words

It's Not About the Bike: My Journey Back to Life

by Lance Armstrong  · 1 Sep 2001  · 304pp  · 97,991 words

Hatching Twitter

by Nick Bilton  · 5 Nov 2013  · 304pp  · 93,494 words

Fair Shot: Rethinking Inequality and How We Earn

by Chris Hughes  · 20 Feb 2018  · 173pp  · 53,564 words

Nine Algorithms That Changed the Future: The Ingenious Ideas That Drive Today's Computers

by John MacCormick and Chris Bishop  · 27 Dec 2011  · 250pp  · 73,574 words

The Gamble: General David Petraeus and the American Military Adventure in Iraq, 2006-2008

by Thomas E. Ricks  · 14 Oct 2009  · 509pp  · 153,061 words

Bricks & Mortals: Ten Great Buildings and the People They Made

by Tom Wilkinson  · 21 Jul 2014  · 341pp  · 89,986 words

Our Final Invention: Artificial Intelligence and the End of the Human Era

by James Barrat  · 30 Sep 2013  · 294pp  · 81,292 words

Jennifer Morgue

by Stross, Charles  · 12 Jan 2006

Sleepwalk With Me: And Other Painfully True Stories

by Mike Birbiglia  · 11 Oct 2010  · 162pp  · 51,978 words

Double Entry: How the Merchants of Venice Shaped the Modern World - and How Their Invention Could Make or Break the Planet

by Jane Gleeson-White  · 14 May 2011  · 274pp  · 66,721 words

Start It Up: Why Running Your Own Business Is Easier Than You Think

by Luke Johnson  · 31 Aug 2011  · 166pp  · 49,639 words

Woke, Inc: Inside Corporate America's Social Justice Scam

by Vivek Ramaswamy  · 16 Aug 2021  · 344pp  · 104,522 words

The Stolen Year

by Anya Kamenetz  · 23 Aug 2022  · 347pp  · 103,518 words

The Age of Spiritual Machines: When Computers Exceed Human Intelligence

by Ray Kurzweil  · 31 Dec 1998  · 696pp  · 143,736 words

Vulture Capitalism: Corporate Crimes, Backdoor Bailouts, and the Death of Freedom

by Grace Blakeley  · 11 Mar 2024  · 371pp  · 137,268 words

Outnumbered: From Facebook and Google to Fake News and Filter-Bubbles – the Algorithms That Control Our Lives

by David Sumpter  · 18 Jun 2018  · 276pp  · 81,153 words

vN: The First Machine Dynasty (The Machine Dynasty Book 1)

by Madeline Ashby  · 28 Jul 2012  · 343pp  · 93,544 words

Can We Talk About Israel?: A Guide for the Curious, Confused, and Conflicted

by Daniel Sokatch  · 18 Oct 2021  · 556pp  · 95,955 words

The New Trading for a Living: Psychology, Discipline, Trading Tools and Systems, Risk Control, Trade Management

by Alexander Elder  · 28 Sep 2014  · 464pp  · 117,495 words

Theory and Practice of Group Psychotherapy

by Irvin D. Yalom and Molyn Leszcz  · 1 Jan 1967

Posh Boys: How English Public Schools Ruin Britain

by Robert Verkaik  · 14 Apr 2018  · 419pp  · 119,476 words

Equality

by Darrin M. McMahon  · 14 Nov 2023  · 534pp  · 166,876 words

The Narcissist You Know

by Joseph Burgo  · 239pp  · 73,178 words

The Revolt of the Public and the Crisis of Authority in the New Millennium

by Martin Gurri  · 13 Nov 2018  · 379pp  · 99,340 words

Competing on Analytics: The New Science of Winning

by Thomas H. Davenport and Jeanne G. Harris  · 6 Mar 2007  · 233pp  · 67,596 words

Trust: The Social Virtue and the Creation of Prosperity

by Francis Fukuyama  · 1 Jan 1995  · 585pp  · 165,304 words

Free Market Missionaries: The Corporate Manipulation of Community Values

by Sharon Beder  · 30 Sep 2006  · 273pp  · 34,920 words

The Joy of Clojure

by Michael Fogus and Chris Houser  · 28 Nov 2010  · 706pp  · 120,784 words

Advances in Financial Machine Learning

by Marcos Lopez de Prado  · 2 Feb 2018  · 571pp  · 105,054 words

Data Structures & Algorithms Interview Questions You'll Most Likely Be Asked

by Vibrant Publishers  · 24 Jan 2011  · 120pp  · 17,504 words

Machine Learning for Hackers

by Drew Conway and John Myles White  · 10 Feb 2012  · 451pp  · 103,606 words

Beautiful Architecture: Leading Thinkers Reveal the Hidden Beauty in Software Design

by Diomidis Spinellis and Georgios Gousios  · 30 Dec 2008  · 680pp  · 157,865 words

Mining the Social Web: Finding Needles in the Social Haystack

by Matthew A. Russell  · 15 Jan 2011  · 541pp  · 109,698 words

On Writing: A Memoir of the Craft

by Stephen King  · 1 Jan 2000  · 244pp  · 85,379 words

The Pragmatic Programmer

by Andrew Hunt and Dave Thomas  · 19 Oct 1999  · 509pp  · 92,141 words