This book results from a long-term research effort aimed at tackling complex non-standard packing issues which arise in space engineering. The main research objective is to optimize cargo loading and arrangement, in compliance with a set of stringent rules. Complicated geometrical aspects are also taken into account, in addition to balancing conditions based on attitude control specifications.

Chapter 1 introduces the class of non-standard packing problems studied. Chapter 2 gives a detailed explanation of a general model for the orthogonal packing of tetris-like items in a convex domain. A number of additional conditions are looked at in depth, including the prefixed orientation of subsets of items, the presence of unusable holes, separation planes and structural elements, relative distance bounds as well as static and dynamic balancing requirements. The relative feasibility sub-problem which is a special case that does not have an optimization criterion is discussed in Chapter 3. This setting can be exploited by introducing an ad hoc objective function, aimed at facilitating the finding of integer-feasible solutions. The third chapter also discusses the issue of tightening the general MIP model by introducing valid inequalities. A MIP-based heuristic approach is developed in Chapter 4, where the basic concept of abstract configuration is presented. Chapter 5 is devoted to experimental results relevant to a real-world application framework. Chapter 6 adopts both extensions of the general MIP model and non-linear formulations to tackle two further non-standard packing issues. The final Chapter 7 presents conclusions and provides insights regarding prospective developments (including non-standard scheduling aspects).

Practitioners and researchers interested in advanced optimization model development and solution in the context of logistics, transportation systems, complex structures, manufacturing and electronics will find this book useful. The book can also be used in graduate courses on nonlinear - including global and mixed integer - optimization, as a valuable collection of practically meaningful object packing applications.

The concept of Wiener chaos generalizes to an infinite-dimensional setting the properties of orthogonal polynomials associated with probability distributions on the real line. It plays a crucial role in modern probability theory, with applications ranging from Malliavin calculus to stochastic differential equations and from probabilistic approximations to mathematical finance. This book is concerned with combinatorial structures arising from the study of chaotic random variables related to infinitely divisible random measures. The combinatorial structures involved are those of partitions of finite sets, over which Moebius functions and related inversion formulae are defined. This combinatorial standpoint (which is originally due to Rota and Wallstrom) provides an ideal framework for diagrams, which are graphical devices used to compute moments and cumulants of random variables. Several applications are described, in particular, recent limit theorems for chaotic random variables. An Appendix presents a computer implementation in MATHEMATICA for many of the formulae.

Matroid theory is a vibrant area of research that provides a unified way to understand graph theory, linear algebra and combinatorics via finite geometry. This book provides the first comprehensive introduction to the field which will appeal to undergraduate students and to any mathematician interested in the geometric approach to matroids. Written in a friendly, fun-to-read style and developed from the authors' own undergraduate courses, the book is ideal for students. Beginning with a basic introduction to matroids, the book quickly familiarizes the reader with the breadth of the subject, and specific examples are used to illustrate the theory and to help students see matroids as more than just generalizations of graphs. Over 300 exercises are included, with many hints and solutions so students can test their understanding of the materials covered. The authors have also included several projects and open-ended research problems for independent study.

Computational Complexity of Counting and Sampling provides readers with comprehensive and detailed coverage of the subject of computational complexity. It is primarily geared toward researchers in enumerative combinatorics, discrete mathematics, and theoretical computer science. The book covers the following topics: Counting and sampling problems that are solvable in polynomial running time, including holographic algorithms; #P-complete counting problems; and approximation algorithms for counting and sampling. First, it opens with the basics, such as the theoretical computer science background and dynamic programming algorithms. Later, the book expands its scope to focus on advanced topics, like stochastic approximations of counting discrete mathematical objects and holographic algorithms. After finishing the book, readers will agree that the subject is well covered, as the book starts with the basics and gradually explores the more complex aspects of the topic. Features: Each chapter includes exercises and solutions Ideally written for researchers and scientists Covers all aspects of the topic, beginning with a solid introduction, before shifting to computational complexity's more advanced features, with a focus on counting and sampling

Partitions, q-Series, and Modular Forms contains a collection of research and survey papers that grew out of a Conference on Partitions, q-Series and Modular Forms at the University of Florida, Gainesville in March 2008. It will be of interest to researchers and graduate students that would like to learn of recent developments in the theory of q-series and modular and how it relates to number theory, combinatorics and special functions.

