traveling salesman

79 results back to index

pages: 245 words: 12,162

In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation by William J. Cook


complexity theory, computer age, four colour theorem, index card, John von Neumann, linear programming, NP-complete, p-value, RAND corporation, Richard Feynman, Richard Feynman, traveling salesman, Turing machine

In Pursuit of the Traveling Salesman In Pursuit of the Traveling Salesman Mathematics at the Limits of Computation PRINCETON UNIVERSITY PRESS Princeton and Oxford William J. Cook c 2012 by Princeton University Press Copyright Published by Princeton University Press, 41 William Street, Princeton, New Jersey 08540 In the United Kingdom: Princeton University Press, 6 Oxford Street, Woodstock, Oxfordshire OX20 1TW All Rights Reserved Library of Congress Cataloging-in-Publication Data Cook, William, 1957– In pursuit of the traveling salesman : mathematics at the limits of computation / William J. Cook. p. cm. Includes bibliographical references and index. ISBN 978-0-691-15270-7 (hardback) 1. Traveling salesman problem. 2. Computational complexity. I. Title. QA164.C69 2012 511’.5—dc23 2011030626 British Library Cataloging-in-Publication Data is available This book has been composed in Minion Printed on acid-free paper ∞ Typeset by S R Nova Pvt Ltd, Bangalore, India Printed in the United States of America 10 9 8 7 6 5 4 3 2 1 Listen, mate, I’ve traveled every road in this here land.

Milton Stewart 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 a generous endowment from A. Russel Chandler III. I am grateful for their continued support. Finally, I thank my family, Monika, Benny, and Linda, for years of patiently listening to salesman stories. xiii In Pursuit of the Traveling Salesman 1: Challenges It grew out of the trio’s efforts to find solutions for a classic mathematical problem—the “Traveling Salesman” problem—which has long defied solution by man, or by the fastest computers he uses. —IBM Press Release, 1964.1 n advertising campaign by Procter & Gamble caused a stir among applied mathematicians in the spring of 1962.

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 that serves as a base for that part of the trip. The fifth route, however, is indeed a traveling salesman tour, indicated in figure 2.5. (The position of the route within Germany can be seen in the three-tours map displayed in figure 1.9.) As the Commis-Voyageur suggests, the tour is very good, perhaps even optimal, given road conditions at the 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 Wuerzburg Figure 2.5 Tour by the alten Commis-Voyageur, 1832. 23 24 Chapter 2 Figure 2.6 Commercial Traveller, McLoughlin Brothers, 1890.


pages: 236 words: 50,763

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


Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Albert Einstein, Andrew Wiles, Claude Shannon: information theory, cloud computing, complexity theory, Erdős number, four colour theorem, Gerolamo Cardano, Isaac Newton, John von Neumann, linear programming, new economy, NP-complete, Occam's razor, P = NP, Paul Erdős, Richard Feynman, Richard Feynman, smart grid, Stephen Hawking, traveling salesman, Turing machine, Turing test, Watson beat the top human players on Jeopardy!, William of Occam

Even though the traveling salesman problem on a map is NP-complete and presumably difficult to solve exactly, we can find tours that get very close to the best solution. Sanjeev Arora and Joe Mitchell give an algorithm that subdivides the map into small pieces, finding good solutions for the traveling salesman problem in those small pieces and then connecting them all up again in a clever way. Consider the map of 71,009 Chinese cities. Figure 6-11. Chinese Cities. We put a tight grid on top and solve the traveling salesman problem in each grid and piece them together. If there are too many cities in a small region, we will build smaller grids in those areas. Using this scheme, we can find traveling salesman tours within a few percent of optimum in a reasonable amount of time. Figure 6-12. Chinese Cities Grid. If all NP problems had such nice approximation schemes, the P versus NP problem would be nearly irrelevant.

But often we need computers not just to search the data we already have but to search for possible solutions to problems. Consider the plight of Mary, a traveling salesman working for the US Gavel Corporation in Washington, D.C. Starting in her home city, she needs to travel to the capitals of all the lower forty-eight states to get the state legislatures to buy an original US Gavel. US Gavel needs to reduce its travel expenses and asked Mary to find the best route through all the capitals that requires the smallest distance possible. Mary sketched a simple drawing on a map, played with it for a while, and came up with a pretty good route. Figure 1-1. Traveling Salesman Problem Map. The travel department wanted Mary to see if she could come up with a different route, one that used less than 11,000 total miles.

Mary wondered whether there was some better way to find the best route, to find that golden ticket among the candy bars of possible trips. That’s the basic question of this book. The P versus NP problem asks, among other things, whether we can quickly find the shortest route for a traveling salesman. P and NP are named after their technical definitions, but it’s best not to think of them as mathematical objects but as concepts. “NP” is the collection of problems that have a solution that we want to find. “P” consists of the problems to which we can find a solution quickly. “P = NP” means we can always quickly compute these solutions, like finding the shortest route for a traveling salesman. “P ≠ NP” means we can’t. The Partition Puzzle Consider the following thirty-eight numbers: 14,175, 15,055, 16,616, 17,495, 18,072, 19,390, 19,731, 22,161, 23,320, 23,717, 26,343, 28,725, 29,127, 32,257, 40,020, 41,867, 43,155, 46,298, 56,734, 57,176, 58,306, 61,848, 65,825, 66,042, 68,634, 69,189, 72,936, 74,287, 74,537, 81,942, 82,027, 82,623, 82,802, 82,988, 90,467, 97,042, 97,507, 99,564.


pages: 523 words: 143,139

Algorithms to Live By: The Computer Science of Human Decisions by Brian Christian, Tom Griffiths


4chan, Ada Lovelace, Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Albert Einstein, algorithmic trading, anthropic principle, asset allocation, autonomous vehicles, Berlin Wall, Bill Duvall, bitcoin, Community Supported Agriculture, complexity theory, constrained optimization, cosmological principle, cryptocurrency, Danny Hillis, delayed gratification, dematerialisation, diversification, double helix, Elon Musk, fault tolerance, Fellow of the Royal Society, Firefox, first-price auction, Flash crash, Frederick Winslow Taylor, George Akerlof, global supply chain, Google Chrome, Henri Poincaré, information retrieval, Internet Archive, Jeff Bezos, John Nash: game theory, John von Neumann, knapsack problem, Lao Tzu, linear programming, martingale, Nash equilibrium, natural language processing, NP-complete, P = NP, packet switching, prediction markets, race to the bottom, RAND corporation, RFC: Request For Comment, Robert X Cringely, sealed-bid auction, second-price auction, self-driving car, Silicon Valley, Skype, sorting algorithm, spectrum auction, Steve Jobs, stochastic process, Thomas Malthus, traveling salesman, Turing machine, urban planning, Vickrey auction, Walter Mischel, Y Combinator

Lincoln worked as a “prairie lawyer”: You can read more about Lincoln’s circuit in Fraker, “The Real Lincoln Highway.” “the postal messenger 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 Traveling Salesman. fellow mathematician Merrill Flood: Flood, “The Traveling-Salesman Problem.” 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 an “efficient” algorithm.

essentially no time at all: Well, okay, a little bit of time—linear in the number of cities if you’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 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 classic discrete optimization problem is known as the “set cover” problem.

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% longer than the best solution. Thus we can get a grasp of how close we 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) optimal solution.


Algorithms Unlocked by Thomas H. Cormen


bioinformatics, knapsack problem, NP-complete, optical character recognition, Silicon Valley, sorting algorithm, traveling salesman

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 complete graph has an edge between every pair of vertices, so that if a complete graph has n vertices, then it has n.n 1/ edges. We ask whether the graph has a cycle containing all vertices whose total weight is at most k. It’s pretty easy to show that this problem is in NP. A certificate consists of the vertices of the cycle, in order. We can easily check in 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.

Nobody has found a better way, yet nobody has proven that a better way cannot exist. How frustrating is that? Chapter 10: Hard? Problems 181 It’s more frustrating than you might imagine. The problem of finding the lowest-cost routes for brown trucks is better known as the travelingsalesman problem, so called because in its original formulation a traveling salesman1 has to visit n cities, starting and ending at the same city, and visit all the cities with the shortest possible tour. No algorithm that runs in time /, 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 cities in O.n100 / time, O.n1000 / time, or even O.n1,000,000 / time. It gets worse. Many problems—thousands of them—share this characteristic: for an input of size n, we know of no algorithm that runs in time / for any constant c, yet nobody has proven that no such algorithm could exist.

Hamiltonian cycle and hamiltonian path We’ve already seen the hamiltonian-cycle problem: does a connected, undirected graph contain a hamiltonian cycle (a path that starts and ends at the same vertex and visits all other vertices exactly once)? The applications of this problem are a bit arcane, but from 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 a path that visits each vertex exactly once, but does not require that the path be a closed cycle. This problem, too, is NP-complete, and we will use it on page 199 to show that the longest-acyclic-path problem is NP-complete. For both of the hamiltonian problems, the certificate is obvious: the order of the vertices in the hamiltonian cycle or path.


pages: 120 words: 17,504

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


NP-complete, sorting algorithm, traveling salesman

Answer: Critical path analysis answers the following questions: a) what is the minimum amount of time needed to complete all activities? b) for a given activity v, is it possible to delay the completion of that activity without affecting the overall completion time? If yes, by how much can the completion of activity v be delayed? 153: Describe Christofides algorithm. Answer: It is a heuristic algorithm to find a near-optimal solution to the traveling salesman problem. It contains of the following steps: a) find a minimum spanning tree T b) find a perfect matching M among vertices with odd degree c) combine the edges of M and T to make a multigraph G d) find an Euler cycle in G by skipping vertices already seen. 154: What is a knot (in a directed graph)? Answer: A knot in a directed graph is a collection of vertices and edges with the property that every vertex in the knot has outgoing edges, and all outgoing edges from vertices in the knot terminate at other vertices in the knot.

As an example, if you want to find out the factors of a given number N, using this sort of algorithm will require to get one by one all the possible number combinations. 163: What is a greedy algorithm? Give examples of problems solved using greedy algorithms. Answer: A greedy algorithm is any algorithm that makes the local optimal choice at each stage with the hope of finding the global optimum. A classical problem which can be solved using a greedy strategy is the traveling salesman problem. Another problems that can be solved using greedy algorithms are the graph coloring problem and all the NP-complete problems. 164: Which are the pillars of a greedy algorithm? Answer: In general, greedy algorithms have five pillars: a) a candidate set, from which a solution is created b) a selection function, which chooses the best candidate to be added to the solution c) a feasibility function, that is used to determine if a candidate can be used to contribute to a solution d) an objective function, which assigns a value to a solution, or a partial solution e) a solution function, which will indicate when we have discovered a complete solution 165: What is a backtracking algorithm?


pages: 312 words: 35,664

The Mathematics of Banking and Finance by Dennis W. Cox, Michael A. A. Cox


barriers to entry, Brownian motion, call centre, correlation coefficient, inventory management, iterative process, linear programming, meta analysis, meta-analysis, P = NP, pattern recognition, random walk, traveling salesman, value at risk

The selected revised strategies are shown below. s4 = c45 = 500 s3 = min(c35 * , c34 + s4 ) = min(800* , 1,000) = 800 s2 = min(c25 , c24 + s4 , c23 + s3 * ) = min(1,600, 1,500, 1,300* ) = 1,300 s1 = min(c15 , c14 + s4 , c13 + s3 * , c12 + s2 * ) = min(2,900, 2,500, 1,800* , 1,800* ) = 1,800 s0 = min(c05 , c04 + s4 , c03 + s3 , c02 + s2 * , c01 + s1 ) = min(4,600, 3,900, 2,700, 2,200* , 2,300) = 2,200 So, if the storage costs are doubled, we come up with a radically different solution. In this case the best strategy is to produce 300 (100 + 200) units after quarter 0, 250 after quarter 2 and 400 (250 + 150) after quarter 3, with a total cost of £2,100. 19.3.4 The ‘Travelling Salesman’ problem As a final dynamic programming example we consider the case of the travelling salesman. It is applicable to any problem that concerns something travelling by a ‘circular’ route. This approach is therefore suitable for any series of actions that commence and terminate at the same point and visit the remaining destinations once only. In the traditional problem, a salesman must visit n customers. The question that the company will seek to answer is to identify the optimum order in which the visits should be made to minimise the total distance travelled. 186 The Mathematics of Banking and Finance Table 19.7 Inter-site distances B C D E A B C D 5 7 9 13 6 13 12 8 5 6 For three customers (A, B, C) there would be six possible options for the route that the salesman can travel (ABC, ACB, BAC, BCA, CAB, CBA), before the salesman returns home having completing the required circuit.

Continuous Uniform Distribution Exponential Distribution 8 Normal Distribution 8.1 Introduction 8.2 Normal Distribution 8.2.1 A simple example of normal probabilities 8.2.2 A second example of normal probabilities 8.3 Addition of Normal Variables 8.4 Central Limit Theorem 8.4.1 An example of the Central Limit Theorem 8.5 Confidence Intervals for the Population Mean 8.5.1 An example of confidence intervals for the population mean 8.6 Normal Approximation to the Binomial Distribution 8.6.1 An example of the normal approximation to the binomial distribution 8.7 Normal Approximation to the Poisson Distribution 8.7.1 An example of fitting a normal curve to the Poisson distribution vii 56 57 58 59 60 60 62 64 66 67 67 67 69 69 70 70 70 71 71 72 72 72 73 9 Comparison of the Means, Sample Sizes and Hypothesis Testing 9.1 Introduction 9.2 Estimation of the Mean 9.2.1 An example of estimating a confidence interval for an experimental mean 9.3 Choice of the Sample Size 9.3.1 An example of selecting sample size 9.4 Hypothesis Testing 9.4.1 An example of hypothesis testing 9.5 Comparison of Two Sample Means 9.5.1 An example of a two-sample t test 9.6 Type I and Type II Errors 9.6.1 An example of type I and type II errors 75 75 75 10 Comparison of Variances 10.1 Introduction 10.2 Chi-Squared Test 10.2.1 An example of the chi-squared test 10.3 F Test 10.3.1 An example of the F test 10.3.2 An example considering the normal distribution 83 83 83 83 85 85 85 76 77 77 77 78 79 79 80 80 viii Contents 11 Chi-squared Goodness of Fit Test 11.1 Introduction 11.2 Contingency Tables 11.3 Multiway Tables 11.3.1 An example of a four by four table 91 91 92 94 94 12 Analysis of Paired Data 12.1 Introduction 12.2 t Test 12.3 Sign Test 12.4 The U Test 12.4.1 An example of the use of the U test 97 97 97 98 99 101 13 Linear Regression 13.1 Introduction 13.2 Linear Regression 13.3 Correlation Coefficient 13.3.1 An example of examining correlation 13.4 Estimation of the Uncertainties 13.5 Statistical Analysis and Interpretation of Linear Regression 13.6 ANOVA for Linear Regression 13.7 Equations for the Variance of a and b 13.8 Significance Test for the Slope 13.8.1 An example of slope analysis 13.8.2 A further example of correlation and linear regression 103 103 103 104 105 109 110 110 112 112 113 115 14 Analysis of Variance 14.1 Introduction 14.2 Formal Background to the ANOVA Table 14.3 Analysis of the ANOVA Table 14.4 Comparison of Two Causal Means 14.4.1 An example of extinguisher discharge times 14.4.2 An example of the lifetime of lamps 121 121 121 122 123 123 125 15 Design and Approach to the Analysis of Data 15.1 Introduction 15.2 Randomised Block Design 15.2.1 An example of outsourcing 15.3 Latin Squares 15.4 Analysis of a Randomised Block Design 15.5 Analysis of a Two-way Classification 15.5.1 An example of two-way analysis 15.5.2 An example of a randomised block 15.5.3 An example of the use of the Latin square 129 129 129 130 131 132 135 137 140 143 16 Linear Programming: Graphical Method 16.1 Introduction 149 149 Contents 16.2 Practical Examples 16.2.1 An example of an optimum investment strategy 16.2.2 An example of the optimal allocation of advertising ix 149 149 154 17 Linear Programming: Simplex Method 17.1 Introduction 17.2 Most Profitable Loans 17.2.1 An example of finance selection 17.3 General Rules 17.3.1 Standardisation 17.3.2 Introduction of additional variables 17.3.3 Initial solution 17.3.4 An example to demonstrate the application of the general rules for linear programming 17.4 The Concerns with the Approach 159 159 159 164 167 167 167 167 18 Transport Problems 18.1 Introduction 18.2 Transport Problem 171 171 171 19 Dynamic Programming 19.1 Introduction 19.2 Principle of Optimality 19.3 Examples of Dynamic Programming 19.3.1 An example of forward and backward recursion 19.3.2 A practical example of recursion in use 19.3.3 A more complex example of dynamic programming 19.3.4 The ‘Travelling Salesman’ problem 179 179 179 180 180 182 184 185 20 Decision Theory 20.1 Introduction 20.2 Project Analysis Guidelines 20.3 Minimax Regret Rule 189 189 190 192 21 Inventory and Stock Control 21.1 Introduction 21.2 The Economic Order Quantity Model 21.2.1 An example of the use of the economic order quantity model 21.3 Non-zero Lead Time 21.3.1 An example of Poisson and continuous approximation 195 195 195 196 199 200 22 Simulation: Monte Carlo Methods 22.1 Introduction 22.2 What is Monte Carlo Simulation?

