William J. Cook - Böcker

A complete, highly accessible introduction to one of today's most exciting areas of applied mathematics One of the youngest, most vital areas of applied mathematics, combinatorial optimization integrates techniques from combinatorics, linear programming, and the theory of algorithms. Because of its success in solving difficult problems in areas from telecommunications to VLSI, from product distribution to airline crew scheduling, the field has seen a ground swell of activity over the past decade. Combinatorial Optimization is an ideal introduction to this mathematical discipline for advanced undergraduates and graduate students of discrete mathematics, computer science, and operations research. Written by a team of recognized experts, the text offers a thorough, highly accessible treatment of both classical concepts and recent results. The topics include:* Network flow problems* Optimal matching* Integrality of polyhedra* Matroids* NP-completeness Featuring logical and consistent exposition, clear explanations of basic and advanced concepts, many real-world examples, and helpful, skill-building exercises, Combinatorial Optimization is certain to become the standard text in the field for many years to come.

This book presents the latest findings on one of the most intensely investigated subjects in computational mathematics--the traveling salesman problem. It sounds simple enough: given a set of cities and the cost of travel between each pair of them, the problem challenges you to find the cheapest route by which to visit all the cities and return home to where you began. Though seemingly modest, this exercise has inspired studies by mathematicians, chemists, and physicists. Teachers use it in the classroom. It has practical applications in genetics, telecommunications, and neuroscience. The authors of this book are the same pioneers who for nearly two decades have led the investigation into the traveling salesman problem. They have derived solutions to almost eighty-six thousand cities, yet a general solution to the problem has yet to be discovered. Here they describe the method and computer code they used to solve a broad range of large-scale problems, and along the way they demonstrate the interplay of applied mathematics with increasingly powerful computing platforms. They also give the fascinating history of the problem--how it developed, and why it continues to intrigue us.

What is the shortest possible route for a traveling salesman seeking to visit each city on a list exactly once and return to his city of origin? It sounds simple enough, yet the traveling salesman problem is one of the most intensely studied puzzles in applied mathematics--and it has defied solution to this day. In this book, William Cook takes readers on a mathematical excursion, picking up the salesman's trail in the 1800s when Irish mathematician W. R. Hamilton first defined the problem, and venturing to the furthest limits of today's state-of-the-art attempts to solve it. He also explores its many important applications, from genome sequencing and designing computer processors to arranging music and hunting for planets. In Pursuit of the Traveling Salesman travels to the very threshold of our understanding about the nature of complexity, and challenges you yourself to discover the solution to this captivating mathematical problem.

Most of what passes for strategic planning is not strategic at all. It is long-range planning or comprehensive planning, or in some cases just program or project planning. The result is a relinquishment of control to external conditions and circumstances, the perpetuation of obsolete systems, and organizational fragmentation and internal conflict. The opportunity to create new possibilities and realities—the ultimate object of strategy—is lost. Cook maintains that even to attempt strategy there must first be a strategic system, a system that deals with strategic issues, decision-making, and strategic action, which is preceded by strategic thinking. Cook combines these three aspects of strategy into a coherent, powerful concept that reinvigorates strategy with its original forceful meaning: strategos—to lead an army. In this way strategy becomes the means by which communities continuously create artifactual systems to serve extraordinary purposes. His book contains sound, pragmatic theory, original insights into strategic issues, and detailed hands-on guidance on all phases of strategic thinking, planning, and action.Cook explains that stragetics can be expressed as thinking, planning, and action. Strategic thinking will always embrace five arenas: the definition of strategy, the meaning of leaders and leading, the distinction between condition and cause, the nature of systems, and the characteristics of organizations. Strategic planning, as a currently popular management practice, is not what it was originally. The definition has changed. The only definition that captures the original intent is: the means by which a community of people create artifactual systems to serve extraordinary purposes. Dr. Cook points out that strategic action is seldom included in any contemporary intepretation or application of strategy, yet action is both the realization of strategy and the creation of new possibilities beyond strategy. In that sense, strategic action is the end and the beinning of strategics. Thus, Cook takes the traditional idea of strategic planning, infuses it with strategic thinking, and carries it to strategic action. Instead of merely improving what already exists, organizations can create new systems that are capable of what he calls constant emergence—always vital, always creative.