Srinivasa Ramanujan was a mathematician brilliant beyond comparison who inspired many great mathematicians. There is extensive literature available on the work of Ramanujan. But what is missing in the literature is an analysis that would place his mathematics in context and interpret it in terms of modern developments. The 12 lectures by Hardy, delivered in 1936, served this purpose at the time they were given. This book presents Ramanujan's essential mathematical contributions and gives an informal account of some of the major developments that emanated from his work in the 20th and 21st centuries. It contends that his work still has an impact on many different fields of mathematical research. This book examines some of these themes in the landscape of 21st-century mathematics. These essays, based on the lectures given by the authors focus on a subset of Ramanujan's significant papers and show how these papers shaped the course of modern mathematics.

This text offers an introduction to error-correcting linear codes for researchers and graduate students in mathematics, computer science and engineering. The book differs from other standard texts in its emphasis on the classification of codes by means of isometry classes. The relevant algebraic are developed rigorously. Cyclic codes are discussed in great detail. In the last four chapters these isometry classes are enumerated, and representatives are constructed algorithmically.

These lecture notes study the interplay between randomness and geometry of graphs. The first part of the notes reviews several basic geometric concepts, before moving on to examine the manifestation of the underlying geometry in the behavior of random processes, mostly percolation and random walk. The study of the geometry of infinite vertex transitive graphs, and of Cayley graphs in particular, is fairly well developed. One goal of these notes is to point to some random metric spaces modeled by graphs that turn out to be somewhat exotic, that is, they admit a combination of properties not encountered in the vertex transitive world. These include percolation clusters on vertex transitive graphs, critical clusters, local and scaling limits of graphs, long range percolation, CCCP graphs obtained by contracting percolation clusters on graphs, and stationary random graphs, including the uniform infinite planar triangulation (UIPT) and the stochastic hyperbolic planar quadrangulation (SHIQ).