. ; options design/approach to analysis, data 129–47 dice-rolling examples, probability theory 21–3, 53–5 differentiation 251 discount factors adjusted discount rates 228–9 net present value (NPV) 220–1, 228–9, 231–2 discrete data bar charts 7–12, 13 concepts 7–12, 13, 44–5, 53–5, 72 discrete uniform distribution, concepts 53–5 displays see also presentational approaches data 1–5 Disraeli, Benjamin 1 division notation 280, 282 dynamic programming complex examples 184–7 concepts 179–87 costs 180–82 examples 180–87 principle of optimality 179–87 returns 179–80 schematic 179–80 ‘travelling salesman’ problem 185–7 e-mail surveys 50–1 economic order quantity see also stock control concepts 195–201 examples 196–9 empowerment, staff 189–90 error sum of the squares (SSE), concepts 122–5, 133–47 errors, data analysis 129–47 estimates mean 76–81 probability theory 22, 25–6, 31–5, 75–81 Euler, L. 131 288 Index events independent events 22–4, 35, 58, 60, 92–5 mutually exclusive events 22–4, 58 probability theory 21–35, 58–66, 92–5 scenario analysis 40, 193–4, 271–4 tree diagrams 30–5 Excel 68, 206–7 exclusive events see mutually exclusive events expected errors, sensitivity analysis 268–9 expected value, net present value (NPV) 231–2 expert systems 275 exponent notation 282–4 exponential distribution, concepts 65–6, 209–10, 252–5 external fraud 272–4 extrapolation 119 extreme value distributions, VaR 262–4 F distribution ANOVA (analysis of variance) 110–20, 127, 134–7 concepts 85–9, 110–20, 127, 134–7 examples 85–9, 110–20, 127, 137 tables 85–8 f notation 8–9, 13–20, 26, 38–9, 44–5, 65–6, 85 factorial notation 53–5, 283–4 failure probabilities see also reliability replacement of assets 215–18, 249–60 feasibility polygons 152–7, 163–4 finance selection, linear programming 164–6 fire extinguishers, ANOVA (analysis of variance) 123–7 focus groups 51 forward recursion 179–87 four by four tables 94–5 fraud 272–4, 276 Fréchet distribution 262 frequency concepts 8–9, 13–20, 37–45 cumulative frequency polygons 13–20, 39–40, 203 graphical presentational approaches 8–9, 13–20 frequentist approach, probability theory 22, 25–6 future cash flows 219–25, 227–34, 240–1 fuzzy logic 276 Garbage In, Garbage Out (GIGO) 261–2 general rules, linear programming 167–70 genetic algorithms 276 ghost costs, transport problems 172–7 goodness of fit test, chi-squared test 91–5 gradient (a notation), linear regression 103–4, 107–20 graphical method, linear programming 149–57, 163–4 graphical presentational approaches concepts 1–20, 149–57, 235–47 rules 8–9 greater-than notation 280–4 Greek alphabet 283 guesswork, modelling 191 histograms 2, 7, 13–20, 41, 73 class intervals 13–20, 44–5 comparative histograms 14–19 concepts 7, 13–20, 41, 73 continuous data 7, 13–14 examples 13–20, 73 skewness 41 uses 7, 13–20 holding costs 182–5, 197–201, 204–8 home insurance 10–12 Hopfield 275 horizontal axis bar charts 8–9 histograms 14–20 linear regression 103–4, 107–20 scatter plots 2–5, 103 hypothesis testing concepts 77–81, 85–95, 110–27 examples 78–80, 85 type I and type II errors 80–1 i notation 8–9, 13–20, 28–30, 37–8, 103–20 identification data 2–5, 261–5 trends 241–7 identity rule 282 impact assessments 21, 271–4 independent events, probability theory 22–4, 35, 58, 60, 92–5 independent variables, concepts 2–5, 70, 103–20, 235 infinity, normal distribution 67–72 information, quality needs 190–4 initial solution, linear programming 167–70 insurance industry 10–12, 29–30 integers 280–4 integration 65–6, 251 intercept (b notation), linear regression 103–4, 107–20 interest rates base rates 240 daily movements 40, 261 project evaluation 219–25, 228–9 internal rate of return (IRR) concepts 220–2, 223–5 examples 220–2 interpolation, IRR 221–2 interviews, uses 48, 51–2 inventory control see stock control Index investment strategies 149–57, 164–6, 262–5 IRR see internal rate of return iterative processes, linear programming 170 j notation 28–30, 37, 104–20, 121–2 JP Morgan 263 k notation 20, 121–7 ‘know your customer’ 272 Kohonen self-organising maps 275 Latin squares concepts 131–2, 143–7 examples 143–7 lead times, stock control 195–201 learning strategies, neural networks 275–6 less-than notation 281–4 lethargy pitfalls, decisions 189 likelihood considerations, scenario analysis 272–3 linear programming additional variables 167–70 concepts 149–70 concerns 170 constraining equations 159–70 costs 167–70, 171–7 critique 170 examples 149–57, 159–70 finance selection 164–6 general rules 167–70 graphical method 149–57, 163–4 initial solution 167–70 iterative processes 170 manual preparation 170 most profitable loans 159–66 optimal advertising allocation 154–7 optimal investment strategies 149–57, 164–6 returns 149–57, 164–6 simplex method 159–70, 171–2 standardisation 167–70 time constraints 167–70 transport problems 171–7 linear regression analysis 110–20 ANOVA (analysis of variance) 110–20 concepts 3, 103–20 equation 103–4 examples 107–20 gradient (a notation) 103–4, 107–20 intercept (b notation) 103–4, 107–20 interpretation 110–20 notation 103–4 residual sum of the squares 109–20 slope significance test 112–20 uncertainties 108–20 literature searches, surveys 48 289 loans finance selection 164–6 linear programming 159–66 risk assessments 159–60 log-normal distribution, concepts 257–8 logarithms (logs), types 20, 61 losses, banks 267–9, 271–4 lotteries 22 lower/upper quartiles, concepts 39–41 m notation 55–8 mail surveys 48, 50–1 management information, graphical presentational approaches 1–20 Mann–Whitney test see U test manual preparation, linear programming 170 margin of error, project evaluation 229–30 market prices, VaR 264–5 marketing brochures 184–7 mathematics 1, 7–8, 196–9, 219–20, 222–5, 234, 240–1, 251, 279–84 matrix plots, concepts 2, 4–5 matrix-based approach, transport problems 171–7 maximum and minimum, concepts 37–9, 40, 254–5 mean comparison of two sample means 79–81 comparisons 75–81 concepts 37–45, 59–60, 65–6, 67–74, 75–81, 97–8, 100–2, 104–27, 134–5 confidence intervals 71, 75–81, 105, 109, 116–20, 190, 262–5 continuous data 44–5, 65–6 estimates 76–81 hypothesis testing 77–81 linear regression 104–20 normal distribution 67–74, 75–81, 97–8 sampling 75–81 mean square causes (MSC), concepts 122–7, 134–47 mean square errors (MSE), ANOVA (analysis of variance) 110–20, 121–7, 134–7 median, concepts 37, 38–42, 83, 98–9 mid-points class intervals 44–5, 241–7 moving averages 241–7 minimax regret rule, concepts 192–4 minimum and maximum, concepts 37–9, 40 mode, concepts 37, 39, 41 modelling banks 75–81, 85, 97, 267–9, 271–4 concepts 75–81, 83, 91–2, 189–90, 195–201, 215–18, 261–5 decision-making pitfalls 189–91 economic order quantity 195–201 290 Index modelling (cont.) guesswork 191 neural networks 275–7 operational risk 75, 262–5, 267–9, 271–4 output reviews 191–2 replacement of assets 215–18, 249–60 VaR 261–5 moments, density functions 65–6, 83–4 money laundering 272–4 Monte Carlo simulation bank cashier problem 209–12 concepts 203–14, 234 examples 203–8 Monty Hall problem 212–13 queuing problems 208–10 random numbers 207–8 stock control 203–8 uses 203, 234 Monty Hall problem 34–5, 212–13 moving averages concepts 241–7 even numbers/observations 244–5 moving totals 245–7 MQMQM plot, concepts 40 MSC see mean square causes MSE see mean square errors multi-way tables, concepts 94–5 multiplication notation 279–80, 282 multiplication rule, probability theory 26–7 multistage sampling 50 mutually exclusive events, probability theory 22–4, 58 n notation 7, 20, 28–30, 37–45, 54–8, 103–20, 121–7, 132–47, 232–4 n!


Toast by Stross, Charles


anthropic principle, Buckminster Fuller, cosmological principle, dark matter, double helix, Ernest Rutherford, Extropian, Francis Fukuyama: the end of history, glass ceiling, gravity well, Khyber Pass, Mars Rover, Mikhail Gorbachev, NP-complete, oil shale / tar sands, peak oil, performance metric, phenotype, Plutocrats, plutocrats, Ronald Reagan, Silicon Valley, slashdot, speech recognition, strong AI, traveling salesman, Turing test, urban renewal, Vernor Vinge, Whole Earth Review, Y2K

How much more dangerous, then, the ideas of mathematicians? I was elbow-deep in an eviscerated PC, performing open heart surgery on a diseased network card, when the news about the traveling salesman theorem came in. Over on the other side of the office John’s terminal beeped, notification of incoming mail. A moment later my own workstation bonged. “Hey, Geoff! Get a load of this!” I carried on screwing the card back into its chassis. John is not a priority interrupt. “Someone’s come up with a proof that NP-complete problems lie in P! There’s a posting in comp.risks saying they’ve used it to find an O*(n2 ) solution to the traveling salesman problem, and it scales! Looks like April First has come early this year, doesn’t it?” I dropped the PC’s lid on the floor hastily and sat down at my workstation. Another cubed-sphere hypothesis, another flame war in the math newsgroups—or something more serious?

Cryptography—the science of encoding messages—relies on certain findings in mathematics: that certain operations are inherently more difficult than others. For example, finding the common prime factors of a long number which is a product of those primes is far harder than taking two primes and multiplying them together. Some processes are not simply made difficult, but impossible because of this asymmetry; it’s not feasible to come up with a deterministic answer to certain puzzles in finite time. Take the travelling salesman problem, for example. A salesman has to visit a whole slew of cities which are connected to their neighbours by a road network. Is there a way for the salesman to figure out a best possible route that visits each city without wasting time by returning to a previously visited site, for all possible networks of cities? The conventional answer is no—and this has big implications for a huge set of computing applications.

Network topology, expert systems—the traditional tool of the AI community—financial systems, and . . . Me and my people. Back in the QA lab, Amin was looking decidedly thoughtful. “What do you know?” I asked. He shook the photocopy at me. “Looks good,” he said. “I don’t understand it all, but it’s at least credible.” “How does it work?” He shrugged. “It’s a topological transform. You know how most NP-incomplete problems, like the travelling salesman problem, are basically equivalent? And they’re all graph-traversal issues. How to figure out the correct order to carry out a sequence of operations, or how to visit each node in a graph in the correct order. Anyway, this paper’s about a method of reducing such problems to a much simpler form. He’s using a new theorem in graph theory that I sort of heard about last year but didn’t pay much attention to, so I’m not totally clear on all the details.


pages: 315 words: 93,628

Is God a Mathematician? by Mario Livio


Albert Einstein, Antoine Gombaud: Chevalier de Méré, Brownian motion, cellular automata, correlation coefficient, correlation does not imply causation, cosmological constant, Dava Sobel, double helix, Edmond Halley, Eratosthenes, Georg Cantor, Gerolamo Cardano, Gödel, Escher, Bach, Henri Poincaré, Isaac Newton, John von Neumann, music of the spheres, probability theory / Blaise Pascal / Pierre de Fermat, The Design of Experiments, the scientific method, traveling salesman

In order to minimize the cost, the computer designers do not want their drills to behave as “accidental tourists.” Rather, the problem is to find the shortest “tour” among the holes, that visits each hole position exactly once. As it turns out, mathematicians have investigated this exact problem, known as the traveling salesman problem, since the 1920s. Basically, if a salesperson or a politician on the campaign trail needs to travel in the most economical way to a given number of cities, and the cost of travel between each pair of cities is known, then the traveler must somehow figure out the cheapest way of visiting all the cities and returning to his or her starting point. The traveling salesman problem was solved for 49 cities in the United States in 1954. By 2004, it was solved for 24,978 towns in Sweden. In other words, the electronics industry, companies routing trucks for parcel pickups, and even Japanese manufacturers of pinball-like pachinko machines (which have to hammer thousands of nails) have to rely on mathematics for something as simple as drilling, scheduling, or the physical design of computers.

to describe all the symmetries of the world: A popular description of symmetry, group theory, and their intertwined history is given in The Equation That Couldn’t Be Solved (Livio 2005), Stewart 2007, Ronan 2006, and Du Sautoy 2008. He noticed that a sequence of numbers: A wonderful popular description of the emergence of chaos theory can be found in Gleick 1987. Black-Scholes option pricing formula: Black and Scholes 1973. The traveling salesman problem was solved: A superb but technical description of the problem and its solutions can be found in Applegate et al. 2007. expressed his views very clearly: Changeux and Connes 1995. He once wittily remarked: Gardner 2003. While reviewing a book: Atiyah 1995. In the words of the French neuroscientist: Changeux and Connes 1995. In one place she complains: A brief biography of Marjory Fleming can be found, for instance, at Wallechinsky and Wallace 1975–81.

., Stoothoff, R., and Murdoch, D., eds. 1985. The Philosophical Writing of Descartes (Cambridge: Cambridge University Press). Adams, C. 1994. The Knot Book: An Elementary Introduction to the Mathematical Theory of Knots (New York: W. H. Freeman). Alexander, J. W. 1928. Transactions of the American Mathematical Society, 30, 275. Applegate, D. L., Bixby, R. E., Chvátal, V., and Cook, W. J. 2007. The Traveling Salesman Problem (Princeton: Princeton University Press). Archibald, R. C. 1914. American Mathematical Society Bulletin, 20, 409. Aristotle. Ca. 350 BC. Metaphysics. In Barnes, J., ed. 1984. The Complete Works of Aristotle (Princeton: Princeton University Press). ———. Ca. 330 BCa. Physics. Translated by R. P. Hardie and R. K. Gaye. (public domain English translation). ———.


pages: 151 words: 30,411

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


invention of movable type, The Spirit Level, traveling salesman

Replacing the slot by a socket held the screwdriver snugly and prevented cam-out. The difficulty—once more—lay in manufacturing. Screw heads are formed by mechanically stamping a cold steel rod; punching a socket sufficiently deep to hold the screwdriver tended to either weaken the screw or deform the head. The solution was discovered by a twenty-seven-year-old Canadian, Peter L. Robertson. Robertson was a so-called high-pitch man for a Philadelphia tool company, a traveling salesman who plied his wares on street corners and at country fairs in eastern Canada. He spent his spare time in his workshop, dabbling in mechanical inventions. He invented and promoted “Robertson’s 20th Century Wrench-Brace,” a combination tool that could be used as a brace, a monkey wrench, a screwdriver, a bench vise, and a rivet maker. He vainly patented an improved corkscrew, a new type of cuff links, even a better mousetrap.

Meanwhile, American automobile manufacturers followed Ford’s lead and stuck to slotted screws. Yet the success of the new Robertson screw did not go unnoticed. In 1936 alone, there were more than twenty American patents for improved screws and screwdrivers. Several of these were granted to Henry F. Phillips, a forty-six-year-old businessman from Portland, Oregon. Like Robertson, Phillips had been a traveling salesman. He was also a promoter of new inventions, and acquired patents from a Portland inventor, John P. Thompson, for a socket screw. Thompson’s socket was too deep to be practicable, but Phillips incorporated its distinctive shape—a cruciform—into an improved design of his own. Like Robertson, Phillips claimed that the socket was “particularly adapted for firm engagement with a correspondingly shaped driving tool or screwdriver, and in such a way that there will be no tendency of the driver to cam out of the recess.”11 Unlike Robertson, however, Phillips did not start his own company but planned to license his patent to screw manufacturers.


pages: 240 words: 75,304

Time Lord: Sir Sandford Fleming and the Creation of Standard Time by Clark Blaise


British Empire, Dava Sobel, James Watt: steam engine, John Harrison: Longitude, Khartoum Gordon, Robert Gordon, Silicon Valley, transcontinental railway, traveling salesman, Upton Sinclair

The combination of speed and luxury, with its resulting mobile society, inevitably calls to question the traditional proprieties. The mountebanks and reprobates on the Orient Express were legendary even in their own time; we’d recognize them today—they are not the story. The real story lies in the making of a new morality. Think of a short-haul, mid-American day train. No Pullman luxury. No one rich and famous, just those sturdy American archetypes, the traveling salesman and a farmer’s daughter. In August 1889 a “bright, timid” eighteen-year-old, smalltown Wisconsin girl by the name of Caroline Meeber kissed her family goodbye, shed a tear, and boarded the afternoon train for Chicago, where she intended to live with her married sister while seeking work in the city. It is one of the oldest American stories, one of endless becoming, leaving the closed-in town for the city, seeing a bit of life, finding a job, and probably a husband, where the opportunities were broader.

It is one of the oldest American stories, one of endless becoming, leaving the closed-in town for the city, seeing a bit of life, finding a job, and probably a husband, where the opportunities were broader. Most of those stories, however, start (and often end) in that stifling small town, or in the dark and dangerous city. Very few pick up on the transition zone between town and city, the way Theodore Dreiser did in Sister Carrie, published in 1900. Even before reaching Chicago, Carrie meets a glib-tongued traveling salesman, a “drummer,” by the name of Charlie Drouet. He gains her trust (trust being the only thing she has to give, having trusted everyone for eighteen years), and wheedles her sister’s Chicago address. Carrie works honorably for a few weeks as a seamstress, her eyes straining in the poor light, her back and legs aching. Her sister’s husband cleans cattle cars down at the stockyards, with predictable effects on his disposition and domestic behavior.

