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.

Modern algorithmic techniques for summation, most of which were introduced in the 1990s, are developed here and carefully implemented in the computer algebra system Maple (TM). The algorithms of Fasenmyer, Gosper, Zeilberger, Petkovsek and van Hoeij for hypergeometric summation and recurrence equations, efficient multivariate summation as well as q-analogues of the above algorithms are covered. Similar algorithms concerning differential equations are considered. An equivalent theory of hyperexponential integration due to Almkvist and Zeilberger completes the book. The combination of these results gives orthogonal polynomials and (hypergeometric and q-hypergeometric) special functions a solid algorithmic foundation. Hence, many examples from this very active field are given. The materials covered are suitable for an introductory course on algorithmic summation and will appeal to students and researchers alike.

Spectral Radius of Graphs provides a thorough overview of important results on the spectral radius of adjacency matrix of graphs that have appeared in the literature in the preceding ten years, most of them with proofs, and including some previously unpublished results of the author. The primer begins with a brief classical review, in order to provide the reader with a foundation for the subsequent chapters. Topics covered include spectral decomposition, the Perron-Frobenius theorem, the Rayleigh quotient, the Weyl inequalities, and the Interlacing theorem. From this introduction, the book delves deeper into the properties of the principal eigenvector; a critical subject as many of the results on the spectral radius of graphs rely on the properties of the principal eigenvector for their proofs. A following chapter surveys spectral radius of special graphs, covering multipartite graphs, non-regular graphs, planar graphs, threshold graphs, and others. Finally, the work explores results on the structure of graphs having extreme spectral radius in classes of graphs defined by fixing the value of a particular, integer-valued graph invariant, such as: the diameter, the radius, the domination number, the matching number, the clique number, the independence number, the chromatic number or the sequence of vertex degrees. Throughout, the text includes the valuable addition of proofs to accompany the majority of presented results. This enables the reader to learn tricks of the trade and easily see if some of the techniques apply to a current research problem, without having to spend time on searching for the original articles. The book also contains a handful of open problems on the topic that might provide initiative for the reader's research.

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.

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.

This is the first book devoted to the systematic study of sparse graphs and sparse finite structures. Although the notion of sparsity appears in various contexts and is a typical example of a hard to define notion, the authors devised an unifying classification of general classes of structures. This approach is very robust and it has many remarkable properties. For example the classification is expressible in many different ways involving most extremal combinatorial invariants. This study of sparse structures found applications in such diverse areas as algorithmic graph theory, complexity of algorithms, property testing, descriptive complexity and mathematical logic (homomorphism preservation,fixed parameter tractability and constraint satisfaction problems). It should be stressed that despite of its generality this approach leads to linear (and nearly linear) algorithms. Jaroslav Nesetril is a professor at Charles University, Prague; Patrice Ossona de Mendez is a CNRS researcher et EHESS, Paris. This book is related to the material presented by the first author at ICM 2010.

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.

With the advent of approximation algorithms for NP-hard combinatorial optimization problems, several techniques from exact optimization such as the primal-dual method have proven their staying power and versatility. This book describes a simple and powerful method that is iterative in essence, and similarly useful in a variety of settings for exact and approximate optimization. The authors highlight the commonality and uses of this method to prove a variety of classical polyhedral results on matchings, trees, matroids, and flows. The presentation style is elementary enough to be accessible to anyone with exposure to basic linear algebra and graph theory, making the book suitable for introductory courses in combinatorial optimization at the upper undergraduate and beginning graduate levels. Discussions of advanced applications illustrate their potential for future application in research in approximation algorithms.

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.

Covering Walks in Graphs is aimed at researchers and graduate students in the graph theory community and provides a comprehensive treatment on measures of two well studied graphical properties, namely Hamiltonicity and traversability in graphs. This text looks into the famous K nigsberg Bridge Problem, the Chinese Postman Problem, the Icosian Game and the Traveling Salesman Problem as well as well-known mathematicians who were involved in these problems. The concepts of different spanning walks with examples and present classical results on Hamiltonian numbers and upper Hamiltonian numbers of graphs are described; in some cases, the authors provide proofs of these results to illustrate the beauty and complexity of this area of research. Two new concepts of traceable numbers of graphs and traceable numbers of vertices of a graph which were inspired by and closely related to Hamiltonian numbers are introduced. Results are illustrated on these two concepts and the relationship between traceable concepts and Hamiltonian concepts are examined. Describes several variations of traceable numbers, which provide new frame works for several well-known Hamiltonian concepts and produce interesting new results.