Combinatorial Engineering of Decomposable Systems presents a morphological approach to the combinatorial design/synthesis of decomposable systems. Applications involve the following: design (e.g., information systems; user's interfaces; educational courses); planning (e.g., problem-solving strategies; product life cycles; investment); metaheuristics for combinatorial optimization; information retrieval; etc.

The field of global optimization has been developing at a rapid pace. There is a journal devoted to the topic, as well as many publications and notable books discussing various aspects of global optimization. This book is intended to complement these other publications with a focus on stochastic methods for global optimization. Stochastic methods, such as simulated annealing and genetic algo rithms, are gaining in popularity among practitioners and engineers be they are relatively easy to program on a computer and may be cause applied to a broad class of global optimization problems. However, the theoretical performance of these stochastic methods is not well under stood. In this book, an attempt is made to describe the theoretical prop erties of several stochastic adaptive search methods. Such a theoretical understanding may allow us to better predict algorithm performance and ultimately design new and improved algorithms. This book consolidates a collection of papers on the analysis and de velopment of stochastic adaptive search. The first chapter introduces random search algorithms. Chapters 2-5 describe the theoretical anal ysis of a progression of algorithms. A main result is that the expected number of iterations for pure adaptive search is linear in dimension for a class of Lipschitz global optimization problems. Chapter 6 discusses algorithms, based on the Hit-and-Run sampling method, that have been developed to approximate the ideal performance of pure random search. The final chapter discusses several applications in engineering that use stochastic adaptive search methods."

This monograph provides a detailed review of the state-of-the-art theoretical (analytical and numerical) methodologies for the analysis of dissipative wave dynamics and pattern formation on the surface of a film falling down a planar, inclined substrate. Particular emphasis is given to low-dimensional approximations for such flows through a hierarchy of modeling approaches, including equations of the boundary-layer type, averaged formulations based on weighted residuals approaches, and long-wave expansions.

Whenever possible, the link between theory and experiments is illustrated and, as a further bridge between the two, the development of order-of-magnitude estimates and scaling arguments is used to facilitate the understanding of the underlying basic physics.

The book will be of particular interest to advanced graduate students in applied mathematics, science or engineering undertaking research on interfacial fluid mechanics or studying fluid mechanics as part of their program; researchers working on both applied and fundamental theoretical and experimental aspects of thin film flows; and engineers and technologists dealing with processes involving thin films, either isothermal or heated.

Topics covered include:

Detailed derivations of governing equations and wall and free-surface boundary conditions for free-surface thin film flows in the presence of thermocapillary Marangoni effect; linear stability including Orr-Sommerfeld, absolute/convective instability and Floquet analysis of periodic waves; strongly nonlinear analysis including construction of bifurcation diagrams of periodic and solitary waves; weakly nonlinear prototypes such as Kuramoto-Sivashinsky equation; validity domain of the long-wave expansions; kinematic/dynamic waves, connection with shallow water and river flows/hydraulic jumps; dynamical systems approach, local and global bifurcations, homoclinicity and conditions for periodic, subsidiary and secondary homoclinic orbits; modulation instability of solitary waves to transverse perturbations; transition to two-dimensional solitary waves and interaction of two-dimensional solitary waves; and substrate heating and competition between solitary waves and rivulet formation in free-surface flows over heated substrates.

Tutorials and details of computational methodologies including computer programs:

Solution of the Orr-Sommerfeld eigenvalue problem; computational search via continuation for traveling wave solutions and their bifurcations; computation of systems of nonlinear pde s using finite differences; spectral representation and aliasing.

"

This book on multimedia tools for communicating mathematics arose from presentations at an international workshop organized by the Centro de Matematica e Aplicacoes Fundamentais at the University of Lisbon, in November 2000, with the collaboration of the Sonderforschungsbereich 288 at the University of Technology in Berlin, and of the Centre for Experimental and Constructive Mathematics at Simon Fraser University in Burnaby, Canada. The MTCM2000 meeting aimed at the scientific methods and algorithms at work inside multimedia tools, and it provided an overview of the range of present multimedia projects, of their limitations and the underlying mathematical problems.
This book presents some of the tools and algorithms currently being used to create new ways of making enhanced interactive presentations and multimedia courses. It is an invaluable and up-to-date reference book on multimedia tools presently available for mathematics and related subjects."

Richard Stanley's two-volume basic introduction to enumerative combinatorics has become the standard guide to the topic for students and experts alike. This thoroughly revised second edition of Volume 1 includes ten new sections and more than 300 new exercises, most with solutions, reflecting numerous new developments since the publication of the first edition in 1986. The author brings the coverage up to date and includes a wide variety of additional applications and examples, as well as updated and expanded chapter bibliographies. Many of the less difficult new exercises have no solutions so that they can more easily be assigned to students. The material on P-partitions has been rearranged and generalized; the treatment of permutation statistics has been greatly enlarged; and there are also new sections on q-analogues of permutations, hyperplane arrangements, the cd-index, promotion and evacuation and differential posets.

In many applications of graph theory, graphs are regarded as geometric objects drawn in the plane or in some other surface. The traditional methods of "abstract" graph theory are often incapable of providing satisfactory answers to questions arising in such applications. In the past couple of decades, many powerful new combinatorial and topological techniques have been developed to tackle these problems. Today geometric graph theory is a burgeoning field with many striking results and appealing open questions. This contributed volume contains thirty original survey and research papers on important recent developments in geometric graph theory. The contributions were thoroughly reviewed and written by excellent researchers in this field.

Cryptography has become essential as bank transactions, credit card infor-mation, contracts, and sensitive medical information are sent through inse-cure channels. This book is concerned with the mathematical, especially algebraic, aspects of cryptography. It grew out of many courses presented by the authors over the past twenty years at various universities and covers a wide range of topics in mathematical cryptography. It is primarily geared towards graduate students and advanced undergraduates in mathematics and computer science, but may also be of interest to researchers in the area. Besides the classical methods of symmetric and private key encryption, the book treats the mathematics of cryptographic protocols and several unique topics such as Group-Based Cryptography Groebner Basis Methods in Cryptography Lattice-Based Cryptography

It is a pleasure for me to have the opportunity to write the foreword to this volume, which is dedicated to Professor Georgy Egorychev on the occasion of his seventieth birthday. I have learned a great deal from his creative and important work, as has the whole world of mathematics. From his life's work (so far) in having made d- tinguished contributions to ?elds as diverse as the theory of permanents, Lie groups, combinatorial identities, the Jacobian conjecture, etc., let me comment on just two of the most important of his research areas. The permanent of an nxn matrix A is Per(A)= a a ...a , (1) ? 1,i 2,i n,i 1 2 n extended over the n! permutations{i ,...,i} of{1,2,...,n}. Thus, the permanent 1 n is "like the determinant except for dropping the sign factors from the terms." H- ever by dropping those signs, one loses almost all of the friendly characteristics of determinants, such as the fact that det(AB)= det(A)det(B), the invariance under elementary row and column operations, and so forth. The permanent is a creature of multilinear algebra, rather than of linear algebra, and is much crankier to deal with in virtually all of its aspects, both theoretical and algorithmic.

This innovative textbook introduces a new pattern-based approach to learning proof methods in the mathematical sciences. Readers will discover techniques that will enable them to learn new proofs across different areas of pure mathematics with ease. The patterns in proofs from diverse fields such as algebra, analysis, topology and number theory are explored. Specific topics examined include game theory, combinatorics and Euclidean geometry, enabling a broad familiarity. The author, an experienced lecturer and researcher renowned for his innovative view and intuitive style, illuminates a wide range of techniques and examples from duplicating the cube to triangulating polygons to the infinitude of primes to the fundamental theorem of algebra. Intended as a companion for undergraduate students, this text is an essential addition to every aspiring mathematician's toolkit.

Several geometric problems can be formulated in terms of the arrangement of a collection of curves in a plane, which has made this one of the most widely studied topics in computational geometry. This book, first published in 1991, presents a study of various problems related to arrangements of lines, segments, or curves in the plane. The first problem is a proof of almost tight bounds on the length of (n,s)-Davenport-Schinzel sequences, a technique for obtaining optimal bounds for numerous algorithmic problems. Then the intersection problem is treated. The final problem is improving the efficiency of partitioning algorithms, particularly those used to construct spanning trees with low stabbing numbers, a very versatile tool in solving geometric problems. A number of applications are also discussed. Researchers in computational and combinatorial geometry should find much to interest them in this book.

Graphs on Surfaces: Dualities, Polynomials, and Knots offers an accessible and comprehensive treatment of recent developments on generalized duals of graphs on surfaces, and their applications. The authors illustrate the interdependency between duality, medial graphs and knots; how this interdependency is reflected in algebraic invariants of graphs and knots; and how it can be exploited to solve problems in graph and knot theory. Taking a constructive approach, the authors emphasize how generalized duals and related ideas arise by localizing classical constructions, such as geometric duals and Tait graphs, and then removing artificial restrictions in these constructions to obtain full extensions of them to embedded graphs. The authors demonstrate the benefits of these generalizations to embedded graphs in chapters describing their applications to graph polynomials and knots. Graphs on Surfaces: Dualities, Polynomials, and Knots also provides a self-contained introduction to graphs on surfaces, generalized duals, topological graph polynomials, and knot polynomials that is accessible both to graph theorists and to knot theorists. Directed at those with some familiarity with basic graph theory and knot theory, this book is appropriate for graduate students and researchers in either area. Because the area is advancing so rapidly, the authors give a comprehensive overview of the topic and include a robust bibliography, aiming to provide the reader with the necessary foundations to stay abreast of the field. The reader will come away from the text convinced of advantages of considering these higher genus analogues of constructions of plane and abstract graphs, and with a good understanding of how they arise.

This volume contains nine survey articles based on the invited lectures given at the 23rd British Combinatorial Conference, held at Exeter in July 2011. This biennial conference is a well-established international event, with speakers from all over the world. By its nature, this volume provides an up-to-date overview of current research activity in several areas of combinatorics, including extremal graph theory, the cyclic sieving phenomenon and transversals in Latin squares. Each article is clearly written and assumes little prior knowledge on the part of the reader. The authors are some of the world's foremost researchers in their fields, and here they summarise existing results and give a unique preview of the most recent developments. The book provides a valuable survey of the present state of knowledge in combinatorics. It will be useful to research workers and advanced graduate students, primarily in mathematics but also in computer science and statistics.

The study of combinatorial block designs is a vibrant area of combinatorial mathematics with connections to finite geometries, graph theory, coding theory and statistics. The practice of ordering combinatorial objects can trace its roots to bell ringing which originated in 17th century England, but only emerged as a significant modern research area with the work of F. Gray and N. de Bruijn. These two fascinating areas of mathematics are brought together for the first time in this book. It presents new terminology and concepts which unify existing and recent results from a wide variety of sources. In order to provide a complete introduction and survey, the book begins with background material on combinatorial block designs and combinatorial orderings, including Gray codes -- the most common and well-studied combinatorial ordering concept -- and universal cycles. The central chapter discusses how ordering concepts can be applied to block designs, with definitions from existing (configuration orderings) and new (Gray codes and universal cycles for designs) research. Two chapters are devoted to a survey of results in the field, including illustrative proofs and examples. The book concludes with a discussion of connections to a broad range of applications in computer science, engineering and statistics. This book will appeal to both graduate students and researchers. Each chapter contains worked examples and proofs, complete reference lists, exercises and a list of conjectures and open problems. Practitioners will also find the book appealing for its accessible, self-contained introduction to the mathematics behind the applications.

This book constitutes the thoroughly refereed post-workshop proceedings of the 24th International Workshop on Combinatorial Algorithms, IWOCA 2013, held in Rouen, France, in July 2013. The 33 revised full papers presented together with 10 short papers and 5 invited talks were carefully reviewed and selected from a total of 91 submissions. The papers are organized in topical sections on algorithms on graphs; algorithms on strings; discrete geometry and satisfiability.

This book is a thoroughly revised result, updated to mid-1995, of the NATO Advanced Research Workshop on "Intelligent Learning Environments: the case of geometry", held in Grenoble, France, November 13-16, 1989. The main aim of the workshop was to foster exchanges among researchers who were concerned with the design of intelligent learning environments for geometry. The problem of student modelling was chosen as a central theme of the workshop, insofar as geometry cannot be reduced to procedural knowledge and because the significance of its complexity makes it of interest for intelligent tutoring system (ITS) development. The workshop centred around the following themes: modelling the knowledge domain, modelling student knowledge, design ing "didactic interaction", and learner control. This book contains revised versions of the papers presented at the workshop. All of the chapters that follow have been written by participants at the workshop. Each formed the basis for a scheduled presentation and discussion. Many are suggestive of research directions that will be carried out in the future. There are four main issues running through the papers presented in this book: * knowledge about geometry is not knowledge about the real world, and materialization of geometrical objects implies a reification of geometry which is amplified in the case of its implementation in a computer, since objects can be manipulated directly and relations are the results of actions (Laborde, Schumann). This aspect is well exemplified by research projects focusing on the design of geometric microworlds (Guin, Laborde).

Current language technology is dominated by approaches that either enumerate a large set of rules, or are focused on a large amount of manually labelled data. The creation of both is time-consuming and expensive, which is commonly thought to be the reason why automated natural language understanding has still not made its way into "real-life" applications yet. This book sets an ambitious goal: to shift the development of language processing systems to a much more automated setting than previous works. A new approach is defined: what if computers analysed large samples of language data on their own, identifying structural regularities that perform the necessary abstractions and generalisations in order to better understand language in the process? After defining the framework of Structure Discovery and shedding light on the nature and the graphic structure of natural language data, several procedures are described that do exactly this: let the computer discover structures without supervision in order to boost the performance of language technology applications. Here, multilingual documents are sorted by language, word classes are identified, and semantic ambiguities are discovered and resolved without using a dictionary or other explicit human input. The book concludes with an outlook on the possibilities implied by this paradigm and sets the methods in perspective to human computer interaction. The target audience are academics on all levels (undergraduate and graduate students, lecturers and professors) working in the fields of natural language processing and computational linguistics, as well as natural language engineers who are seeking to improve their systems.

A powerful new image presentation technique has evolved over the last twenty years, and its value demonstrated through its support of many and varied common tasks. Conceptually, Rapid Serial Visual Presentation (RSVP) is basically simple, exemplified in the physical world by the rapid riffling of the pages of a book in order to locate a known image. Advances in computation and graphics processing allow RSVP to be applied flexibly and effectively to a huge variety of common tasks such as window shopping, video fast-forward and rewind, TV channel selection and product browsing. At its heart is a remarkable feature of the human visual processing system known as pre-attentive processing, one which supports the recognition of a known image within as little as one hundred milliseconds and without conscious cognitive effort. Knowledge of pre-attentive processing, together with extensive empirical evidence concerning RSVP, has allowed the authors to provide useful guidance to interaction designers wishing to explore the relevance of RSVP to an application, guidance which is supported by a variety of illustrative examples.