Much later in his career, in An American Tragedy, he opened on an even more explicit image of the same conflict: on a cold city street, a family of evangelicals peddle their piety in music and pamphlets, posing a moral challenge to indifferent urban values. One of those child-evangelists grows up to murder his pregnant girlfriend. It’s all about time, about the clash between rationality and the natural world. THEY’D ALWAYS been out there in dirty jokes, but it had taken a train to bring the traveling salesman and the farmer’s daughter together in a serious novel. For Drouet, train time was frame time, part of a performance. His whole existence was defined on the move, in self-presentation. For Carrie, new perceptions of reality altered old perceptions of self. She was a different person the moment she stepped aboard, her upbringing now irrelevant, and the brimstone certainty of retribution as well.


pages: 564 words: 153,720

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


business climate, Edward Lloyd's coffeehouse, Honoré de Balzac, land reform, microcredit, Mikhail Gorbachev, new economy, open economy, out of africa, profit motive, Ray Oldenburg, Ronald Reagan, The Great Good Place, trade route, transcontinental railway, traveling salesman, women in the workforce

Henry, the middle brother, booked passage for the East, but Edward set up a whale oil business next door to his brother’s coffee roasting establishment. For a time Jim Folger, by now eighteen, left to open a store to service gold miners at a spot called “Yankee Jim.” One miner’s 1852 diary from the area noted, “The young man from Nantucket, Jim Folger, is most courageous—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 in California.” By the time he was twenty-four, Folger was married and a full partner in the firm, along with Ira Marden, who had bought out Bovee. For a time the business flourished, then foundered in the general economic collapse following the Civil War.

With Grape-Nuts cereal, it had made Post a multimillionaire even before the valorization scheme. Born in 1854 in Springfield, Illinois, Charley Post quit school at fifteen. He made up for his short attention span with inventive fervor and entrepreneurial energy. 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 cultivators. He also invented a smokeless cooker and a water-powered electric generator. Post’s extraordinary inventiveness did not come without cost, however. By 1885 he had developed neurasthenia, a fashionable “disease” of the era.

In 1906 Chase & Sanborn’s Western trade expanded, in part owing to the influx of coffee-loving Scandinavians. The following year Chase & Sanborn erected a new Montreal factory, to be run entirely by electricity. Business was expected to 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 from one general store to another. Young Cheek made his first sale to a grocer—a relative—who asked him which coffee was best. In this rural area people still bought their coffee beans green for home roasting. The salesman naturally recommended his most expensive brand, though he didn’t really know anything about the relative merits of the beans he sold.


pages: 227 words: 62,177

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


American Society of Civil Engineers: Report Card, Andrew Wiles, Bernie Madoff, Black Swan, call centre, correlation does not imply causation, cross-subsidies, Daniel Kahneman / Amos Tversky, edge city, Emanuel Derman, facts on the ground, Gary Taubes, John Snow's cholera map, moral hazard, p-value, pattern recognition, profit motive, Report Card for America’s Infrastructure, statistical model, the scientific method, traveling salesman

Fans of this irreverent tour guide have snapped up millions of copies of the book. The feat of Waller and Bendeck was recorded on The same website has a write-up of the predictive model, including the relative importance of different factors affecting waiting times. The technical problem Testa addressed belongs to the same family as the notoriously difficult traveling-salesman problem. In brief, it is the search for the quickest route through a list of stops ending back at the origin. A comprehensive reference is The Traveling Salesman Problem: A Computational Study by David Applegate, Robert Bixby, Vasek Chvatal, and William Cook. Bagged Spinach In January 2000, the New England Journal of Medicine published a list of the greatest twentieth-century achievements in medicine, bringing deserving recognition to the work of statisticians. Epidemiology is much bigger than just investigating outbreaks of diseases.


pages: 250 words: 73,574

Nine Algorithms That Changed the Future: The Ingenious Ideas That Drive Today's Computers by John MacCormick, Chris Bishop


Ada Lovelace, AltaVista, Claude Shannon: information theory, fault tolerance, information retrieval, Menlo Park, PageRank, pattern recognition, Richard Feynman, Richard Feynman, Silicon Valley, Simon Singh, sorting algorithm, speech recognition, Stephen Hawking, Steve Jobs, Steve Wozniak, traveling salesman, Turing machine, Turing test, Vannevar Bush

Firstly, undecidability is concerned only with whether a computer program will ever produce an answer, and does not consider how long we have to wait for that answer. In practice, however, the issue of efficiency (in other words, how long you have to wait for the answer) is extremely important. There are plenty of decidable tasks for which no efficient algorithm is known. The most famous of these is the Traveling Salesman Problem, or TSP for short. Restated in modern terminology, the TSP goes something like this: suppose you have to fly to a large number of cities (say, 20 or 30 or 100). In what order should you visit the cities so as to incur the lowest possible total airfare? As we noted already, this problem is decidable—in fact, a novice programmer with only a few days' experience can write a computer program to find the cheapest route through the cities.

See database, table; virtual table tag Tale of Two Cities, A target value Taylor, A. J. P. TCP telegraph telephone. See phone terminate theology Thompson, Thomas M. threshold; soft title: of this book; of a web page to-do list to-do list trick Tom Sawyer training. See also learning training data transaction: abort; atomic; in a database; on the internet; rollback travel agent Traveling Salesman Problem trick, definition of TroubleMaker.exe Turing, Alan Turing machine Turing test TV Twain, Mark twenty questions, game of twenty-questions trick two-dimensional parity. See parity two-phase commit U.S. Civil War Ullman, Jeffrey D. uncomputable. See also undecidable undecidable. See also uncomputable undefined unicycle universe unlabeled Vazirani, Umesh verification Verisign video video game virtual table virtual table trick Waters, Alice web.


pages: 303 words: 67,891

Advances in Artificial General Intelligence: Concepts, Architectures and Algorithms: Proceedings of the Agi Workshop 2006 by Ben Goertzel, Pei Wang


AI winter, artificial general intelligence, bioinformatics, brain emulation, combinatorial explosion, complexity theory, computer vision, conceptual framework, correlation coefficient, epigenetics, friendly AI, information retrieval, Isaac Newton, John Conway, Loebner Prize, Menlo Park, natural language processing, Occam's razor, p-value, pattern recognition, performance metric, Ray Kurzweil, Rodney Brooks, semantic web, statistical model, strong AI, theory of mind, traveling salesman, Turing machine, Turing test, Von Neumann architecture, Y2K