Association schemes are of interest to both mathematicians and statisticians and this book was written with both audiences in mind. For statisticians, it shows how to construct designs for experiments in blocks, how to compare such designs, and how to analyse data from them. The reader is only assumed to know very basic abstract algebra. For pure mathematicians, it tells why association schemes are important and develops the theory to the level of advanced research. This book arose from a course successfully taught by the author and as such the material is thoroughly class-tested. There are a great number of examples and exercises that will increase the book's appeal to both graduate students and their instructors. It is ideal for those coming either from pure mathematics or statistics backgrounds who wish to develop their understanding of association schemes.

This 2003 book provides an analysis of combinatorial games - games not involving chance or hidden information. It contains a fascinating collection of articles by some well-known names in the field, such as Elwyn Berlekamp and John Conway, plus other researchers in mathematics and computer science, together with some top game players. The articles run the gamut from theoretical approaches (infinite games, generalizations of game values, 2-player cellular automata, Alpha-Beta pruning under partial orders) to other games (Amazons, Chomp, Dot-and-Boxes, Go, Chess, Hex). Many of these advances reflect the interplay of the computer science and the mathematics. The book ends with a bibliography by A. Fraenkel and a list of combinatorial game theory problems by R. K. Guy. Like its predecessor, Games of No Chance, this should be on the shelf of all serious combinatorial games enthusiasts.

This 1997 work explores the role of probabilistic methods for solving combinatorial problems. These methods not only provide the means of efficiently using such notions as characteristic and generating functions, the moment method and so on but also let us use the powerful technique of limit theorems. The basic objects under investigation are nonnegative matrices, partitions and mappings of finite sets, with special emphasis on permutations and graphs, and equivalence classes specified on sequences of finite length consisting of elements of partially ordered sets; these specify the probabilistic setting of Sachkov's general combinatorial scheme. The author pays special attention to using probabilistic methods to obtain asymptotic formulae that are difficult to derive using combinatorial methods. This was an important book, describing many ideas not previously available in English; the author has taken the chance to rewrite parts of the text and refresh the references where appropriate.

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).

The huge bandwidth of optical fiber was recognized back in the 1970s during the early development of fiber optic technology. For the last two decades, the capacity of experimental and deployed systems has been increasing at a rate of 100-fold each decade-a rate exceeding the increase of integrated circuit speeds. Today, optical communication in the public communication networks has developed from the status of a curiosity into being the dominant technology. Various great challenges arising from the deployment of the wavelength division multiplexing (WDM) have attracted a lot of efforts from many researchers. Indeed, the optical networking has been a fertile ground for both theoretical researches and experimental studies. This monograph presents the contribution from my past and ongoing research in the optical networking area. The works presented in this book focus more on graph-theoretical and algorithmic aspects of optical networks. Although this book is limited to the works by myself and my coauthors, there are many outstanding achievements made by other individuals, which will be cited in many places in this book. Without the inspiration from their efforts, this book would have never been possible. This monograph is divided into four parts: * Multichannel Optical Networking Architectures, * Broadcast-and-Select Passive Optical Networks, * Wavelength-Switched Optical Networks, * SONET/WDM Optical Networks. The first part consists of the first three chapters. Chapter 1 pro vides a brief survey on the networking architectures of optical trans- XVll xvm MULTICHANNEL OPTICAL NETWORKS port networks, optical access networks and optical premise networks.

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.

Certain constrained combinatorial optimization problems have a natural analogue in the continuous setting of the classical isoperimetric problem. The study of so called combinatorial isoperimetric problems exploits similarities between these two, seemingly disparate, settings. This text focuses on global methods. This means that morphisms, typically arising from symmetry or direct product decomposition, are employed to transform new problems into more restricted and easily solvable settings whilst preserving essential structure. This book is based on Professor Harper's many years' experience in teaching this subject and is ideal for graduate students entering the field. The author has increased the utility of the text for teaching by including worked examples, exercises and material about applications to computer science. Applied systematically, the global point of view can lead to surprising insights and results, and established researchers will find this to be a valuable reference work on an innovative method for problem solving.

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."