The corporation model of organizations is in terminal decline, says Cook, and is being displaced by what he calls syntagma, a body of persons forming a division of the population of a country. The point he makes by this is that the emerging organization will be no artifact, no fabrication. It will be innately human, and in that sense, organic. His book traces the philosophical and historical development of the modern corporation through Hellenistic-Judeo-Christian theologies, with particular emphases on the social, political, and economic impacts of rationalistic science, impacts such as humanism, democracy, capitalism, and behaviorism. Cook offers an analysis of the critical aspects of the corporation as it exists today, and draws heavily for evidence upon contemporary management theories and practices. In doing so he argues that it is the radical changes going on in society itself that is rendering the traditional corporation obsolete. And, since western civilization is undergoing an epochal shift, the new, emerging corporation can have no resemblance to the old model. He maintains that the organization evolving to replace it will be characterized by common values, mutual purpose, excess capacity, and creative action, and will have two dynamics, what he calls commensuration and essentiality. Only with this kind of human system is it possible to create an organization that solely and exclusively serves the common good. His book is a provocative contribution to the professional and academic literature of several fields, including management, the social sciences, organizational behavior, development, and history, and will be of particular interest as well to certain well informed nonspecialists with concern for the role played the corporation in their societies.

This book constitutes the refereed proceedings of the 9th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2002, held in Cambridge, MA, USA, in May 2002. The 33 revised full papers presented were carefully reviewed and selected from a total of 110 submissions. Among the topics covered are scaling algorithms, flow algorithms, combinatorial optimization algorithms, approximate TSP solutions, graph computations, algorithmic geometry, mixed integer programming, network design, logistic scheduling, constraint solving, resource allocation, matching algorithms, and matroid intersection algorithms.

The editors and authors dedicate this book to Bernhard Korte on the occasion of his seventieth birthday. We, the editors, are happy about the overwhelming feedback to our initiative to honor him with this book and with a workshop in Bonn on November 3–7,2008.Althoughthiswouldbeareasontolookback,wewouldratherliketolook forward and see what are the interesting research directions today. This book is written by leading experts in combinatorial optimization. All - pers were carefully reviewed, and eventually twenty-three of the invited papers were accepted for this book. The breadth of topics is typical for the eld: combinatorial optimization builds bridges between areas like combinatorics and graph theory, submodular functions and matroids, network ows and connectivity, approximation algorithms and mat- matical programming, computational geometry and polyhedral combinatorics. All these topics are related, and they are all addressed in this book. Combi- torial optimization is also known for its numerous applications. To limit the scope, however, this book is not primarily about applications, although some are mentioned at various places. Most papers in this volume are surveys that provide an excellent overview of an activeresearcharea,butthisbookalsocontainsmanynewresults.Highlightingmany of the currently most interesting research directions in combinatorial optimization, we hope that this book constitutes a good basis for future research in these areas.

The editors and authors dedicate this book to Bernhard Korte on the occasion of his seventieth birthday. We, the editors, are happy about the overwhelming feedback to our initiative to honor him with this book and with a workshop in Bonn on November 3–7,2008.Althoughthiswouldbeareasontolookback,wewouldratherliketolook forward and see what are the interesting research directions today. This book is written by leading experts in combinatorial optimization. All - pers were carefully reviewed, and eventually twenty-three of the invited papers were accepted for this book. The breadth of topics is typical for the eld: combinatorial optimization builds bridges between areas like combinatorics and graph theory, submodular functions and matroids, network ows and connectivity, approximation algorithms and mat- matical programming, computational geometry and polyhedral combinatorics. All these topics are related, and they are all addressed in this book. Combi- torial optimization is also known for its numerous applications. To limit the scope, however, this book is not primarily about applications, although some are mentioned at various places. Most papers in this volume are surveys that provide an excellent overview of an activeresearcharea,butthisbookalsocontainsmanynewresults.Highlightingmany of the currently most interesting research directions in combinatorial optimization, we hope that this book constitutes a good basis for future research in these areas.