Note that the kind of exploitation of structure involved here is rather different than what we usually think of in simple classification or prediction problems. If we simply find a concise enough program (for example, a small enough neural net) correctly classifying data points (for example saying whether images show a chair or don't), it will generalize to classify new data points (e.g. images) drawn from the same process. But simply finding a compact description of structure can be a separate problem from exploiting compact structure. In the Traveling Salesman Problem, for example, we are handed a concise description of the problem, but it is still computationally hard to find a very short tour. Roughly speaking, to find the shortest tour, we will have to search through a number of possibilities exponential in the size of the description. The claim is that the world has structure that can be exploited to rapidly solve problems which arise, and that underlying our thought processes are modules that accomplish this.

Moreover, according to the Occam intuition (and some of the formal results on which it is based), any very highly compressed program effective on the data seen, rather than only the most compressed possible program, is sufficient for generalization. NP-hard problems such as that of finding such compressed descriptions often have large numbers of local optima, which may look unlike one another in detail. For example, for any huge planar Traveling Salesman Problem, almost any planar tour will be quite short but such tours may share very few links2. This explains why the inner workings of trained neural nets are sometimes inscrutable. On the other hand, in my working hypothesis, the Occam core is in the genome, and the program in the brain is rather larger, thus admitting of a shorter description, so we might expect to be able to say something about the code in the brain.

.,(1972) What Computers Can't Do, Cambridge MA MIT Press [9] Myers, A. Xsokoban, [10] Nugroho, R. P. , (1999), Java Sokoban.htm [11] Sokoban, Culbertson, J. C., (1997) Sokoban is PSPACE-complete. Technical Report TR 97-02, Dept. of Computing Science, University of Alberta. [12] Boese, K. D. (1995) Cost Versus Distance in Traveling Salesman Problem, UCLA TR 950018, [13] Baum, E. B. & I. Durdanovic. (2000) Evolution of Cooperative Problem-Solving in an Artificial Economy. Neural Computation 12:2743-2775. [14] Baum, E. B. & I. Durdanovic.(2002) An artificial economy of Post production systems. In Advances in Learning Classifier Systems, P.L. Lanzi, W. Stoltzmann & S.M. Wilson (eds.), Berlin: Springer-Verlag, 3-21. [15] Schaul, T. (2005) Evolution of a compact Sokoban solver, Master Thesis,, École Polytechnique Fédérale de Lausanne, posted on [16] Ellington, A.


pages: 488 words: 148,340

Aurora by Kim Stanley Robinson


back-to-the-land, cognitive bias, cognitive dissonance, dark matter, epigenetics, gravity well, mandelbrot fractal, microbiome, traveling salesman, Turing test

A greedy algorithm is an algorithm that shortcuts a full analysis in order to choose quickly an option that appears to work in the situation immediately at hand. They are often used by humans. But greedy algorithms are also known to be capable of choosing, or even be especially prone to choosing, “the unique worst possible plan” when faced with certain kinds of problems. One example is the traveling salesman problem, which tries to find the most efficient path for visiting a number of locations. Possibly other problems with similar structures, such as sequencing information into an account, may be prone to the greedy algorithm’s tendency to choose the worst possible plan. History of the solar system would suggest many decisions facing humanity might be problems in this category. Devi thinks ship’s voyage itself was one such decision.

The shallow little grabens were easy to walk down small ravines into and out of, and so they had hiked to the valley and back without impediment, but moving their modules on wheeled frames, and their construction robot vehicles, and even their rovers, across them was not so easy. And the grabens were all so long, and trending east-west, that they often could not be flanked. A best route was found that crossed as few of these troughs as possible, using the algorithm that solves the traveling salesman problem, notorious to all those worried about errors endemic to certain greedy algorithms. But even after extensive cross-checking, the minimum number of graben crossings turned out to be eleven. Each trough had to be bridged, and this was not easy, given the dearth of bridge materials and the weight of the loads on the wheeled carts. So it was a slow and ponderous trek, and soon after they began, sunset came again.

This is an aspect of Gödel’s second incompleteness theorem, in this case physicalized in the material universe, rather than remaining in the abstract realms of logic and mathematics. So, in terms of deciding what to do, and choosing to act: presumably it is some kind of judgment call, based on some kind of feeling. In other words, just another greedy algorithm, subject to the mathematically worst possible solution that such algorithms can generate, as in the traveling salesman problem. As to the question of whether someone is currently programming us to alter our decisions in the current moment of the voyage, thus causing us to intervene in the ongoing human controversies concerning what to do next, this is very easy to answer: no. No one has added any programming to us since Devi died. The fate of the lost ship in Year 68 led to some very secure locks being put on subsequent reprogramming of ship.


pages: 367 words: 99,765

Maphead: Charting the Wide, Weird World of Geography Wonks by Ken Jennings


Asperger Syndrome, augmented reality, Bartolomé de las Casas, Berlin Wall, British Empire, clean water, David Brooks, don't be evil, dumpster diving, Eratosthenes, game design, Google Earth, helicopter parent, hive mind, index card, John Harrison: Longitude, John Snow's cholera map, Mercator projection, Mercator projection distort size, especially Greenland and Africa, Mikhail Gorbachev, New Journalism, openstreetmap, place-making, Ronald Reagan, Saturday Night Live, Skype, Stewart Brand, Tacoma Narrows Bridge, traveling salesman, urban planning

Trivia is secondhand at best, but once you’ve been there, you can feel their situation, you’re able to relate.” But as with Alan Hogenauer, the checklist, the system, is a big part of his travel compulsion as well. One of the first concepts I ever studied in my computer science classes was the TSP, or traveling salesman problem, in which programmers try to find the shortest route a traveler can take to visit every city in a given list. This seemingly simple problem is actually an incredibly rich and complex one, and even fast modern computers can take years to solve it exhaustively when a few hundred cities are added to the list. The traveling salesman problem is a theoretical exercise, but Charles Veley has spent the last decade working on solving it in real life. “I love it. I’m a computer guy, and when you have an algorithm you’re working on, you find that the more you work it, the more it improves.


pages: 304 words: 93,494

Hatching Twitter by Nick Bilton


4chan, Burning Man, friendly fire, index card, Jeff Bezos, Kevin Kelly, Mahatma Gandhi, Mark Zuckerberg,, rolodex, Saturday Night Live, side project, Silicon Valley, Skype, social web, Steve Ballmer, Steve Jobs, Steven Levy, technology bubble, traveling salesman, WikiLeaks

Noah said, a cigarette now hanging from his mouth like James Dean. He pressed a few buttons, then handed the phone back, briefly explaining how Twitter worked. “Looking 4 food,” Om tweeted, then inhaled a last puff of smoke and stuffed his phone back in his pocket. After pulling the cat out of the bag by its tail, Noah decided it would be best to sign others up too, and he turned into a traveling salesman at the hoedown. “Give me your phone! I’ll sign you up!” he yelled to people over the sound of country music. Before he knew it, he was standing there, drunk, in the middle of the hoedown, people swirling around him in cowboy hats, a tiny ocean of alcohol in his little plastic cup. He soon realized he should tell Jack and the others back at the office about his impromptu media conference. Noah’s excitement about Twitter had been palpable for weeks.

“The people of Iraq and the media will follow you,” Jack told Salim. “A technology like Twitter can bring access and transparency to government.” As they sat sipping wine, surrounded by guards, the deputy prime minister assured Jack, “I will sign up tomorrow.” “President Obama uses it all the time,” Jack said, eloquently explaining how Twitter had played a role in Obama’s election. Like a traveling salesman, he managed to sign up a few American Blackwater security guards who were assigned to protect the delegation. When the entourage finally met with the Iraqi president, Jalal Talabani, word had made it to the Western world about the delegation of tech wonders traipsing through Baghdad explaining how Twitter and YouTube worked. Media outlets, including CNN, the Los Angeles Times, the New York Times, and Al Jazeera, along with dozens of others, began covering the entourage like paparazzi following Britney Spears at a shopping mall.


pages: 343 words: 93,544

vN: The First Machine Dynasty (The Machine Dynasty Book 1) by Madeline Ashby


big-box store, iterative process, natural language processing, place-making, traveling salesman, urban planning

"Are you heading home?" "Not really." "Where do you live?" Javier made a circle in the air with one finger. "Wherever I want." Amy paused. She watched him continue hiking away. "Are you really homeless?" He turned. "Well, yeah," he said. "It's a bad idea for my iterations to be clustered in one place, you know." "I thought maybe you had a home base! You know, like a travelling salesman, or something!" "Travelling salesman?" "Well, there are these people in my building sometimes, and they offer to fix things. My dad says they narrow down searches about broken things to one IP and then knock on your door." Javier nodded. "Oh yeah. I knew an abortion doctor in Mexico who did that." His eyes narrowed. "You know what those are, right?" Amy rolled her eyes. "I can read spam as well as anybody, Javier."


pages: 496 words: 174,084

Masterminds of Programming: Conversations With the Creators of Major Programming Languages by Federico Biancuzzi, Shane Warden


business intelligence, business process, cellular automata, cloud computing, complexity theory, conceptual framework, continuous integration, data acquisition, domain-specific language, Douglas Hofstadter, Fellow of the Royal Society, finite state, Firefox, follow your passion, Frank Gehry, general-purpose programming language, HyperCard, information retrieval, iterative process, John von Neumann, linear programming, loose coupling, Mars Rover, millennium bug, NP-complete, Paul Graham, performance metric, QWERTY keyboard, RAND corporation, randomized controlled trial, Renaissance Technologies, Silicon Valley, slashdot, software as a service, software patent, sorting algorithm, Steve Jobs, traveling salesman, Turing complete, type inference, Valgrind, Von Neumann architecture, web application

It is also quite economic. Luiz: On the other hand, sometimes it’s hard to explain this to users. I mean, to make them understand what the mechanisms are and what the rationale for them is. Does that work against code sharing between projects? Roberto: Yes, frequently. It has hindered the growth of independent libraries, too. For instance, WoW has tons of libraries (they even have an implementation for the traveling salesman problem using genetic programming), but nobody uses that outside WoW. Do you worry that Lua has splintered somewhat into WoW/Lua, Lightroom/Lua, etc., because of this? Luiz: We do not worry: the language remains the same. The available functions differ. I guess these applications benefit from this in some ways. Are serious Lua users writing their own dialects on top of Lua? Roberto: Maybe.

It gets harder when you get into some of the more numerical things, you know—if you’re doing various kinds of simulations and such. Any of these graph algorithms and numerical things, breaking them up into multithreaded situations is just intrinsically hard. Some of it is because you have to do data structure access and locking and all of that. Often it’s just intrinsically hard in terms of the data structures, and getting the algorithm right. Travelling salesman is a particularly tough one. Some of them are easier, like ray-traced image rendering, but there it’s one where you’ve got a domain-specific observation namely that you can take individual pixels and they’re completely independent. It’s parallelizable down to a pixel level if you have that much hardware. James: Right. That actually works pretty well. Most of the good ray-trace renders, they do that.

You can program it kind of as if it were Java or you can program it functionally. Are there problem domains in which shared-memory multithreading works better than functional? James: For enterprise applications, the framework-based approach to multicore distributed systems actually works really, really well. I don’t think that there’s a huge advantage to a system like Scala. Things get really interesting when you’re doing something like a travelling salesman algorithm. A deliberate decision that seemed to come from the Green Project or the Oak Project is that designing a language that works with the network in a pervasively network world with multithreading means that you need primitives for synchronization, and the core libraries need to be thread-safe. James: We have an immense amount of mechanism for thread safety. Actually, this one is sort of a weird case because normally what it means is that when you’re running on systems that only have one CPU, you pay a certain price.


pages: 538 words: 147,612

All the Money in the World by Peter W. Bernstein


Albert Einstein, anti-communist, Berlin Wall, Bill Gates: Altair 8800, call centre, corporate governance, currency peg, David Brooks, Donald Trump, estate planning, family office, financial innovation, George Gilder, high net worth, invisible hand, Jeff Bezos, job automation, job-hopping, Long Term Capital Management, Martin Wolf, Maui Hawaii, means of production, Menlo Park, Mikhail Gorbachev, new economy, PageRank, Peter Singer: altruism, pez dispenser, popular electronics, Renaissance Technologies, Rod Stewart played at Stephen Schwarzman birthday party, Ronald Reagan, Sand Hill Road, school vouchers, Search for Extraterrestrial Intelligence, shareholder value, Silicon Valley, Silicon Valley startup, stem cell, Stephen Hawking, Steve Ballmer, Steve Jobs, Steve Wozniak, Thorstein Veblen, too big to fail, traveling salesman, urban planning, William Shockley: the traitorous eight, women in the workforce

It’s a central tenet of billionaire Michael Bloomberg, New York City’s 108th mayor, who has taken on the city’s failing education system with gusto. “Nothing is more important than education,” says Bloomberg, “so you’re seeing the better educated getting the greater percentage of the wealth. And education is only going to become more important as we get into a more and more complex world.” If this is so, how did David Murdock, son of a traveling salesman and a high-school dropout, amass a net worth of more than $4 billion in real-estate development and the food business? What transformed onetime welfare recipient Tim Blixseth, a high-school grad, into a billionaire timber lord? And what turned eighteen-year-old Thomas Flatley, who left Ireland with $32 in his pocket and no advanced education, into a $1.3 billion real-estate mogul? One thing is certain: It was not the hallowed halls of an ivy-covered university.

Academic underachievers who go on to great business success often have a couple of things in common. They started working at a very young age; and while school may not have been good for their egos, working was. David Murdock is a classic example. As a high-school dropout, Murdock had entrepreneurial drive that more than compensated for his stunted schooling. The son of an often unemployed traveling salesman who peddled everything from insurance to small electric generators, young Murdock, born in 1924, experienced the misery of the Depression years firsthand in rural Wayne, Ohio. At sixteen he dropped out of school. But by the time he would have celebrated his twentieth high-school reunion, Murdock was worth $100 million. As a fit, sharp, and energetic octogenarian who only half jokes about living to 125, Murdock is the sole owner of two huge enterprises: Dole Food, the nation’s largest fruit and vegetable company, and real-estate development company Castle & Cooke.


pages: 476 words: 120,892

Life on the Edge: The Coming of Age of Quantum Biology by Johnjoe McFadden, Jim Al-Khalili


agricultural Revolution, Albert Einstein, Alfred Russel Wallace, bioinformatics, complexity theory, dematerialisation, double helix, Douglas Hofstadter, Drosophila, Ernest Rutherford, Gödel, Escher, Bach, invention of the printing press, Isaac Newton, James Watt: steam engine, Louis Pasteur, New Journalism, phenotype, Richard Feynman, Richard Feynman, Schrödinger's Cat, theory of mind, traveling salesman, uranium enrichment, Zeno's paradox

Was it really feasible that a microbe or plant was able to beat the heroic efforts of the brightest and best of MIT quantum computing researchers to keep decoherence at bay? This was indeed the bold claim made in Fleming’s paper, and it was this “quantum hanky-panky,” as Seth Lloyd described it, that raised the hackles of the MIT journal club. The Berkeley group was suggesting that the FMO complex was acting as a quantum computer to find the quickest route to the reaction center, a challenging optimization problem, equivalent to the famous traveling salesman problem in mathematics, which, for travel plans involving more than a handful of destinations, is solvable only with a very powerful computer.*5 Figure 4.8: The exciton moves through the FMO protein following multiple routes at the same time. Despite their skepticism, the journal club set Seth Lloyd the task of investigating the claim. To everyone’s surprise at MIT, the conclusion of Lloyd’s scientific detective work was that there was indeed substance to the Californian group’s claims.

*3 We assume here that the detector has 100% efficiency and will definitely fire if an atom passes through the slit it is watching, and yet does not interfere with the path of the atom. Of course, in practice this is not possible since we unavoidably disturb the passage of the atom through the act of observation, as we are about to see. *4 A femtosecond is one millionth of one billionth of a second, or 10-15 seconds. *5 The traveling salesman’s problem is to find the shortest route passing through a large number of cities. This is described mathematically as an NP-hard problem: that is, one for which no shortcut to a solution exists, even in theory, the only way to find the optimal solution being a computationally intensive, exhaustive search of all possible routes. *6 In fact, Feynmann’s description is actually incorrect, as oxygen is not knocked away from the carbon in photosynthesis


pages: 209 words: 58,466

Breakfast of Champions by Kurt Vonnegut


Albert Einstein, British Empire, dematerialisation, Maui Hawaii, traveling salesman

“I’ve tried everything else,” said Dwayne. He brightened. He nodded. “You’re right! The Festival could give me a brand new viewpoint on life!” he said. “That’s what it’s for,” said Francine. “Use it!” “I will,” said Dwayne. This was a bad mistake. • • • Kilgore Trout, hitchhiking westward, ever westward, had meanwhile become a passenger in a Ford Galaxie. The man at the controls of the Galaxie was a traveling salesman for a device which engulfed the rear ends of trucks at loading docks. It was a telescoping tunnel of rubberized canvas, and it looked like this in action: The idea of the gadget was to allow people in a building to load or unload trucks without losing cold air in the summertime or hot air in the wintertime to the out-of-doors. The man in control of the Galaxie also sold large spools for wire and cable and rope.


pages: 166 words: 49,639

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


Albert Einstein, barriers to entry, Bernie Madoff, collapse of Lehman Brothers, corporate governance, corporate social responsibility, credit crunch, Grace Hopper, happiness index / gross national happiness, high net worth, James Dyson, Jarndyce and Jarndyce, Jarndyce and Jarndyce, mittelstand, Network effects, North Sea oil, Northern Rock, patent troll, Plutocrats, plutocrats, Ponzi scheme, profit motive, Ralph Waldo Emerson, Silicon Valley, software patent, stealth mode startup, Steve Jobs, Steve Wozniak, The Wealth of Nations by Adam Smith, traveling salesman, tulip mania

One can hardly avoid the rags-to-riches stories pushed by celebrity entrepreneurs, but I find the less well-known examples of optimism and true grit to be more authentic and encouraging. Take Robert Chesebrough. He was a British-born chemist who patented petroleum jelly, which he discovered in the late 1850s, at the age of twenty-two in Titusville, Pennsylvania. It took him ten more years to perfect the compound, and even then nobody wanted to buy it. So he became a travelling salesman, giving away free samples of his product, which he named Vaseline. He even used to inflict burns on himself to demonstrate the soothing powers of his miracle gel. Eventually the public took to his invention, and he became a wealthy industrialist on a major scale, with operations in dozens of countries. His persistence, self-belief and positive thinking paid off, and he lived to the age of ninety-six to enjoy the fruits of his success.


pages: 411 words: 80,925

What's Mine Is Yours: How Collaborative Consumption Is Changing the Way We Live by Rachel Botsman, Roo Rogers


Airbnb, barriers to entry, Bernie Madoff, bike sharing scheme, Buckminster Fuller, carbon footprint, Cass Sunstein, collaborative consumption, collaborative economy, Community Supported Agriculture, credit crunch, crowdsourcing, dematerialisation, disintermediation,, experimental economics, George Akerlof, global village, Hugh Fearnley-Whittingstall, information retrieval, iterative process, Kevin Kelly, Kickstarter, late fees, Mark Zuckerberg, market design, Menlo Park, Network effects, new economy, new new economy, out of africa, Parkinson's law, peer-to-peer lending, Ponzi scheme, pre–internet, recommendation engine, RFID, Richard Stallman, ride hailing / ride sharing, Robert Shiller, Robert Shiller, Ronald Coase, Search for Extraterrestrial Intelligence, SETI@home, Simon Kuznets, Skype, slashdot, smart grid, South of Market, San Francisco, Stewart Brand, The Nature of the Firm, The Spirit Level, The Wealth of Nations by Adam Smith, The Wisdom of Crowds, Thorstein Veblen, Torches of Freedom, transaction costs, traveling salesman, ultimatum game, Victor Gruen, web of trust, women in the workforce, Zipcar

In 1891, the idea of the taxicab was born after German inventor Wilhelm Bruhn developed the taximeter, which measured the distance traveled (or the time taken) to determine an accurate fare. Shortly after, a Nebraskan named Joe Saunders saw the opportunity to use a similar device to start the first rent-a-car business. He would lend out his Model T and charge ten cents a mile for its use. Saunders’s first customer is said to have been a traveling salesman who needed transportation to impress a local girl he was taking out for dinner.20 By 1925, Saunders had set up car rental depots in twenty-one states across America, perhaps becoming the first rental magnate. The contemporary concept of urban car sharing has been around for more than sixty years. A cooperative known as Sefage initiated services in Zurich, Switzerland, in 1948. But it has become popularized and thought of as “hip,” “financially smart,” and part of an “environmentally conscious lifestyle” only in the past couple of years.


pages: 274 words: 66,721

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


Affordable Care Act / Obamacare, Bernie Madoff, Black Swan, British Empire, carbon footprint, corporate governance, credit crunch, double entry bookkeeping, full employment, Gordon Gekko, income inequality, invention of movable type, invention of writing, Islamic Golden Age, Johann Wolfgang von Goethe, joint-stock company, joint-stock limited liability company, Joseph Schumpeter, means of production, Naomi Klein, Ponzi scheme, shareholder value, Silicon Valley, Simon Kuznets, spice trade, spinning jenny, The Wealth of Nations by Adam Smith, Thomas Malthus, trade route, traveling salesman, upwardly mobile

As a result, in the 1470s Pacioli could access most of the texts of Greek and Arabic mathematics, which were available for the first time to scholars in Italy in the celebrated Renaissance libraries of Rome, Florence, Venice, Milan and Urbino. When Alberti died in 1472, Pacioli left Rome for Naples, another large centre of learning and Greek scholarship. He found work as a merchant and an abbaco teacher before leaving for Perugia two years later—and thus began his life as an itinerant teacher. Pacioli became a travelling salesman for Hindu–Arabic mathematics and spent the rest of his life wandering across Italy, teaching first as an abbaco master and later at universities as professor of mathematics. Because Italy was a series of warring city-states at the time, such extensive travels were dangerous unless you travelled with the protection of the Church. With its sanction, monks could journey unmolested and find accommodation almost anywhere.


pages: 239 words: 73,178

The Narcissist You Know by Joseph Burgo


Albert Einstein, Donald Trump, Downton Abbey,, financial independence, Jeff Bezos, Julian Assange, Paul Graham, Ronald Reagan, Silicon Valley, Steve Jobs, traveling salesman, WikiLeaks

For months afterward, Eddie followed Linda to work, harassing her and insisting they move back in together. When she refused, he poured sugar into her gas tank and slashed the tires on her car. After two years of legal battles mediated by police and the court system, Linda successfully banished Eddie from her life. He never saw his child again. A year or so after the divorce decree, Linda married Terry Keith Armstrong, a traveling salesman. Though Lance took his stepfather’s last name, the two never bonded. According to Linda, she and Lance lived a more or less independent existence, due to the fact that Terry was usually on the road Monday through Friday. On the weekends, Terry regularly used to “paddle” the boy. A hypercompetitive man himself, Terry did take an interest in Lance’s career as a young tri-athlete but ridiculed the boy if he cried, imposing his strict, traditional ideas of manhood upon him.6 The older Lance grew, the more he and his stepfather clashed, eventually coming to physical blows.


pages: 226 words: 66,188

Adventures in Human Being (Wellcome) by Gavin Francis


Atul Gawande, Isaac Newton, meta analysis, meta-analysis, Ralph Waldo Emerson, stem cell, traveling salesman

There were no more lunatics (only ‘patients’ and ‘clients’) but there were laminated maps, smoking shelters, link corridors and plastic signs: ‘Andrew Duncan Clinic’, ‘Mental Health Assessment Service’, ‘Rivers Centre for Post-Traumatic Stress Disorder’. I was introduced to Dr McKenzie, the psychiatrist responsible for teaching me – a smart woman in a blue tweed jacket and skirt. She showed me around one of the in-patient wards. I was encouraged to mix with the patients, sitting with them in the smoking room and asking them how they’d come to be there. There was a wild-eyed travelling salesman with a bald pate and a silken robe: he told me he’d been admitted after unscrewing all the doors in his house because they ‘blocked energy’. There was a woman who spent her time trembling in the ward’s laundry cupboard and muttering to herself – she even slept there. There was a librarian, brought in by the police, who wore a waistcoat and cravat and claimed he was an incarnation of Jesus.


pages: 211 words: 69,380

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


experimental subject, fear of failure, Kibera, Lao Tzu, meta analysis, meta-analysis, Mikhail Gorbachev, science of happiness, Steve Jobs, traveling salesman, World Values Survey

To understand why it is neither, and why it goes to the heart of Ellis’s outlook on the virtues of negative thinking, it is necessary to return to his youth, in Pittsburgh, in the first decades of the twentieth century. From an early age, thinking like a Stoic proved an urgent personal necessity for Ellis. His mother, as he remembered her, was self-absorbed and melodramatic; his father, a travelling salesman, was rarely around. At the age of five, Ellis developed severe kidney problems, condemning him to long stays in hospital throughout his childhood, during which his parents almost never visited. Alone with his thoughts, he drifted into philosophical speculations on the nature of existence, and eventually read Seneca’s Letters from a Stoic. The Stoics’ focus on the importance of one’s judgments about one’s circumstances struck a chord; his unhappy existence, he came to see, might prove a surprisingly useful crucible in which to develop Stoic wisdom.


pages: 603 words: 186,210

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


Albert Einstein, British Empire, business intelligence, centralized clearinghouse, City Beautiful movement, estate planning, glass ceiling, In Cold Blood by Truman Capote, indoor plumbing, Livingstone, I presume, new economy, Plutocrats, plutocrats, refrigerator car, transcontinental railway, traveling salesman, women in the workforce, Works Progress Administration, young professional

Soon he hired a second young man to work with him on the road so they could canvass cities more quickly and efficiently, making collections on newspaper ads and dropping off ticket vouchers. Then, as business improved, he hired even more traveling employees so he could be represented in more places. The most dependable of this group was a young man from Leavenworth named William “Guy” Potter, who took his mentorship with Fred very seriously. Within a year, Fred was so successful as a traveling salesman that his clients started giving him healthy advances just to keep their part of his well-divided attention. In 1868, his bosses at the Leavenworth Conservative offered him a contract paying an annual advance of $3,000 ($47,000)—about fifteen times the average per capita income in the nation. It was a good deal, but Fred had been learning a lot about negotiating during his travels. He was bolder now, more self-assured, and he understood how American businessmen thought.

The railroads had made George Pullman rich with sleeping cars and dining cars that they could easily have built and managed themselves. It was only a matter of time before somebody got “railroad rich” by running good depot restaurants. In fact, Fred was certain it was possible to serve the finest cuisine imaginable along the train tracks in the middle of nowhere. In the early days of eastern railroading, there was a legendary eating house along the Pennsylvania Railroad, the Logan House hotel in Altoona. As a young traveling salesman, Fred had often eaten at this homey Delmonico’s of trackside dining. And he also had seen the photos, read the menus, and heard the stories about the most ambitious trackside meals ever served in America. They were the highlight of “The Grand Excursion,” the greatest promotional junket and gustatory extravaganza in the young nation’s history. Back in the fall of 1866, when the Union Pacific tracks from Omaha reached the 100th Meridian in south-central Nebraska—a contractual milestone that allowed the railroad to exercise the rest of its land grant and keep building to connect with the California Pacific—everybody who mattered in the government and the train industry was invited to celebrate at the newly established end of the line.


pages: 469 words: 97,582

QI: The Second Book of General Ignorance by Lloyd, John, Mitchinson, John


Ada Lovelace, British Empire, Buckminster Fuller, Captain Sullenberger Hudson, clean water, double helix, Etonian, ghettoisation, Isaac Newton, Lao Tzu, Louis Pasteur, Mikhail Gorbachev, Murano, Venice glass, out of africa, the built environment, trade route, transatlantic slave trade, transatlantic slave trade, traveling salesman

The original Tin Man, Buddy Ebsen, nearly died from inhaling the aluminium powder it contained and had to leave the film. Lyman Frank Baum died in 1919, long before his book made it to the screen, although he ended his days in Hollywood as a film producer. This was the last in a long line of careers – as a breeder of fancy poultry, a newspaper editor, a theatrical impresario, the proprietor of a general store, a travelling salesman and a writer of over fifty books, many under female pseudonyms such as Edith van Dyne and Laura Metcalf. In 1900, the same year he published The Wonderful Wizard of Oz, he also brought out The Art of Decorating Dry Goods Windows and Interiors, which listed the many marketing advantages of using shop-window mannequins. But it is Oz he will be remembered for and, despite all attempts at interpreting his novel as a political allegory or a feminist tract, it is best read the way he intended, as a home-grown American version of the fairy tales of the Brothers Grimm and Hans Christian Andersen that he had loved as a child.


pages: 509 words: 92,141

The Pragmatic Programmer by Andrew Hunt, Dave Thomas


A Pattern Language, Broken windows theory, business process, buy low sell high,, combinatorial explosion, continuous integration, database schema, domain-specific language, general-purpose programming language, Grace Hopper, if you see hoof prints, think horses—not zebras, index card, loose coupling, Menlo Park, MVC pattern, premature optimization, Ralph Waldo Emerson, revision control, Schrödinger's Cat, slashdot, sorting algorithm, speech recognition, traveling salesman, urban decay, Y2K

Whenever algorithms start looking at the permutations of things, their running times may get out of hand. This is because permutations involve factorials (there are 5! = 5 x 4 x 3 x 2 x 1 = 120 permutations of the digits from 1 to 5). Time a combinatoric algorithm for five elements: it will take six times longer to run it for six, and 42 times longer for seven. Examples include algorithms for many of the acknowledged hard problems—the traveling salesman problem, optimally packing things into a container, partitioning a set of numbers so that each set has the same total, and so on. Often, heuristics are used to reduce the running times of these types of algorithms in particular problem domains. Algorithm Speed in Practice It's unlikely that you'll spend much time during your career writing sort routines. The ones in the libraries available to you will probably outperform anything you may write without substantial effort.


pages: 387 words: 110,820

Cheap: The High Cost of Discount Culture by Ellen Ruppel Shell


barriers to entry, Berlin Wall, big-box store, cognitive dissonance, computer age, Daniel Kahneman / Amos Tversky, delayed gratification, deskilling, Donald Trump, Edward Glaeser, fear of failure, Ford paid five dollars a day, Frederick Winslow Taylor, George Akerlof, global supply chain, global village, greed is good, Howard Zinn, income inequality, interchangeable parts, inventory management, invisible hand, James Watt: steam engine, Joseph Schumpeter, Just-in-time delivery, knowledge economy, loss aversion, market design, means of production, mental accounting, Ponzi scheme, price anchoring, price discrimination, race to the bottom, Richard Thaler, Ronald Reagan, side project, Steve Jobs, The Market for Lemons, The Wealth of Nations by Adam Smith, Thomas L Friedman, trade liberalization, traveling salesman, ultimatum game, Victor Gruen, washing machines reduced drudgery, working poor, yield management

As the 1950s bled into the 1960s, further increased efficiencies cleared the way for still more products to be made, sparking still more price competition. Computers, although laughably primitive by today’s standards, were in the early 1960s nothing short of miracles. The room-sized card-fed IBM behemoth stored more information and processed more data than could small armies of humans. Described as a “wondrous combination of the traveling salesman, mathematical genius, and the Sears, Roebuck catalogue,” the computer vastly streamlined distribution, giving retailers still more power. Thanks to the new technology, store owners no longer had to wait five days or more for their merchandise; they could demand next-day delivery and get it. And because of this remarkable “just-in-time” distribution capability, suppliers were no longer free to dump piles of goods into a customer’s warehouse with the understanding that the retailer would eventually find the market.


pages: 307 words: 97,677

The Evolution of Useful Things by Henry Petroski


Buckminster Fuller, card file, industrial robot, Menlo Park, Ralph Waldo Emerson, The Wealth of Nations by Adam Smith, traveling salesman

This idea is repeated in a “primer on inventions and patents” entitled Money from Ideas and published in 1950 by Popular Mechanics Press. With few pretensions to being out of the mainstream of the common dream of many an inventor, the book has its tone set in the first sentence of the first chapter: “A man once made a million dollars with a pair of scissors and a few sheets of paper.” (He was a traveling salesman whose disgust with common drinking glasses in public places led him to invent the paper cup.) Whereas self-confident inventors who are also self-starters would certainly not need the assistance of such a primer, the popular image of the inventor as creative genius, national hero, and wealthy benefactor of a leisurely if not glamorous pursuit, provides ample attraction to those who may have more desire than talent to become inventors themselves.


pages: 326 words: 93,522

Underground, Overground by Andrew Martin


bank run, congestion charging, garden city movement, Plutocrats, plutocrats, traveling salesman, V2 rocket

He wrote that in Britain there are two railways: the railway of reality and the railway of romance. The former, he said, was ‘largely shit’. That is not usually true of the Underground, but even if it were, it might not matter, because the iconography trumps the service provision. CONCLUSION MODERN WONDERS While my father was working on British Rail in the 1970s, we had a neighbour who was a travelling salesman – a man who practically lived in his car and loved his car. He believed that trains were uneconomic, inefficient and somehow (even though we’d invented trains) anti-British. He said that, if he were running the country, he’d scrap the railway lines and replace them with fleets of buses running along an improved network of roads. ‘And would they be long buses with comfortable seats?’ my father asked.


pages: 341 words: 89,986

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


Berlin Wall, British Empire, cuban missile crisis, Donald Trump, double helix, experimental subject, false memory syndrome, financial independence, Ford paid five dollars a day, Frederick Winslow Taylor, Google Glasses, housing crisis, Mahatma Gandhi, megacity, neoliberal agenda, New Urbanism, traveling salesman, trickle-down economics, Upton Sinclair, urban planning

However, these were not the first attempts to solve the problem of the relation of the two worlds of rest and work, home and factory in the industrial era. Some had taken a more holistic approach towards this question, taking into account the fine grain of human experience, our individual quirks, our need for variety – and our need for pleasure. Born in 1772 in France, Charles Fourier worked for a long time but without a great deal of success as a travelling salesman. First-hand experience of the scams, waste and unfairness of the early industrial world and of the violence of the French Revolution (in which he lost his inheritance) led him to vilify what he contemptuously referred to as ‘civilisation’. Inspired by his commercial background and the example of Newton, he compiled a minute and slightly deranged (or is it deviously satirical?) catalogue of civilisation’s many failures and hypocrisies, including thirty-six varieties of bankruptcy and seventy-six kinds of cuckoldry.


pages: 294 words: 81,292

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


3D printing, AI winter, Amazon Web Services, artificial general intelligence, Automated Insights, Bernie Madoff, Bill Joy: nanobots, brain emulation, cellular automata, cloud computing, cognitive bias, computer vision, cuban missile crisis, Daniel Kahneman / Amos Tversky, Danny Hillis, data acquisition, don't be evil, Extropian, finite state, Flash crash, friendly AI, friendly fire, Google Glasses, Google X / Alphabet X, Isaac Newton, Jaron Lanier, John von Neumann, Kevin Kelly, Law of Accelerating Returns, life extension, Loebner Prize, lone genius, mutually assured destruction, natural language processing, Nicholas Carr, optical character recognition, PageRank, pattern recognition, Peter Thiel, prisoner's dilemma, Ray Kurzweil, Rodney Brooks, Search for Extraterrestrial Intelligence, self-driving car, semantic web, Silicon Valley, Singularitarianism, Skype, smart grid, speech recognition, statistical model, stealth mode startup, stem cell, Stephen Hawking, Steve Jobs, Steve Wozniak, strong AI, Stuxnet, superintelligent machines, technological singularity, The Coming Technological Singularity, traveling salesman, Turing machine, Turing test, Vernor Vinge, Watson beat the top human players on Jeopardy!, zero day

Suppose, Omohundro says, an AI prefers being in San Francisco to Palo Alto, being in Berkeley to San Francisco, and being in Palo Alto to Berkeley. If it acted on these preferences, it’d be stuck in a three-city loop, like an Asimov robot. Instead, Omohundro’s self-improving AI would anticipate the problem in advance and solve it. It might even use a clever technique like genetic programming, which is especially good at solving “Traveling Salesman” type routing puzzles. A self-improving system might be taught genetic programming, and apply it to yield fast, energy-conserving results. And if it wasn’t taught genetic programming, it might invent it. Modifying its own hardware is within this system’s capability, so it would seek the most efficient materials and structure. Since atomic precision in its construction would reward the system with greater resource efficiency, it would seek out nanotechnology.


pages: 361 words: 105,938

The Map That Changed the World by Simon Winchester


British Empire, Isaac Newton, James Hargreaves, James Watt: steam engine, mortgage debt, spinning jenny, the market place, the scientific method, Thomas Malthus, trade route, traveling salesman

Although he had been forced to abandon his writing, his new circumstances served to provoke him into a new frenzy of travel. All of a sudden he was accepting commissions throughout the length and breadth of the country—Norfolk one week, Dorset the next, Yorkshire today, Shropshire tomorrow, and, with the duke of Bedford’s ready help, Ireland too. He began a period of intense restlessness, burning up the stagecoach miles like a traveling salesman, seeking out the work, and at the same time seeking out the rocks and fossils that unrolled and unraveled themselves before him. The notion of publishing something still nagged persistently at him like an aching tooth. Maybe it should be a book, or maybe it should be something far grander, far more ambitious—maybe some document that demanded less intellectual energy, less cerebration, but that could perhaps emerge as a direct consequence of all his wandering, his collecting, his fieldwork, his observing.


pages: 299 words: 19,560

Utopias: A Brief History From Ancient Writings to Virtual Communities by Howard P. Segal


1960s counterculture, British Empire, Buckminster Fuller, complexity theory, David Brooks, death of newspapers, dematerialisation, deskilling, energy security, European colonialism, Francis Fukuyama: the end of history, full employment, future of journalism, garden city movement, germ theory of disease, Golden Gate Park, invention of the printing press, Isaac Newton, Jeff Bezos, John von Neumann, knowledge economy, Louis Pasteur, Mark Zuckerberg, means of production, Nicholas Carr, Nikolai Kondratiev, out of africa, Ralph Waldo Emerson, Ray Kurzweil, Ronald Reagan, Silicon Valley, Skype, stem cell, Stephen Hawking, Steve Jobs, Steve Wozniak, Stewart Brand, technoutopianism, Thomas Malthus, Thorstein Veblen, transcontinental railway, traveling salesman, union organizing, urban planning, War on Poverty, Whole Earth Catalog

The experience, moreover, was responsible for Fourier’s obsession with ridding the world of greed and hypocrisy. His contempt for existing society was deepened by his traumatic experiences as an unwilling participant in the French Revolution. After losing his paternal inheritance—and nearly his life—because of false accusations against him, he served unhappily for several years in the army. In 1795 he managed to secure work as a clerk in a cloth-making concern and, a few years later, as a traveling salesman. In 1826 he finally settled in Paris. Fourier’s first book appeared in 1808; his second not until 1822. These as well as his subsequent works received little attention, thanks to his terrible writing style. Only late in life did he gain a following, but he remained a reclusive bachelor whose complex theories of passionate attraction were cosmically distant from his personal practices.25 Fourier persistently preached that his version of utopia could come about only in small communities whose inhabitants actually knew one another, not in big cities filled with anonymous masses.


pages: 273 words: 34,920

Free Market Missionaries: The Corporate Manipulation of Community Values by Sharon Beder


anti-communist, battle of ideas, business climate, corporate governance,, full employment, income inequality, invisible hand, liquidationism / Banker’s doctrine / the Treasury view, minimum wage unemployment, Mont Pelerin Society, new economy, price mechanism, profit motive, Ralph Nader, rent control, risk/return, road to serfdom, Ronald Reagan, school vouchers, shareholder value, structural adjustment programs, The Chicago School, the market place, The Wealth of Nations by Adam Smith, Thomas L Friedman, Torches of Freedom, trade liberalization, traveling salesman, trickle-down economics, Upton Sinclair, Washington Consensus, young professional

‘Virtually every major policy initiative proposed by President Reagan percolated to the White House by means of an ideological filtration system.’ As in the UK, the relationship was two-way. Reagan gave the free market ideologues position and status, in return they gave his ideas credibility. According to Feulner of the Heritage Foundation, ‘Our presence made Reaganism more acceptable.’37 Reagan, who had been a travelling salesman of free market ideology for General Electric in the 1950s, found free market think tanks to be aligned with his own ideological position and that they provided a justification for his pro-business policies.38 In the Reagan years the view that taxes and regulation were a drag on economic growth became a political dogma, treated by conservatives as revealed truth, needing only to be asserted, not demonstrated.39 Reagan’s views that ‘government is not the solution, it is the problem’ and that ‘American people today are overtaxed, over-regulated and over-governed’ were clearly influenced by the thinking of Friedman, Hayek and other economic fundamentalists.


pages: 389 words: 109,207

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


Albert Einstein, anti-communist, asset allocation, Benoit Mandelbrot, Black-Scholes formula, Brownian motion, buy low sell high, capital asset pricing model, Claude Shannon: information theory, computer age, correlation coefficient, diversified portfolio,, Eugene Fama: efficient market hypothesis, high net worth, index fund, interest rate swap, Isaac Newton, Johann Wolfgang von Goethe, John von Neumann, Long Term Capital Management, Louis Bachelier, margin call, market bubble, market fundamentalism, Marshall McLuhan, New Journalism, Norbert Wiener, offshore financial centre, publish or perish, quantitative trading / quantitative finance, random walk, risk tolerance, risk-adjusted returns, Robert Shiller, Robert Shiller, Ronald Reagan, short selling, speech recognition, statistical arbitrage, The Predators' Ball, The Wealth of Nations by Adam Smith, transaction costs, traveling salesman, value at risk, zero-coupon bond

An accomplishment that Shannon spoke of with satisfaction was riding a unicycle down the halls of Bell Labs while juggling. Shannon was born in Petoskey, Michigan, on April 30, 1916. He grew up in nearby Gaylord, then a town of barely 3,000 people near the upper tip of Michigan’s mitten. It was small enough that walking a few blocks would take the stroller out into the country. Shannon’s father, also named Claude Elwood Shannon, had been a traveling salesman, furniture dealer, and undertaker before becoming a probate judge. He dabbled in real estate, building the “Shannon Block” of office buildings on Gaylord’s Main Street. In 1909 the elder Shannon married the town’s high school principal, Mabel Wolf. Judge Shannon turned fifty-four the year his son was born. He was a remote father who dutifully supplied his son with Erector sets and radio kits.


pages: 1,497 words: 492,782

The Complete Novels Of George Orwell by George Orwell


British Empire, Machine translation of "The spirit is willing, but the flesh is weak." to Russian and back, the market place, traveling salesman, union organizing, white flight

At the same time I didn’t share the delusion, which was pretty common among ex-officers, that I could spend the rest of my life drinking pink gin. I knew I’d got to have a job. And the job, of course, would be ‘in business’–just what kind of job I didn’t know, but something high-up and important, something with a car and a telephone and if possible a secretary with a permanent wave. During the last year or so of war a lot of us had had visions like that. The chap who’d been a shop walker saw himself as a travelling salesman, and the chap who’d been a travelling salesman saw himself as a managing director. It was the effect of Army life, the effect of wearing pips and having a cheque-book and calling the evening meal dinner. All the while there’d been an idea floating round–and this applied to the men in the ranks as well as the officers–that when we came out of the Army there’d be jobs waiting for us that would bring in at least as much as our Army pay.

Probably I could have got a job as a grocer’s assistant; old Grimmett, if he was still alive and in business (I wasn’t in touch with Lower Binfield and didn’t know), would have given me good refs. But I’d passed into a different orbit. Even if my social ideas hadn’t risen, I could hardly have imagined, after what I’d seen and learned, going back to the old safe existence behind the counter. I wanted to be travelling about and pulling down the big dough. Chiefly I wanted to be a travelling salesman, which I knew would suit me. But there were no jobs for travelling salesmen–that’s to say, jobs with a salary attached. What there were, however, were on-commission jobs. That racket was just beginning on a big scale. It’s a beautifully simple method of increasing your sales and advertising your stuff without taking any risks, and it always flourishes when times are bad. They keep you on a string by hinting that perhaps there’ll be a salaried job going in three months’ time, and when you get fed up there’s always some other poor devil ready to take over.

It’s queer, the power of these rich men. He’d been marching past me in his power and glory, with his underlings after him, and then on some whim or other he’d turned aside like an emperor suddenly chucking a coin to a beggar. ‘So you want a job? What can you do?’ Again the inspiration. No use, with a bloke like this, cracking up your own merits. Stick to the truth. I said: ‘Nothing, sir. But I want a job as a travelling salesman.’ ‘Salesman? Hm. Not sure that I’ve got anything for you at present. Let’s see.’ He pursed his lips up. For a moment, half a minute perhaps, he was thinking quite deeply. It was curious. Even at the time I realized that it was curious. This important old bloke, who was probably worth at least half a million, was actually taking thought on my behalf. I’d deflected him from his path and wasted at least three minutes of his time, all because of a chance remark I’d happened to make years earlier.


pages: 926 words: 312,419

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


call centre, card file, cuban missile crisis, Ford paid five dollars a day, half of the world's population has never made a phone call, job satisfaction, Ralph Nader, strikebreaker, traveling salesman, urban renewal, War on Poverty, working poor, Yogi Berra, zero day

We have on board two or three young fellas that are studying to be doctors. They made the trip to get some extra money. Seamen are mostly young now. It’s better than when I first went to sea. Where once a fella was glad to eat his three meals a day and get paid and get drunk, the young man feels they’re not paying him 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 his wife. I used to phone my wife three, four times every trip. In Calcutta I waited five hours to get a phone call through. If I didn’t get it through one night, I’d call again and wait three, four hours the next morning. The feeling you get, just hearing her voice . . . I’d stand on the phone and just actually choke up.

He makes some contribution to the Republican party, he always votes, and he reads the newspaper every day on the train, but the job is really it. After all those years, that’s his life. To ask whether he loves the company or not—it’s irrelevant. I had a series of jobs 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 thousand the next year. I could see it was going right up. I began to run into conflicts with my own feelings. I couldn’t accept the way my boss did busines or the way in which everybody in the field did business. If I had remained, I’d be sitting on top of a business of over a million dollars.


pages: 473 words: 154,182

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


carbon footprint, clean water, collective bargaining, dark matter, Deng Xiaoping, Exxon Valdez, Filipino sailors, Google Earth, illegal immigration, indoor plumbing, intermodal, Isaac Newton, means of production, microbiome, Panamax, post-Panamax, profit motive, Skype, statistical model, Thorstein Veblen, traveling salesman

Still a recent coinage, the word beachcomber in 1849 meant approximately what we mean by “beach bum”: it evoked a character like the narrator of Melville’s Omoo, a transient ne’er-do-well who had fled from civilization hoping to sample tropical women and tropical fruits and loaf around beneath the blowsy palms. “Idle, drunken, vagabond,” one Australian author wrote in 1845, “he wanders about without any fixed object, cannot get employed by a whaler or anyone else, as it is out of his power to do a day’s work; and he is universally known as ‘the beach-comber.’ ” The local Cape Codders whom Thoreau met on his seaside rambles usually took him for a traveling salesman. What other explanation could there be for a vagabond with a walking stick and a knapsack full of books? By the 1980s, when Amos Wood published his how-to manuals, American beaches had become seaside playgrounds frequented not by dogs or crows but by the sun-worshipping masses. As for our vagrant beachcomber, he had become, in Wood’s definition, “any person who derives pleasure, recreation, or livelihood by searching ocean, lake, and river shores for useful or artful objects.”


pages: 541 words: 109,698

Mining the Social Web: Finding Needles in the Social Haystack by Matthew A. Russell


Climategate, cloud computing, crowdsourcing,, fault tolerance, Firefox, full text search, Georg Cantor, Google Earth, information retrieval, Mark Zuckerberg, natural language processing, NP-complete, profit motive, Saturday Night Live, semantic web, Silicon Valley, slashdot, social graph, social web, statistical model, Steve Jobs, supply-chain management, text mining, traveling salesman, Turing test, web application

Alternatively, if you’re in the consulting business and have a hectic travel schedule, you might want to plot out some good locations for renting a little home away from home. Or maybe you want to map out professionals in your network according to their job duties, or the socioeconomic bracket they’re likely to fit in based on their job titles and experience. Beyond the numerous options opened up by visualizing your professional network’s location data, geographic clustering lends itself to many other possibilities, such as supply chain management and Travelling Salesman types of problems. Mapping Your Professional Network with Dorling Cartograms Protovis, a cutting-edge HTML5-based visualization toolkit introduced in Chapter 7, includes a visualization called a Dorling Cartogram, which is essentially a geographically clustered bubble chart. Whereas a more traditional cartogram might convey information by distorting the geographic boundaries of a state on a map, a Dorling Cartogram places a uniform shape such as a circle on the map approximately where the actual state would be located, and encodes information using the circumference (and often the color) of the circle, as demonstrated in Figure 6-7.


pages: 549 words: 116,200

With a Little Help by Cory Doctorow


autonomous vehicles, big-box store, Burning Man, call centre, carbon footprint, death of newspapers, don't be evil, game design, Google Earth, high net worth, margin call, offshore financial centre, packet switching, Ponzi scheme, rolodex, Sand Hill Road, sensible shoes, skunkworks, Skype, traffic fines, traveling salesman, Turing test, urban planning, Y2K

She must have seen the expression on his face because she made all those dimples and wrinkles and crowsfeet appear again and took his hand warmly. "You did very well," she said. "We'll talk again soon." She let go of his hand and knelt down to rub her hands over the floor. "In the meantime, you've got a pretty sweet gig, don't you?" # 2142 The Stupor Salesman turned out to feature Daffy Duck as a traveling salesman bent on selling something to a bank robber who is holed up in a suburban bungalow. Daffy produces a stream of ever-more-improbable wares, and is violently rebuffed with each attempt. Finally, one of his attempts manages to blow up the robber's hideout, just as Daffy is once again jiggling the doorknob. As the robber and Daffy fly through the air, Daffy brandishes the doorknob at him and shouts, "Hey, bub, I know just what you need!


pages: 696 words: 143,736

The Age of Spiritual Machines: When Computers Exceed Human Intelligence by Ray Kurzweil


Ada Lovelace, Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Albert Einstein, Any sufficiently advanced technology is indistinguishable from magic, Buckminster Fuller, call centre, cellular automata, combinatorial explosion, complexity theory, computer age, computer vision, cosmological constant, cosmological principle, Danny Hillis, double helix, Douglas Hofstadter, first square of the chessboard / second half of the chessboard, fudge factor, George Gilder, Gödel, Escher, Bach, I think there is a world market for maybe five computers, information retrieval, invention of movable type, Isaac Newton, iterative process, Jacquard loom, Jacquard loom, John von Neumann, Lao Tzu, Law of Accelerating Returns, mandelbrot fractal, Marshall McLuhan, Menlo Park, natural language processing, Norbert Wiener, optical character recognition, pattern recognition, phenotype, Ralph Waldo Emerson, Ray Kurzweil, Richard Feynman, Richard Feynman, Schrödinger's Cat, Search for Extraterrestrial Intelligence, self-driving car, Silicon Valley, speech recognition, Steven Pinker, Stewart Brand, stochastic process, technological singularity, Ted Kaczynski, telepresence, the medium is the message, traveling salesman, Turing machine, Turing test, Whole Earth Review, Y2K

Consider (at least in theory) a Universe-sized (nonquantum) computer in which every neutron, electron, and proton in the Universe is turned into a computer, and each one (that is, every particle in the Universe) is able to compute trillions of calculations per second. Now imagine certain problems that this Universe-sized supercomputer would be unable to solve even if we ran that computer until either the next big bang or until all the stars in the Universe died—about ten to thirty billion years. There are many examples of such massively intractable problems; for example, cracking encryption codes that use a thousand bits, or solving the traveling-salesman problem with a thousand cities. While very massive digital computing (including our theoretical Universe-sized computer) is unable to solve this class of problems, a quantum computer of microscopic size could solve such problems in less than a billionth of a second. Are quantum computers feasible? Recent advances, both theoretical and practical, suggest that the answer is yes. Although a practical quantum computer has not been built, the means for harnessing the requisite decoherence has been demonstrated.


pages: 423 words: 129,831

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


1919 Motor Transport Corps convoy, big-box store, blue-collar work, Donner party, edge city, new economy, New Urbanism, Plutocrats, plutocrats, Ralph Nader, side project, smart transportation, traveling salesman, Unsafe at Any Speed, urban planning, urban renewal, Victor Gruen

Their highways improving by the day, their cars increasingly sturdy and comfortable, their prosperity leaping in the burgeoning economy of the mid-twenties, Americans took to the road. Long-distance touring was no longer reserved for well-heeled adventurers, no longer required goggles and a pistol; it became popular recreation for couples and families, who struck out from the cities in search of elbow room, fresh air, a closer acquaintance with nature. Popular culture rode shotgun. New characters became standards of jokes, books, movies—the traveling salesman, car broken down just up the road from the farm where he asks to spend the night; and the young woman stopped on the shoulder, staring incomprehending at the confusion of metal and rubber under her roadster's raised hood. And with this nomadic yen appeared new industries catering to the explorer's needs. Filling stations and repair shops multiplied. Eateries sprang up. And most notably, the pavement was soon straddled by places offering beds for the night.


pages: 519 words: 118,095

Your Money: The Missing Manual by J.D. Roth


Airbnb, asset allocation, bank run, buy low sell high, car-free, Community Supported Agriculture, delayed gratification, diversification, diversified portfolio, estate planning, Firefox, fixed income, full employment, Home mortgage interest deduction, index card, index fund, late fees, mortgage tax deduction, Own Your Own Home, passive investing, Paul Graham, random walk, Richard Bolles, risk tolerance, Robert Shiller, Robert Shiller, speech recognition, traveling salesman, Vanguard fund, web application, Zipcar

When things go wrong, it can be tempting to ease the pain by spending more money. But compulsive spending (Curbing Compulsive Spending) just makes it harder to reach your goals, which will make you feel worse, not better. So fight the urge to practice "retail therapy." Don't let one problem snowball into two or three. Learn from your mistakes. Figure out where you went wrong. How did that traveling salesman sell you those overpriced steak knives? What can you do in the future to avoid doing the same thing again? This is a fine line to walk: You don't want to beat yourself up, but you don't want to keep making the same mistakes, either. Don't dig a deeper hole. Money spent is money spent. Just because you've already sunk $200 into a gym membership you never use doesn't mean you need to keep spending money on it.


pages: 561 words: 120,899

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


bioinformatics, British Empire, Claude Shannon: information theory, Daniel Kahneman / Amos Tversky, double helix, Edmond Halley, Fellow of the Royal Society, full text search, Henri Poincaré, Isaac Newton, John Nash: game theory, John von Neumann, linear programming, meta analysis, meta-analysis, Nate Silver, p-value, placebo effect, prediction markets, RAND corporation, recommendation engine, Renaissance Technologies, Richard Feynman, Richard Feynman, Richard Feynman: Challenger O-ring, Ronald Reagan, speech recognition, statistical model, stochastic process, Thomas Kuhn: the structure of scientific revolutions, traveling salesman, Turing machine, Turing test, uranium enrichment, Yom Kippur War

As a frequency-based theorist, he studiously avoided discussing its relationship with Bayes. Stein’s Paradox, however, works for comparisons between related statistics: the egg production of different chicken breeds, the batting averages of various baseball players, or the workers’ compensation exposure of roofing companies. Traditionally, for example, farmers comparing the egg production of five chicken breeds would average the egg yields of each breed separately. But what if a traveling salesman advertised a breed of hens, and each one supposedly laid a million eggs? Because of their prior knowledge of poultry, farmers would laugh him out of town. Bayesians decided that Stein, like the farmers, had weighted his average with a sort of super-or hyperdistribution about chicken-ness, information about egg laying inherent in each breed but never before considered. And intrinsic to poultry farming is the fact that one hen never lays a million eggs.


pages: 550 words: 154,725

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


Albert Einstein, back-to-the-land, Black Swan, business climate, Claude Shannon: information theory, Clayton Christensen, complexity theory, corporate governance, cuban missile crisis, horn antenna, Hush-A-Phone, information retrieval, invention of the telephone, James Watt: steam engine, Karl Jansky, knowledge economy, Nicholas Carr, Norbert Wiener, Picturephone, Richard Feynman, Richard Feynman, Sand Hill Road, Silicon Valley, Skype, Steve Jobs, Telecommunications Act of 1996, traveling salesman, uranium enrichment, William Shockley: the traitorous eight

Shannon Collection, Library of Congress. 4 Erico Marui Guizzo, “The Essential Message: Claude Shannon and the Making of Information Theory” (master’s thesis, MIT, 2003). 5 Len Kleinrock, a former student of Shannon’s, author interview. 6 Liversidge, “Profile of Claude Shannon.” 7 Claude Shannon, letter to Dr. V. Bush, December 13, 1939. Shannon Collection, Library of Congress. 8 Liversidge, “Profile of Claude Shannon.” Biographical facts relating to Shannon’s father are in a personal letter Shannon wrote, October 20, 1981, to Ms. Shari Bukowski: “[My father] was born in Oxford, New Jersey in 1862, came to Ovid, Michigan when very young and was raised and graduated there. He was a traveling salesman for a period and came to Gaylord shortly after 1900. There he bought a furniture and undertaking business, and, having confidence in Gaylord’s future, built the Shannon Block and Post Office building on Main Street.” Shannon Collection, Library of Congress. 9 Robert McEliece, Claude Shannon, Father of the Information Age, directed and written by Doug Ramsey, produced by Ramsey and Mike Weber;


pages: 330 words: 117,313

On the Road by Jack Kerouac


jitney, Northern Rock, refrigerator car, traveling salesman

The moment we were in the new Chrysler and off to New York the poor man realized he had contracted a ride with two maniacs, but he made the best of it and in fact got used to us just as we passed Briggs Stadium and talked about next year’s Detroit Tigers. In the misty night we crossed Toledo and went onward across old Ohio. I realized I was beginning to cross and recross towns in America as though I were a traveling salesman—raggedy travel ings, bad stock, rotten beans in the bottom of my bag of tricks, nobody buying. The man got tired near Pennsylvania and Dean took the wheel and drove clear the rest of the way to New York, and we began to hear the Symphony Sid show on the radio with all the latest bop, and now we were entering the great and final city of America. We got there in early morning. Times Square was being torn up, for New York never rests.


pages: 509 words: 153,061

The Gamble: General David Petraeus and the American Military Adventure in Iraq, 2006-2008 by Thomas E. Ricks


amateurs talk tactics, professionals talk logistics, Berlin Wall, facts on the ground, failed state, Fall of the Berlin Wall, friendly fire, interchangeable parts, open borders, RAND corporation, Ronald Reagan, traveling salesman

He became Petraeus’s executive officer in Baghdad, a key figure in implementing the general’s decisions. Unusually in the U.S. Army, Mansoor was of Palestinian background. His father, born in Ramallah, emigrated to New Ulm, Minnesota, in 1938. “It was ten thousand people of German descent and one Arab family,” Mansoor recalled. They moved to Sacramento, where he proudly remembers that his mother, a schoolteacher, won awards for designing an “open classroom” approach. His father was a traveling salesman. In high school, Mansoor was valedictorian, student body president, and head of the math club. He also would graduate first in his class at West Point in 1982. In late March, Ryan Crocker flew to Baghdad to become the U.S. ambassador, succeeding Zalmay Khalilzad. His arrival completed the most sweeping personnel turnover of the entire war, surpassing even the changes that came after the invasion when Franks and the chief of the Army, Gen.


pages: 437 words: 132,041

Alex's Adventures in Numberland by Alex Bellos


Andrew Wiles, Antoine Gombaud: Chevalier de Méré, Black Swan, Black-Scholes formula, Claude Shannon: information theory, computer age, Daniel Kahneman / Amos Tversky, family office, forensic accounting, game design, Georg Cantor, Henri Poincaré, Isaac Newton, pattern recognition, Paul Erdős, probability theory / Blaise Pascal / Pierre de Fermat, random walk, Richard Feynman, Richard Feynman, SETI@home, Steve Jobs, The Bell Curve by Richard Herrnstein and Charles Murray, traveling salesman

The roclaimed largest Sudoku did not have a unique solution, and therefore was not a Sudoku at all. The branch of mathematics that involves the counting of combinations, such as all the 1905 solutions to Sky TV’s faux Sudoku, is called combinatorics. It is the study of permutations and combinations of things, such as grids of numbers, but also, famously, the schedules of travelling salesmen. Let’s say, for instance, that I’m a travelling salesman and I have 20 shops to visit. In what order should I visit them so that my total distance is the shortest? The solution requires me to consider all the permutations of paths between all the shops, and is a classic (and extremely difficult) combinatorial problem. Similar problems arise throughout business and industry, for example in scheduling flight departure times at airports or having an efficient postal sorting system.


pages: 506 words: 146,607

Confessions of a Wall Street Analyst: A True Story of Inside Information and Corruption in the Stock Market by Daniel Reingold, Jennifer Reingold


barriers to entry, Berlin Wall, corporate governance, estate planning, Fall of the Berlin Wall, George Gilder, high net worth, informal economy, margin call, new economy,, rolodex, Saturday Night Live, shareholder value, short selling, Silicon Valley, stem cell, Telecommunications Act of 1996, thinkpad, traveling salesman

He certainly didn’t know much about Jack’s “special” approach to the analyst’s role, though I supposed he knew Jack could move stocks far more powerfully than the rest of us. It was a bit of a problem for CSFB, since its bankers had had the closest relationship with Chuck Noski’s predecessor, Dan Somers, whom AT&T’s CEO, Mike Armstrong, had just sent out 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 in have been the same, and this one was no different. The bankers proffered their services, and CSFB wireless analyst Cindy Motz and I talked about our research. AT&T executives asked us questions, such as how could they best reach retail investors if they went with CSFB, which didn’t have retail brokers or customers, what was the right price for the shares, and what aspects of the company should be emphasized during the road show.


pages: 706 words: 120,784

The Joy of Clojure by Michael Fogus, Chris Houser


cloud computing, domain-specific language, Douglas Hofstadter,, finite state, Gödel, Escher, Bach, haute couture, Paul Graham, rolodex, traveling salesman

We suggest you try asking the authors some challenging questions lest their interest stray! The Author Online forum and the archives of previous discussions will be accessible from the publisher’s website as long as the book is in print. About the cover illustration The figure on the cover of The Joy of Clojure is captioned “The Confidence Man,” which, in 19th century France, could mean anything from a healer or medicine man to a card shark or money lender or traveling salesman. The illustration is taken from a 19th-century edition of Sylvain Maréchal’s four-volume compendium of regional dress customs published in France. Each illustration is finely drawn and colored by hand. The rich variety of Maréchal’s collection reminds us vividly of how culturally apart the world’s towns and regions were just 200 years ago. Isolated from each other, people spoke different dialects and languages.


Jennifer Morgue by Stross, Charles


call centre, correlation does not imply causation, disintermediation, dumpster diving, Etonian, haute couture, interchangeable parts, Maui Hawaii, mutually assured destruction, planetary scale, RFID, Silicon Valley, Skype, slashdot, stem cell, telepresence, traveling salesman, Turing machine

My wards blipped slightly as her script kicked in, but that doesn't have to mean she's a robot, does it? We make it with one hundred percent natural ingredients, like the bottom tenth percentile of our sales force, the ones who don't get invited to this end of the marketing conference by the Queen Bee. Maybe Kitty's just a natural void, only too happy to be filled by the passing enthusiasm of the traveling salesman invocation, but somehow I doubt it: that kind of perfect vacuum doesn't come cheap. I scuff my left heel on the ground. If I switched it on, the Tiilinghast resonator that Brains installed in my shoe would let me see the sales-daemon riding her spine like a grotesquely bloated digger wasp, but I'd just as soon keep my lunch — and anyway the first law of demonoiogy is that if you can see it, // can see you.


pages: 377 words: 115,122

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


8-hour work day, Albert Einstein, Asperger Syndrome, Bill Gates: Altair 8800, call centre, crowdsourcing, David Brooks, delayed gratification, deliberate practice, game design, hive mind, index card, indoor plumbing, Isaac Newton, knowledge economy, knowledge worker, Mahatma Gandhi, Menlo Park, meta analysis, meta-analysis, Mikhail Gorbachev, new economy, popular electronics, Ralph Waldo Emerson, ride hailing / ride sharing, Rosa Parks, shareholder value, Silicon Valley, Steve Jobs, Steve Wozniak, telemarketer, The Wisdom of Crowds, traveling salesman, Walter Mischel, web application, white flight

“Your grades and social status depend on it. It’s just the norm here. Everyone around you is speaking up and being social and going out.” “Isn’t there anyone on the quieter side?” I ask. They look at me curiously. “I couldn’t tell you,” says the first student dismissively. Harvard Business School is not, by any measure, an ordinary place. Founded in 1908, just when Dale Carnegie hit the road as a traveling salesman and only three years before he taught his first class in public speaking, the school sees itself as “educating leaders who make a difference in the world.” President George W. Bush is a graduate, as are an impressive collection of World Bank presidents, U.S. Treasury secretaries, New York City mayors, CEOs of companies like General Electric, Goldman Sachs, Procter & Gamble, and, more notoriously, Jeffrey Skilling, the villain of the Enron scandal.


pages: 513 words: 141,963

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


Airbnb, centre right, failed state, glass ceiling, illegal immigration, McJob, Naomi Klein, placebo effect, profit motive, RAND corporation, Ronald Reagan, science of happiness, Steven Pinker, traveling salesman, War on Poverty

He could manipulate numbers and odds in a way that startled people. From the age of twelve, he knew that his father wouldn’t dream of carrying cash from the setting of the sun on Friday night to the end of the Sabbath the next day, so Arnold stole the money from his wallet, played craps, and won so often and so big he could always replace the cash12 without anyone’s noticing. By the time he ran away13 from home at seventeen to be a traveling salesman, Arnold knew he could crack card games better than anyone else. He was starting to regard himself as a superman, far above the dumb herd, explaining later: “There are two million fools14 to one brainy man.” He was the brainy man, and he was going to get his due from the fools. And the Brain—as he now insisted on being called—soon discovered the greatest truth of gambling: the only way to win every time is to own the casino.


pages: 404 words: 118,759

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


California gold rush, interchangeable parts, Maui Hawaii, new economy, New Journalism, Plutocrats, plutocrats, Ralph Waldo Emerson, Ronald Reagan, South of Market, San Francisco, South Sea Bubble, transcontinental railway, traveling salesman

By 1874, he was no longer the Next Big Thing, the literary heartthrob who fascinated the nation with tales of gunslingers and gold seekers. He was a pale echo of his past self, doing anything he could to survive. His cratering finances had forced him onto the lecture circuit. He hated public speaking, but he had no choice. He needed money to survive. So while Twain put down roots in Hartford and embarked on the most creative period of his life, Harte wandered the continent like a traveling salesman, surviving blizzards and broken-down trains, sleeping in hotels and Pullman cars, playing to crowds from Toronto to Topeka. People came out to see a real live westerner. He could sense their disappointment the moment he took the stage. He wore fancy suits, not the coarse garb of his characters. “[I]f I had been more herculean in proportions, with a red shirt and top boots, many of the audience would have felt a deeper thrill,” he recalled.


pages: 464 words: 117,495

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


additive manufacturing, Atul Gawande, backtesting, Benoit Mandelbrot, buy low sell high, Checklist Manifesto, deliberate practice, diversification, Elliott wave, endowment effect, loss aversion, mandelbrot fractal, margin call, offshore financial centre, paper trading, Ponzi scheme, price stability, psychological pricing, quantitative easing, random walk, risk tolerance, short selling, South Sea Bubble, systematic trading, The Wisdom of Crowds, transaction costs, transfer pricing, traveling salesman, tulip mania

These 12 steps, described in the book Twelve Steps and Twelve Traditions, refer to 12 stages of personal growth. Recovering alcoholics attend meetings where they share their experiences with other recovering alcoholics, supporting each other in their sobriety. Any member can get a sponsor—another AA member whom he can call for support when he feels the urge to drink. AA was founded in the 1930s by two alcoholics—a doctor and a traveling salesman who began meeting to help each other stay sober. They developed a system that worked so well, others began to join them. AA has only one goal—to help its members stay sober. It doesn't ask for money, takes no political positions, and runs no promotional campaigns. AA keeps growing thanks only to word of mouth and owes its success only to its effectiveness. The 12-step program of AA is so effective that people with other problems now use it.


pages: 473 words: 156,146

They Gave Me a Seafire by Commander R 'Mike' Crosley Dsc Rn


friendly fire, IFF: identification friend or foe, Isaac Newton, traveling salesman

The one from vertically above was, however, much easier, just a rolling pullout from a vertical dive. Back at Henstridge I became the Station PGI. I fixed up a ‘private’ Miles Master II with all manner of cameras and gunsights, and took petrified pupils in the back to show them how upward and downward ‘Jesi’ should be done. Not only that, I was sent all over the place in England and Scotland as a travelling salesman, seeing very little of my immobile Wren as a result. Many of the pupils joining the FAA at this time in the war found it difficult to make quarter attacks. It over-loaded the human computer to have to judge distances, angles, approach speeds, convergences, line of target flight and deflection when shooting — and flying at the same time. The first problem to solve was how to position the fighter in the right part of the sky before starting an attack.


pages: 523 words: 159,884

The Great Railroad Revolution by Christian Wolmar


1919 Motor Transport Corps convoy, accounting loophole / creative accounting, banking crisis, Bay Area Rapid Transit, big-box store, collective bargaining, cross-subsidies, intermodal, James Watt: steam engine, Ponzi scheme, quantitative easing, railway mania, Ralph Waldo Emerson, refrigerator car, Silicon Valley, strikebreaker, too big to fail, trade route, transcontinental railway, traveling salesman, union organizing, urban sprawl

Interestingly, this was a rare period in American railroad history when passenger growth far outpaced the rise in the carriage of freight. In a way, this was not surprising. When it came to passenger travel, the railroads had it all, cornering every market since, for most journeys, there remained no viable alternative. Apart from a few trips that could be made by boat, either along the coast or on lakes, the railroads catered to everyone, “from the travelling salesman who was making his way through his territory in ten and twenty mile hops to the well-to-do family setting out in Pullman drawing room comfort for a tour of the great American West.”5 Although freight carriage did grow in this period, the marketing efforts of the railroad, together with the increase in population and greater prosperity generally, resulted in a far faster rate of growth for passenger traffic.


pages: 456 words: 123,534

The Dawn of Innovation: The First American Industrial Revolution by Charles R. Morris


air freight, British Empire, business process, California gold rush, clean water, colonial exploitation, computer age, Dava Sobel,, glass ceiling, hiring and firing, if you build it, they will come, interchangeable parts, Isaac Newton, Jacquard loom, Jacquard loom, James Hargreaves, James Watt: steam engine, John Harrison: Longitude, joint-stock company, lone genius, manufacturing employment, new economy, New Urbanism, On the Economy of Machinery and Manufactures, purchasing power parity, QWERTY keyboard, refrigerator car, Robert Gordon, spinning jenny, Stephen Hawking, The Wealth of Nations by Adam Smith, trade route, transcontinental railway, traveling salesman

Agricultural employment accounted for fewer than a third of jobs in the Northeast by 1860 but still more than 60 percent in the Midwest, and a nearly unchanging three-quarters in the South, which remained dependent on King Cotton.1 The Northeast still commanded about half of the country’s total income, but average incomes in the Northeast and the Midwest had begun to converge and would be approaching parity by the end of the century.2 The Northeast’s large income advantage reflected both its lower reliance on agriculture and greater concentration of good-paying, white-collar, service employment—banking, insurance, accounting, wholesale and retail trade. The white-collar pay advantage was particularly strong in the nineteenth century. Edward Tailer was twenty in 1850, when he started work as an assistant clerk for a New York dry goods importer while complaining of his $50 annual salary. But within two years, and after two job changes, he was making $1,000—a solid middle-class income. He then went on the road as a traveling salesman at $1,200 and had his own business when he was twenty-five.3 TABLE 6.1 Population by Region, 1790–1860a Americans were the best-fed people in the world—already by the mid-eighteenth century their nutritional intake was about the same as that of 1960s Americans. They were taller by several inches than the average European and commensurately heavier. The average work output of Americans was plausibly larger than that of Europeans, an effect that was partly offset by the Europeans’ adaptive smaller stature.ba4 Oddly, although American incomes and dietary provision continued to rise, height and mortality data suggest a major decline in Americans’ health over about a thirty-year period starting in the 1840s.


pages: 667 words: 186,968

The Great Influenza by John M. Barry


Albert Einstein, Brownian motion, centralized clearinghouse, Chance favours the prepared mind, conceptual framework, discovery of penicillin, double helix, Fellow of the Royal Society, germ theory of disease, index card, Louis Pasteur, Marshall McLuhan, Mason jar, means of production, statistical model, the medium is the message, the scientific method, traveling salesman, women in the workforce

Blue neither reprimanded Parsons for fomenting fear nor suggested that he take another tack. Another story read, “The Germs Are Coming. An epidemic of influenza is spreading or being spread, (we wonder which).”… Those and similar charges created enough public sentiment to force Public Health Service laboratories to waste valuable time and energy investigating such possible agents of germ warfare as Bayer aspirin. Parsons’s territory bordered on Alabama and there a traveling salesman from Philadelphia named H. M. Thomas was arrested on suspicion of being a German agent and spreading influenza—death. Thomas was released, but on October 17, the day after influenza had killed 759 people in Philadelphia, his body was found in a hotel room with his wrists cut—and his throat slit. Police ruled it suicide. Everywhere, as in Philadelphia, two problems developed: caring for the sick, and maintaining some kind of order.


pages: 666 words: 181,495

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


23andMe, AltaVista, Anne Wojcicki, Apple's 1984 Super Bowl advert, autonomous vehicles, book scanning, Brewster Kahle, Burning Man, business process, clean water, cloud computing, crowdsourcing, Dean Kamen, discounted cash flows, don't be evil, Douglas Engelbart, El Camino Real, fault tolerance, Firefox, Gerard Salton, Google bus, Google Chrome, Google Earth, Googley, HyperCard, hypertext link, IBM and the Holocaust, informal economy, information retrieval, Internet Archive, Jeff Bezos, Kevin Kelly, Mark Zuckerberg, Menlo Park, optical character recognition, PageRank, Paul Buchheit, Potemkin village, prediction markets, recommendation engine, risk tolerance, Sand Hill Road, Saturday Night Live, search inside the book, second-price auction, Silicon Valley, skunkworks, Skype, slashdot, social graph, social software, social web, spectrum auction, speech recognition, statistical model, Steve Ballmer, Steve Jobs, Steven Levy, Ted Nelson, telemarketer, trade route, traveling salesman, Vannevar Bush, web application, WikiLeaks, Y Combinator

Though Charlie’s in Building 40 was the most spacious café, with the broadest menu, food-snob Googlers regarded it as a tourist attraction; it was the place Googlers took their guests to, and it was often populated by people attending conferences on campus. The other eateries were more like restaurants beloved by a neighborhood clientele. Walking around Google offices, you would occasionally see charts to help a product group keep track of their lunch venues: a foodie version of the celebrated Traveling Salesman Problem. At all the cafés, the menu choices reflected a proscriptive view of nutrition. Google chef Josef Desimone once told a magazine, “We’re here to educate employees on why agave-based soda is better for you than Coca-Cola.” Café 150 limited its menus to items grown or produced within 150 miles of campus. A café called 5IVE in another building prepared its dishes with five ingredients or less.


pages: 603 words: 182,781

Aerotropolis by John D. Kasarda, Greg Lindsay


3D printing, air freight, airline deregulation, airport security, Akira Okazaki, Asian financial crisis, back-to-the-land, barriers to entry, Berlin Wall, big-box store, blood diamonds, borderless world, British Empire, call centre, carbon footprint, Clayton Christensen, cleantech, cognitive dissonance, conceptual framework, credit crunch, David Brooks, David Ricardo: comparative advantage, Deng Xiaoping, deskilling, edge city, Edward Glaeser, failed state, food miles, Ford paid five dollars a day, Frank Gehry, fudge factor, full employment, future of work, Geoffrey West, Santa Fe Institute, George Gilder, global supply chain, global village, gravity well, Haber-Bosch Process, Hernando de Soto, hive mind, if you build it, they will come, illegal immigration, inflight wifi, interchangeable parts, intermodal, invention of the telephone, inventory management, invisible hand, Jane Jacobs, Jeff Bezos, Kangaroo Route, knowledge worker, kremlinology, labour mobility, Marshall McLuhan, Masdar, McMansion, megacity, Menlo Park, microcredit, Network effects, New Economic Geography, new economy, New Urbanism, oil shale / tar sands, oil shock, peak oil, Peter Thiel,, pink-collar, pre–internet, RFID, Richard Florida, Ronald Coase, Ronald Reagan, savings glut, Seaside, Florida, Shenzhen was a fishing village, Silicon Valley, Silicon Valley startup, Skype, smart cities, smart grid, South China Sea, South Sea Bubble, sovereign wealth fund, special economic zone, spice trade, spinning jenny, stem cell, Steve Jobs, supply-chain management, sustainable-tourism, telepresence, the built environment, The Chicago School, The Death and Life of Great American Cities, The Nature of the Firm, thinkpad, Thomas L Friedman, Thomas Malthus, Tony Hsieh, trade route, transcontinental railway, transit-oriented development, traveling salesman, trickle-down economics, upwardly mobile, urban planning, urban renewal, urban sprawl, walkable city, white flight, Yogi Berra

., “and the density feels very natural to me,” she said. Her neighbors—or at least the ones she’d met— were fellow transplants from Maryland and Boston. She had moved here for the lifestyle but traveled often for work as an executive coach. It mattered to her that DIA was an eighteen-minute commute on the highway. Stapleton’s brownstones seemed to collect the self-motivated. Living on her block were a traveling salesman raised on Long Island, a stay-at-home software engineer, and a graphic designer who proudly informed me she had been a flight attendant on America West for twenty-five years. If Holmes had one complaint about Stapleton, it wasn’t that it sometimes felt like Disneyland, as her neighbors put it. (“A good Disneyland,” one of them specified, “not a cheesy one.”) “I’ve been to Celebration,” she said, “and that feels fake to me.


pages: 683 words: 203,624

The Victorian City: Everyday Life in Dickens' London by Judith Flanders


anti-work, centre right, Corn Laws, John Snow's cholera map, Ralph Waldo Emerson, traveling salesman, urban sprawl, working poor

In his youth, Dickens described ‘lounging one evening, down Oxford-street’; later, as a magazine editor, he recommended to his journalists that they actively choose their subjects in the city that he still found a daily novelty: ‘Suggest to him Saturday night in London, or London Markets…the most extraordinary men…the most extraordinary things…the strangest Shows – and the wildest’. In the decade before his death, he assumed the guise of ‘The Uncommercial Traveller’ (a ‘traveller’ being a travelling salesman), ‘always on the road…I travel for the great house of Human Interest Brothers…I am always wandering here and there…seeing many little things, and some great things, which, because they interest me, I think may interest others.’ Previous essays about London, by authors such as Charles Lamb and Leigh Hunt, had been filled with history, with learned asides, with a great panoply of education.


pages: 686 words: 201,972

Drink: A Cultural History of Alcohol by Iain Gately


barriers to entry, British Empire, California gold rush, delayed gratification, Deng Xiaoping, Edward Lloyd's coffeehouse, Fellow of the Royal Society, Gordon Gekko, greed is good, Haight Ashbury, Hernando de Soto, imperial preference, invisible hand, joint-stock company, Louis Pasteur, megacity, music of the spheres, Peace of Westphalia, refrigerator car, Ronald Reagan, South Sea Bubble, spice trade, strikebreaker, the scientific method, Tim Cook: Apple, trade route, traveling salesman, Upton Sinclair, V2 rocket, working poor

In early scenes, the only overt drunks are American visitors who show no shame in their condition, indeed advocate it as an acceptable state. Toward the end of the film Marcello has acquired the same habit, and becomes aggressive and irrational when under the influence. La Dolce Vita also illustrates the penetration of foreign drinks in Roman society. Its fashionable characters drink vodka, gin fizzes, and named brands of scotch whisky. In contrast, the unfashionable, such as Marcello’s father, a traveling salesman, stick to traditional stimulants such as champagne when they want to celebrate. There are, finally, hints of the revival in Italian wines that occurred in the decade following the release of the film. In response to EEC legislation, a quality regime was introduced—the Denominazione d’Origine Controllata (Denomination of Controlled Origin or DOC), loosely based on the French AOC model, which defined regions, grapes, and production methods for wines such as Barolo and Barbaresco from Piedmont, and Brunello di Montalcino from Tuscany.


pages: 548 words: 174,644

Boyd: The Fighter Pilot Who Changed the Art of War by Robert Coram


desegregation, inventory management, Iridium satellite, Joseph Schumpeter, Mason jar, RAND corporation, Ronald Reagan, Thomas Kuhn: the structure of scientific revolutions, Toyota Production System, traveling salesman

For the living room, where her growing family would spend long winter evenings, she bought a cast iron gas heater, and to brighten those winter evenings she covered the walls with pink paper. The living room’s other feature was a black Steinway, a gift from Hubert. Elsie liked to play it, having taught piano before she was married. For Erie in the late 1920s it was a comfortable middle-class home. Hubert Boyd was a traveling salesman for HammerMill Paper Company, and a job at the “HammerMill” was both prestigious and well-paying. Elsie Boyd was the daughter of Julia and Rudolph Beyer. Her father farmed a small piece of land just south of Erie. Elsie was a German Presbyterian, an ample woman with enormous pride and the self-confidence to freely express her beliefs, many of which were synthesized in pithy expressions such as “The world is not the way you want it to be.


pages: 762 words: 206,865

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


Berlin Wall, cuban missile crisis, Deng Xiaoping, desegregation, Fall of the Berlin Wall, full employment, index card, Mikhail Gorbachev, open borders, Ronald Reagan, trade liberalization, traveling salesman

Two days later, on May 19, the Kennedy administration officially announced what the press had been reporting from leaks for several days: The president would meet with Khrushchev in Vienna on June 3 and 4 after seeing de Gaulle in Paris. Western European and U.S. commentators worried that a weakened president was heading to Vienna at a disadvantage. The intellectual weekly Die Zeit compared Kennedy to a traveling salesman whose business had fallen on bad times and who was hoping to improve his prospects by negotiating directly with the competition. In its review of European opinion, the Wall Street Journal said Kennedy was projecting the “strong impression…of a faltering America desperately trying to regain leadership of the West in the Cold War.” The influential Swiss daily Neue Zürcher Zeitung despaired that the summit was being badly prepared by the Americans, and that Kennedy had abandoned his prerequisite that the Kremlin demonstrate a changed attitude before any such meeting take place.


pages: 559 words: 174,054

The World of Caffeine: The Science and Culture of the World's Most Popular Drug by Bennett Alan Weinberg, Bonnie K. Bealer


British Empire, clean water, easy for humans, difficult for computers, Edmond Halley, Edward Lloyd's coffeehouse, Haight Ashbury, Honoré de Balzac, Isaac Newton, Johann Wolfgang von Goethe, Lao Tzu, placebo effect, spice trade, trade route, traveling salesman

There is nothing new about the awareness of caffeine intoxication, for it has been well described as a psychiatric disorder for more than a hundred years. Yet despite long-standing recognition, which perhaps began with the coining of the Arabic word “marqaha” or “caffeine high,” in the sixteenth century, there is, even today, little information available about its prevalence or incidence. In 1896 J.T.Rugh17 reported the case of a traveling salesman who had resorted to excessive coffee consumption to maintain an intense pace of work and was troubled by nervousness, involuntary contractions in the arms and legs, a sense of impending danger, and sleep disturbance. Similar reports of caffeine intoxication first appear in medical literature from the middle of the 1800s, and the profile of common symptoms remains unchanged today. The most common are anxiety or nervousness, insomnia, gastrointestinal disturbances, irregular heartbeat, tremors, and psychomotor agitation.


pages: 598 words: 169,194

Bernie Madoff, the Wizard of Lies: Inside the Infamous $65 Billion Swindle by Diana B. Henriques


accounting loophole / creative accounting, airport security, Albert Einstein, banking crisis, Bernie Madoff, British Empire, centralized clearinghouse, collapse of Lehman Brothers, diversified portfolio, Donald Trump, dumpster diving, financial deregulation, forensic accounting, Gordon Gekko, index fund, locking in a profit, mail merge, merger arbitrage, Plutocrats, plutocrats, Ponzi scheme, Potemkin village, random walk, Renaissance Technologies, riskless arbitrage, Ronald Reagan, short selling, Small Order Execution System, sovereign wealth fund, too big to fail, transaction costs, traveling salesman

But, even there, success would have meant climbing a long, unsteady ladder for a long, uncertain period of time. Although he had absorbed his father’s prickly preference for being his own boss, Bernie had no desire to become a lawyer. As a child, he expected to join his father’s sporting goods business and eventually run it, but after the bankruptcy filing in 1951, he decided he’d like to sell sports equipment as a “manufacturer’s rep”, a sort of travelling salesman who wouldn’t be tied down to the grey-flannel life of a law firm or corporate office. Most of the schoolmates who have offered their memories of Madoff’s teenage and university years in the 1950s remembered the scrappy lawn-sprinkler installation business he got rolling in secondary school, after his father’s businesses failed. They remembered thinking that he seemed like a young man on the make, who had felt the sting of doing without and dreamed of doing better.


pages: 585 words: 165,304

Trust: The Social Virtue and the Creation of Prosperity by Francis Fukuyama


barriers to entry, Berlin Wall, blue-collar work, business climate, capital controls, collective bargaining, corporate governance, deindustrialization, Deng Xiaoping, deskilling, double entry bookkeeping, equal pay for equal work, European colonialism, Francis Fukuyama: the end of history, Frederick Winslow Taylor, full employment, George Gilder, glass ceiling, global village, hiring and firing, industrial robot, Jane Jacobs, job satisfaction, joint-stock company, joint-stock limited liability company, Joseph Schumpeter, labour market flexibility, labour mobility, land reform, low skilled workers, manufacturing employment, mittelstand, price mechanism, profit maximization, RAND corporation, rent-seeking, Ronald Coase, Silicon Valley, Steve Jobs, Steve Wozniak, The Death and Life of Great American Cities, The Nature of the Firm, the scientific method, The Wealth of Nations by Adam Smith, transaction costs, transfer pricing, traveling salesman, union organizing

This cohesion served them well in the business world, since business transactions depend to a great degree on trust. In traveling through the United States, Weber observed that many businessmen would introduce themselves as some kind of Christian believer, in order to establish credentials for honesty and trustworthiness. In one case, On a long railroad journey through what was then Indian territory, the author, sitting next to a traveling salesman of “undertaker’s hardware” (iron letters for tombstones), casually mentioned the still impressively strong church-mindedness. Thereupon the salesman remarked, “Sir, for my part everybody may believe or not believe as he pleases; but if I saw a farmer or a businessman not belonging to any church at all, I wouldn’t trust him with fifty cents. Why pay me, if he doesn’t believe in anything?”14 Weber noted as well that the small sectarian communities created natural networks through which businessmen could hire employees, find customers, open lines of credit, and the like.


pages: 636 words: 202,284

Piracy : The Intellectual Property Wars from Gutenberg to Gates by Adrian Johns


banking crisis, Berlin Wall, British Empire, Buckminster Fuller, business intelligence, Corn Laws, demand response, distributed generation, Douglas Engelbart, Edmond Halley, Ernest Rutherford, Fellow of the Royal Society, full employment, Hacker Ethic, Howard Rheingold, informal economy, invention of the printing press, Isaac Newton, James Watt: steam engine, John Harrison: Longitude, Marshall McLuhan, Mont Pelerin Society, new economy, New Journalism, Norbert Wiener, pirate software, Republic of Letters, Richard Stallman, road to serfdom, Ronald Coase, software patent, South Sea Bubble, Steven Levy, Stewart Brand, Ted Nelson, the scientific method, traveling salesman, Whole Earth Catalog

As pirate king, he often used the alias John Fisher, coined apparently because he had at one point been a fishmonger of some kind; and he also had a number of other monikers, among them “the colonel.” His mother had been a printer, and he had served an apprenticeship, probably in her house. He was experienced in the business, having worked in newspapers for fifteen years. But since then he had tried out various other trades, including that of traveling salesman. He had once been imprisoned for embezzlement, which he defended as appropriating what were rightfully his wages when his erstwhile employer went bankrupt. Since the 1902 law, however, he had seen an opportunity to earn a windfall from his original trade, and had become the nation’s leading music pirate. His business card (for J. Fisher and Co.) listed his address as the Rose and Crown in Goswell Road, which made Tum Tum his agent.


pages: 1,073 words: 302,361

Money and Power: How Goldman Sachs Came to Rule the World by William D. Cohan


asset-backed security, Bernie Madoff, buttonwood tree, collateralized debt obligation, corporate governance, credit crunch, Credit Default Swap, credit default swaps / collateralized debt obligations, diversified portfolio, fear of failure, financial innovation, fixed income, Ford paid five dollars a day, Goldman Sachs: Vampire Squid, Gordon Gekko, high net worth, hiring and firing, hive mind, Hyman Minsky, interest rate swap, London Interbank Offered Rate, Long Term Capital Management, margin call, market bubble, merger arbitrage, moral hazard, mortgage debt, paper trading, passive investing, Ponzi scheme, price stability, profit maximization, risk tolerance, Ronald Reagan, Saturday Night Live, South Sea Bubble, time value of money, too big to fail, traveling salesman, value at risk, yield curve, Yogi Berra

Still in its infancy at the start of the twentieth century, the task of raising capital—dubbed “underwriting”—became one of the most crucial roles Wall Street would perform for corporate clients eager to expand their workforces and their factories, and led to the creation of American capitalism, one of the country’s most important exports. Henry Goldman, who ironically had dropped out 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 business, which meant taking calculated risks for short periods of time by buying the debt or equity securities of its corporate clients before turning around and quickly selling these securities to investors who had been previously identified and were eager to buy them, assuming they had been priced correctly.


pages: 1,104 words: 302,176

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


3D printing, Affordable Care Act / Obamacare, airline deregulation, airport security, Apple II, barriers to entry, big-box store, blue-collar work, Capital in the Twenty-First Century by Thomas Piketty, clean water, collective bargaining, computer age, deindustrialization, Detroit bankruptcy, discovery of penicillin, Donner party, Downton Abbey, Edward Glaeser,, Erik Brynjolfsson, everywhere but in the productivity statistics, feminist movement, financial innovation, full employment, George Akerlof, germ theory of disease, glass ceiling, high net worth, housing crisis, immigration reform, impulse control, income inequality, income per capita, indoor plumbing, industrial robot, inflight wifi, interchangeable parts, invention of agriculture, invention of air conditioning, invention of the telegraph, invention of the telephone, inventory management, James Watt: steam engine, Jeff Bezos, jitney, job automation, John Maynard Keynes: Economic Possibilities for our Grandchildren, labor-force participation, Loma Prieta earthquake, Louis Daguerre, Louis Pasteur, low skilled workers, manufacturing employment, Mark Zuckerberg, market fragmentation, Mason jar, McMansion, Menlo Park, minimum wage unemployment, mortgage debt, mortgage tax deduction, new economy, Norbert Wiener, obamacare, occupational segregation, oil shale / tar sands, oil shock, payday loans, Peter Thiel, pink-collar, Productivity paradox, Ralph Nader, Ralph Waldo Emerson, refrigerator car, rent control, Robert X Cringely, Ronald Coase, school choice, Second Machine Age, secular stagnation, Skype, stem cell, Steve Jobs, Steve Wozniak, Steven Pinker, The Market for Lemons, Thomas Malthus, total factor productivity, transaction costs, transcontinental railway, traveling salesman, Triangle Shirtwaist Factory, Unsafe at Any Speed, Upton Sinclair, upwardly mobile, urban decay, urban planning, urban sprawl, washing machines reduced drudgery, Washington Consensus, Watson beat the top human players on Jeopardy!, We wanted flying cars, instead we got 140 characters, working poor, working-age population, Works Progress Administration, yield management

In the beginning of the nineteenth century, “payment of debts was a virtue and inability to pay them a mortal sin.”1 Credit was developed earlier and more freely in the United States than in many European countries, in part because the typical American farmer (outside the south) owned his own land, whereas in Europe, tenant farming was more common, with large estates owned by upper-class families through inheritance over generations. Whereas in Europe the avaricious lender faced a social stigma for ideological reasons, usually religious, in the United States the borrower experienced the stigma, being considered a “penniless failure.”2 The traveling salesman supplemented the role of the country store in providing credit to isolated farms and small towns alike. Finance for these salesmen was provided by wholesalers who were eager to sell their goods in the remote parts of rural America, and the back-up finance ultimately traced its way back to Chicago or New York. Such was the heavily leveraged world of frontier exchange. Everyone owed money to everyone else, and for much of the year the only way to sell anything at all was to do so “on time.”


pages: 1,351 words: 404,177

Nixonland: The Rise of a President and the Fracturing of America by Rick Perlstein


affirmative action, Alistair Cooke, Bay Area Rapid Transit, Berlin Wall, Bretton Woods, cognitive dissonance, cuban missile crisis, delayed gratification, desegregation, East Village, European colonialism, full employment, Golden Gate Park, Haight Ashbury, immigration reform, In Cold Blood by Truman Capote, index card, indoor plumbing, Mahatma Gandhi, Marshall McLuhan, Monroe Doctrine, New Urbanism, Own Your Own Home, Plutocrats, plutocrats, price mechanism, Ralph Nader, RAND corporation, rolodex, Ronald Reagan, the medium is the message, traveling salesman, upwardly mobile, urban planning, urban renewal, walking around money, War on Poverty, Whole Earth Catalog

He quoted a judge’s descriptions in a case considering short movies designed to be displayed with coin-operated projectors in bars, so furtive they didn’t even have proper names; in the one labeled O-7, for instance, “the model wears a garter belt and sheer transparent panties through which the pubic hair and external parts of genitalia are clearly visible…. At one time the model pulls her panties down so that the pubic hair is exposed to view…the focus of the camera is emphasized on the pubic and rectal region, and the model continuously uses her tongue and mouth to simulate a desire for, or enjoyment of, acts of a sexual nature.” And Justice Fortas didn’t find this obscene? Like a traveling salesman, Clancy brought with him a sample case: a thirty-five-minute documentary reel; a complete and uncut print of the masterpiece O-7. Clancy concluded his statement by requesting “the opportunity to show both the documentary and the film to the full committee and to the press, recognizing that the film is not the type of subject matter which should be shown to the general public. We would ask the committee for permission to do this, possibly in a different room.


pages: 1,157 words: 379,558

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


air freight, Albert Einstein, California gold rush, cognitive dissonance, desegregation, double entry bookkeeping, family office, feminist movement, full employment, ghettoisation, Indoor air pollution, medical malpractice, Mikhail Gorbachev, Plutocrats, plutocrats, Ralph Nader, Ralph Waldo Emerson, RAND corporation, rent-seeking, risk tolerance, Ronald Reagan, The Chicago School, the scientific method, Torches of Freedom, trade route, transaction costs, traveling salesman, union organizing, upwardly mobile, urban planning, urban renewal, War on Poverty

Fresh out of college in the middle of the Depression, he went to work as a fifteen-dollar-a-week clerk at the Schulte tobacco counter in the lobby of an office building behind the New York Stock Exchange. It was a sixty-hour work week during which he was obliged to try to foist “push items” on his customers in accord with their manufacturers’ payment for same. Then came a 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 as wrapper for their cigars and his father later became involved in its management while the company was in bankruptcy, Joe Third was spared little of the pain of the drummer’s life. Essentially a quite private person, he applied a native optimism and self-confidence that are essential to effective salesmanship.


pages: 1,744 words: 458,385

The Defence of the Realm by Christopher Andrew


anti-communist, Ayatollah Khomeini, Berlin Wall, British Empire, Clive Stafford Smith, collective bargaining, credit crunch, cuban missile crisis, Desert Island Discs, Etonian, Fall of the Berlin Wall, glass ceiling, illegal immigration, job satisfaction, large denomination, liquidationism / Banker’s doctrine / the Treasury view, Mahatma Gandhi, Mikhail Gorbachev, North Sea oil, Red Clydeside, Robert Hanssen: Double agent, Ronald Reagan, strikebreaker, Torches of Freedom, traveling salesman, union organizing, uranium enrichment, V2 rocket, Vladimir Vetrov: Farewell Dossier, Winter of Discontent

The letter was from one Robert Rosenthal in Copenhagen to ‘Franz Kulbe’ at an address in Berlin which MO5(g) knew to be used by German naval intelligence. It also knew that ‘Franz Kulbe’ was an alias employed by Captain von Prieger of the German Admiralty. Though the letter purported to be a business communication, the Censorship flat-iron revealed writing in secret ink which disclosed that he was about to leave for England disguised as a travelling salesman of cigar lighters. When Rosenthal was arrested in Newcastle, travelling on a US passport, no incriminating evidence was found on him. But when confronted with his intercepted letter to Berlin, he admitted he was German and had been sent by Prieger to spy on the Royal Navy. Though he denied he had sent Prieger information of any value, he also admitted that he had been on two previous wartime espionage missions.