Transportation problems belong to the domains mathematical program ming and operations research. Transportation models are widely applied in various fields. Numerous concrete problems (for example, assignment and distribution problems, maximum-flow problem, etc. ) are formulated as trans portation problems. Some efficient methods have been developed for solving transportation problems of various types. This monograph is devoted to transportation problems with minimax cri teria. The classical (linear) transportation problem was posed several decades ago. In this problem, supply and demand points are given, and it is required to minimize the transportation cost. This statement paved the way for numerous extensions and generalizations. In contrast to the original statement of the problem, we consider a min imax rather than a minimum criterion. In particular, a matrix with the minimal largest element is sought in the class of nonnegative matrices with given sums of row and column elements. In this case, the idea behind the minimax criterion can be interpreted as follows. Suppose that the shipment time from a supply point to a demand point is proportional to the amount to be shipped. Then, the minimax is the minimal time required to transport the total amount. It is a common situation that the decision maker does not know the tariff coefficients. In other situations, they do not have any meaning at all, and neither do nonlinear tariff objective functions. In such cases, the minimax interpretation leads to an effective solution.

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 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.

At first sight discrete and fractional programming techniques appear to be two com pletely unrelated fields in operations research. We will show how techniques in both fields can be applied separately and in a combined form to particular models in location analysis. Location analysis deals with the problem of deciding where to locate facilities, con sidering the clients to be served, in such a way that a certain criterion is optimized. The term "facilities" immediately suggests factories, warehouses, schools, etc., while the term "clients" refers to depots, retail units, students, etc. Three basic classes can be identified in location analysis: continuous location, network location and dis crete location. The differences between these fields arise from the structure of the set of possible locations for the facilities. Hence, locating facilities in the plane or in another continuous space corresponds to a continuous location model while finding optimal facility locations on the edges or vertices of a network corresponds to a net work location model. Finally, if the possible set of locations is a finite set of points we have a discrete location model. Each of these fields has been actively studied, arousing intense discussion on the advantages and disadvantages of each of them. The usual requirement that every point in the plane or on the network must be a candidate location point, is one of the mostly used arguments "against" continuous and network location models."

In the spectrum of mathematics, graph theory which studies a mathe matical structure on a set of elements with a binary relation, as a recognized discipline, is a relative newcomer. In recent three decades the exciting and rapidly growing area of the subject abounds with new mathematical devel opments and significant applications to real-world problems. More and more colleges and universities have made it a required course for the senior or the beginning postgraduate students who are majoring in mathematics, computer science, electronics, scientific management and others. This book provides an introduction to graph theory for these students. The richness of theory and the wideness of applications make it impossi ble to include all topics in graph theory in a textbook for one semester. All materials presented in this book, however, I believe, are the most classical, fundamental, interesting and important. The method we deal with the mate rials is to particularly lay stress on digraphs, regarding undirected graphs as their special cases. My own experience from teaching out of the subject more than ten years at University of Science and Technology of China (USTC) shows that this treatment makes hardly the course di: fficult, but much more accords with the essence and the development trend of the subject."

This book shows how the Bayesian Approach (BA) improves well known heuristics by randomizing and optimizing their parameters. That is the Bayesian Heuristic Approach (BHA). The ten in-depth examples are designed to teach Operations Research using Internet. Each example is a simple representation of some impor tant family of real-life problems. The accompanying software can be run by remote Internet users. The supporting web-sites include software for Java, C++, and other lan guages. A theoretical setting is described in which one can discuss a Bayesian adaptive choice of heuristics for discrete and global optimization prob lems. The techniques are evaluated in the spirit of the average rather than the worst case analysis. In this context, "heuristics" are understood to be an expert opinion defining how to solve a family of problems of dis crete or global optimization. The term "Bayesian Heuristic Approach" means that one defines a set of heuristics and fixes some prior distribu tion on the results obtained. By applying BHA one is looking for the heuristic that reduces the average deviation from the global optimum. The theoretical discussions serve as an introduction to examples that are the main part of the book. All the examples are interconnected. Dif ferent examples illustrate different points of the general subject. How ever, one can consider each example separately, too."

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).