Included in series
Handbooks in Operations Research and Management Science, 12
Description
The chapters of this Handbook volume covers nine main topics that
are representative of recent theoretical and algorithmic
developments in the field. In addition to the nine papers that
present the state of the art, there is an article on the early
history of the field.
The handbook will be a useful reference to experts in the field
as well as students and others who want to learn about discrete
optimization.
All of the chapters in this handbook are written by authors who
have made significant original contributions to their topics.
Herewith a brief introduction to the chapters of the handbook.
"On the history of combinatorial optimization (until 1960)"
goes back to work of Monge in the 18th century on the assignment
problem and presents six problem areas: assignment,
transportation, maximum flow, shortest tree, shortest path and
traveling salesman.
The branch-and-cut algorithm of integer programming is the
computational workhorse of discrete optimization. It provides the
tools that have been implemented in commercial software such as
CPLEX and Xpress MP that make it possible to solve practical
problems in supply chain, manufacturing, telecommunications and
many other areas. "Computational integer programming and
cutting planes" presents the key ingredients of these
algorithms.
Although branch-and-cut based on linear programming relaxation is
the most widely used integer programming algorithm, other
approaches are needed to solve instances for which branch-and-cut
performs poorly and to understand better the structure of
integral polyhedra. The next three chapters discuss alternative
approaches.
"The structure of group relaxations" studies a family
of polyhedra obtained by dropping certain nonnegativity
restrictions on integer programming problems.
Although integer programming is NP-hard in general, it is
polynomially solvable in fixed dimension. "Integer
programming, lattices, and results in fixed dimension"
presents results in this area including algorithms that use
reduced bases of integer lattices that are capable of solving
certain classes of integer programs that defy solution by branch-and-cut.
Relaxation or dual methods, such as cutting plane
algorithms,progressively remove infeasibility while maintaining
optimality to the relaxed problem. Such algorithms have the
disadvantage of possibly obtaining feasibility only when the
algorithm terminates.Primal methods for integer programs, which
move from a feasible solution to a better feasible solution, were
studied in the 1960's but did not appear to be competitive with
dual methods. However,recent development in primal methods
presented in "Primal integer programming" indicate that
this approach is not just interesting theoretically but may have
practical implications as well.
The study of matrices that yield integral polyhedra has a long
tradition in integer programming. A major breakthrough occurred
in the 1990's with the development of polyhedral and structural
results and recognition algorithms for balanced matrices. "Balanced
matrices" is a tutorial on the subject.
Submodular function minimization generalizes some linear
combinatorial optimization problems such as minimum cut and is
one of the fundamental problems of the field that is solvable in
polynomial time. "Submodular function minimization"
presents the theory and algorithms of this subject.
In the search for tighter relaxations of combinatorial
optimization problems, semidefinite programming provides a
generalization of linear programming that can give better
approximations and is still polynomially solvable. This subject
is discussed in "Semidefinite programming and integer
programming".
Many real world problems have uncertain data that is known only
probabilistically. Stochastic programming treats this topic, but
until recently it was limited, for computational reasons, to
stochastic linear programs. Stochastic integer programming is now
a high profile research area and recent developments are
presented in "Algorithms for stochastic mixed-integer
programming models".
Resource constrained scheduling is an example of a class of
combinatorial optimization problems that is not naturally
formulated with linear constraints so that linear programming
based methods do not work well. "Constraint programming"
presents an alternative enumerative approach that is
complementary to branch-and-cut. Constraint programming,primarily
designed for feasibility problems, does not use a relaxation to
obtain bounds. Instead nodes of the search tree are pruned by
constraint propagation, which tightens bounds on variables until
their values are fixed or their domains are shown to be empty.
Audience
Operation Researchers
Contents
1. On the History of Combinatorial Optimization (till 1960) (A.
Schrijver). 2. Computational Integer Programming and Cutting
Planes (A. Fugenschuh, A. Martin). 3. The Structure of Group
Relaxations (R. R. Thomas). 4. Integer programming, lattices, and
results in fixed dimension (K. Aardal, F. Eisenbrand). 5. Primal
Integer Programming (B. Spille, R. Weismantel). 6. Balanced
Matrices (G. Cornuejols, M. Conforti). 7. Submodular Function
Minimization (T. McCormick). 8. Semidefinite Programming and
Integer Programming (M. Laurent, F. Rendl). 9. Algorithms for
Stochastic Mixed-Integer Programming Models (S. Sen). 10.
Constraint Programming (A. Bockmayr, J.N. Hooker).
Hardbound, ISBN: 0-444-51507-0, 620 pages, publication date: 2005
Description
The aim of this book is to report on the progress realized in
probability theory in the field of dynamic random walks and to
present applications in computer science, mathematical physics
and finance. Each chapter contains didactical material as well as
more advanced technical sections. Few appendices will help
refreshing memories (if necessary!).
Audience
This book is intended for mathematicians, computer scientists and
all researchers interested by recent developments in probability
theory and their applications. The book contains introductory
material for graduate students who are new to the field, as well
as more advanced material for specialists.
Contents
Preface
Part I. Theoretical Aspects
1. Preliminaries on Dynamic Random Walks
2. Limit Theorems for Dynamic Random Walks
3. Recurrence and Transience
4. Dynamic Random Walks in a Random Scenery
5. Ergodic Theorems
6. Dynamic Random Walks on Heisenberg Groups
7. Dynamic Quantum Bernoulli Random Walks
Part II. Applications
8. Distributed Algorithms with Dynamical Random Transitions
9. Data Structures with Dynamical Random Transitions
10. Transient Random Walks on Dynamically Oriented Lattices
11. Asset Pricing in Dynamic (B, s)-Markets
Appendices
References
Index
Bibliographic & ordering Information
Hardbound, ISBN: 0-444-52735-4, 278 pages, publication date: 2006
Studies in Logic and the Foundations of Mathematics, vol.149.
Description
The Curry-Howard isomorphism states an amazing correspondence
between systems of formal logic as encountered in proof theory
and computational calculi as found in type theory. For instance,
minimal propositional logic corresponds to simply typed lambda-calculus,
first-order logic corresponds to dependent types, second-order
logic corresponds to polymorphic types, sequent calculus is
related to explicit substitution, etc. The isomorphism has many
aspects, even at the syntactic level: formulas correspond to
types, proofs correspond to terms, provability corresponds to
inhabitation, proof normalization corresponds to term reduction,
etc. But there is more to the isomorphism than this. For
instance, it is an old idea---due to Brouwer, Kolmogorov, and
Heyting---that a constructive proof of an implication is a
procedure that transforms proofs of the antecedent into proofs of
the succedent; the Curry-Howard isomorphism gives syntactic
representations of such procedures. The Curry-Howard isomorphism
also provides theoretical foundations for many modern proof-assistant
systems (e.g. Coq). This book give an introduction to parts of
proof theory and related aspects of type theory relevant for the
Curry-Howard isomorphism. It can serve as an introduction to any
or both of typed lambda-calculus and intuitionistic logic.
Audience
Graduate students, lecturers and researchers in logic and
theoretical computer science. Also for graduate students,
lecturers and researchers in philosophy and mathematics.
Contents
Preface Outline Acknowledgements 1. Typefree lambda-calculus 2.
Intuitionistic logic 3. Simply typed lambdacalculus 4. The Curry-Howard
isomorphism 5. Proofs as combinators 6. Classical logic and
control operators 7. Sequent calculus 8. Firstorder logic 9.
Firstorder arithmetic 10. Godel's system T 11. Secondorder logic
and polymorphism 12. Secondorder arithmetic 13. Dependent types
14. Pure type systems and the lambda-cube 15. Solutions and hints
to selected exercises 16. Solutions for chapter 6 Appendix A
Mathematical Background Appendix B Solutions to Selected
Exercises Bibliography Index
Hardbound, ISBN: 0-444-52077-5, publication date: 2006
Edited by Dana Richards
Finally collected in one volume, Martin Gardner's immensely
popular short puzzles?along with a few new ones from the master.
FOR MORE THAN twenty-five years, Martin Gardner was Scientific
American's renowned provocateur of popular math. His yearly
gatherings of short and inventive problems were easily his most
anticipated math columns. Loyal readers would savor the wit and
elegance of his explorations in physics, probability, topology,
and chess, among others. Grouped by subject and arrayed from
easiest to hardest, the puzzles gathered here, which complement
the lengthier, more involved problems in The Colossal Book of
Mathematics, have been selected by Gardner for their
illuminating? and often bewildering?solutions. Filled with over
300 illustrations, this new volume even contains nine new
mathematical gems that Gardner, now ninety, has been gathering
for the last decade. No amateur or expert math lover should be
without this indispensable volume?a capstone to Gardner's seventy-year
career.
"A remarkable retrospective of [Gardner's] astonishingly
influential career as an expositor extraordinaire."? John
Allen Paulos, author of Innumeracy
MARTIN GARDNER is the author of more than seventy books,
including Fads and Fallacies in the Name of Science, The
Annotated Alice, and The Colossal Book of Mathematics. He lives
in Norman, Oklahoma.
Also Available:
The Colossal Book of Mathematics
November 2005 / hardcover / ISBN 0-393-06114-0 / 308
illustrations / 704 pages
"A gem. . . . An unforgettable account of one of the
great moments in the history of human thought."
---Steven Pinker
PROBING THE LIFE and work of Kurt Godel, Incompleteness indelibly
portrays the tortured genius whose vision rocked the stability of
mathematical reasoning? and brought him to the edge of madness.
"Magnificent. . . . A stimulating exploration of both the
power and the limitations of the human intellect. . . . Goldstein
is an excellent choice for this installment of Norton's Great
Discoveries series: Her philosophical background makes her a sure
guide to the underlying ideas, and she brings a novelistic depth
of character and atmosphere . . . to her sympathetic depiction of
the logician's tortured psyche, as his relentless search for
logical patterns . . . gradually darkened into paranoia."----Publishers
Weekly
"Thoroughly engaging. . . . By the book's end, we understand
well why Einstein would look forward to ethe privilege of
walking home with Godel,' and we can't help but wish that we'd
been able to join them."---Brian Greene
"Penetrating, accessible, and beautifully written." ---Alan
Lightman
--------------------------------------------------------------------------------
REBECCA GOLDSTEIN is a MacArthur Fellow, a professor of
philosophy, and the author of five novels and a collection of
short stories. She lives in Cambridge, Massachusetts.
February 2006 / trade paper / ISBN 0-393-32760-4 / 4
illustrations / 224 pages