Search

This book constitutes the revised selected papers of the 8th International Workshop on Algorithms and Computation, WALCOM 2014, held in Chennai, India, in February 2014. The 29 full papers presented together with 3 invited talks were carefully reviewed and selected from 62 submissions. The papers are organized in topical sections on computational geometry, algorithms and approximations, distributed computing and networks, graph algorithms, complexity and bounds, and graph embeddings and drawings.

This volume contains the proceedings of the Workshop on On-line Algorithms held at the DIMACS Center at Rutgers University in February 1991. Presenting results in the theory of on-line algorithms, the articles discuss a broad range of problems. Most of the papers are based on competitive (worst-case) analysis of on-line algorithms, but some papers consider alternative approaches to on-line analysis. A critical question examined by some of the authors is how to modify competitive analysis to better reconcile the theory and practice of on-line algorithms. Many of the papers examine the ways in which randomization can be used to yield algorithms with improved performance. This book is aimed primarily at specialists in algorithm analysis, but most of the articles present clear expositions of previous work.

The proceedings represent the state of knowledge in the area of algorithmic differentiation (AD). The 31 contributed papers presented at the AD2012 conference cover the application of AD to many areas in science and engineering as well as aspects of AD theory and its implementation in tools. For all papers the referees, selected from the program committee and the greater community, as well as the editors have emphasized accessibility of the presented ideas also to non-AD experts. In the AD tools arena new implementations are introduced covering, for example, Java and graphical modeling environments or join the set of existing tools for Fortran. New developments in AD algorithms target the efficiency of matrix-operation derivatives, detection and exploitation of sparsity, partial separability, the treatment of nonsmooth functions, and other high-level mathematical aspects of the numerical computations to be differentiated. Applications stem from the Earth sciences, nuclear engineering, fluid dynamics, and chemistry, to name just a few. In many cases the applications in a given area of science or engineering share characteristics that require specific approaches to enable AD capabilities or provide an opportunity for efficiency gains in the derivative computation. The description of these characteristics and of the techniques for successfully using AD should make the proceedings a valuable source of information for users of AD tools.

This book constitutes the refereed proceedings of the 15th International Conference on Theory and Applications of Satisfiability Testing, SAT 2012, held in Trento, Italy, in June 2012. The 29 revised full papers, 7 tool papers, and 16 poster papers presented together with 2 invited talks were carefully reviewed and selected from 112 submissions (88 full, 10 tool and 14 poster papers). The papers are organized in topical sections on stochastic local search, theory, quantified Boolean formulae, applications, parallel and portfolio approaches, CDCL SAT solving, MAX-SAT, cores interpolants, complexity analysis, and circuits and encodings.

This book constitutes the refereed proceedings of the 6th International Frontiers of Algorithmics Workshop, FAW 2012, and the 8th International Conference on Algorithmic Aspects in Information and Management, AAIM 2012, jointly held in Beijing, China, in May 2012. The 33 revised full papers presented together with 4 invited talks were carefully reviewed and selected from 81 submissions. The papers are organized in topical sections on algorithms and data structures, algorithmic game theory and incentive analysis, biomedical imaging algorithms, communication networks and optimization, computational learning theory, knowledge discovery, and data mining, experimental algorithmic methodologies, optimization algorithms in economic and operations research, pattern recognition algorithms and trustworthy algorithms and trustworthy software.

This Festschrift volume, published in honor of Kurt Mehlhorn on the occasion of his 60th birthday, contains 28 papers written by his former Ph.D. students and colleagues as well as by his former Ph.D. advisor, Bob Constable. The volume's title is a translation of the title of Kurt Mehlhorn's first book,'Effiziente Algorithmen', published by Teubner-Verlag in 1977. This Festschrift demonstrates how the field of algorithmics has developed and matured in the decades since then. The papers included in this volume are organized in topical sections on models of computation and complexity; sorting and searching; combinatorial optimization with applications; computational geometry and geometric graphs; and algorithm engineering, exactness and robustness.

Meta-heuristics have developed dramatically since their inception in the early 1980s. They have had widespread success in attacking a variety of practical and difficult combinatorial optimization problems. These families of approaches include, but are not limited to greedy random adaptive search procedures, genetic algorithms, problem-space search, neural networks, simulated annealing, tabu search, threshold algorithms, and their hybrids. They incorporate concepts based on biological evolution, intelligent problem solving, mathematical and physical sciences, nervous systems, and statistical mechanics. Since the 1980s, a great deal of effort has been invested in the field of combinatorial optimization theory in which heuristic algorithms have become an important area of research and applications. This volume is drawn from the first conference on Meta-Heuristics and contains 41 papers on the state-of-the-art in heuristic theory and applications. The book treats the following meta-heuristics and applications: Genetic Algorithms, Simulated Annealing, Tabu Search, Networks & Graphs, Scheduling and Control, TSP, and Vehicle Routing Problems. It represents research from the fields of Operations Research, Management Science, Artificial Intelligence and Computer Science.

This book represents the refereed proceedings of the Ninth International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing that was held at the University of Warsaw (Poland) in August 2010. These biennial conferences are major events for Monte Carlo and the premiere event for quasi-Monte Carlo research. The proceedings include articles based on invited lectures as well as carefully selected contributed papers on all theoretical aspects and applications of Monte Carlo and quasi-Monte Carlo methods. The reader will be provided with information on latest developments in these very active areas. The book is an excellent reference for theoreticians and practitioners interested in solving high-dimensional computational problems arising, in particular, in finance and statistics.

Handbook of Whale Optimization Algorithm: Variants, Hybrids, Improvements, and Applications provides the most in-depth look at an emerging meta-heuristic that has been widely used in both science and industry. Whale Optimization Algorithm has been cited more than 5000 times in Google Scholar, thus solving optimization problems using this algorithm requires addressing a number of challenges including multiple objectives, constraints, binary decision variables, large-scale search space, dynamic objective function, and noisy parameters to name a few. This handbook provides readers with in-depth analysis of this algorithm and existing methods in the literature to cope with such challenges. The authors and editors also propose several improvements, variants and hybrids of this algorithm. Several applications are also covered to demonstrate the applicability of methods in this book. Provides in-depth analysis of equations, mathematical models and mechanisms of the Whale Optimization Algorithm Proposes different variants of the Whale Optimization Algorithm to solve binary, multiobjective, noisy, dynamic and combinatorial optimization problems Demonstrates how to design, develop and test different hybrids of Whale Optimization Algorithm Introduces several application areas of the Whale Optimization Algorithm, focusing on sustainability Includes source code from applications and algorithms that is available online

The book is a continuation of Volume I with the same title. It provides different avenues to study algorithms. It also brings new techniques and methodologies to problem solving in computational sciences, engineering, scientific computing and medicine (imaging, radiation therapy) to mention a few. A plethora of algorithms are presented in a sound analytical way. The chapters are written independently of each other, so they can be understood without reading earlier chapters. But some knowledge of analysis, linear algebra, and some computing experience are required. The organization and content of the book cater to senior undergraduate, graduate students, researchers, practitioners, professionals, and academicians in the aforementioned disciplines. It can also be used as a reference book and includes numerous references and open problems.

This book provides different avenues to study algorithms. It also brings new techniques and methodologies to problem solving in computational sciences, engineering, scientific computing and medicine (imaging, radiation therapy) to mention a few. A plethora of algorithms which are universally applicable are presented in a sound, analytical way. The chapters are written independently of each other, so they can be understood without reading earlier chapters. But some knowledge of analysis, linear algebra, and some computing experience is required. The organization and content of this book cater to senior undergraduate, graduate students, researchers, practitioners, professionals, and academicians in the aforementioned disciplines. It can also be used as a reference book and includes numerous references and open problems.

This open access book surveys the progress in addressing selected challenges related to the growth of big data in combination with increasingly complicated hardware. It emerged from a research program established by the German Research Foundation (DFG) as priority program SPP 1736 on Algorithmics for Big Data where researchers from theoretical computer science worked together with application experts in order to tackle problems in domains such as networking, genomics research, and information retrieval. Such domains are unthinkable without substantial hardware and software support, and these systems acquire, process, exchange, and store data at an exponential rate. The chapters of this volume summarize the results of projects realized within the program and survey-related work.This is an open access book.

Numerous problems from diverse disciplines can be converted using mathematical modeling to an equation defined on suitable abstract spaces usually involving the n-dimensional Euclidean space or Hilbert space or Banach Space or even more general spaces. The solution of these equations is sought in closed form. But this is possible only in special cases. That is why researchers and practitioners use iterative algorithms, which seem to be the only alternative. Due to the explosion of technology, faster and faster computers become available. This development simply means that new optimized algorithms should be developed to take advantage of these improvements. That is exactly where we come in with our book containing such algorithms with applications in problems from numerical analysis and economics but also from other areas such as biology, chemistry, physics, parallel computing, and engineering. The book is an outgrowth of scientific research conducted over two years. This book can be used by senior undergraduate students, graduate students, researchers, and practitioners in the aforementioned areas in the classroom or as reference material. Readers should know the fundamentals of numerical-functional analysis, economic theory, and Newtonian physics. Some knowledge of computers and contemporary programming shall be very helpful to readers.

This book discusses an important area of numerical optimization, called interior-point method. This topic has been popular since the 1980s when people gradually realized that all simplex algorithms were not convergent in polynomial time and many interior-point algorithms could be proved to converge in polynomial time. However, for a long time, there was a noticeable gap between theoretical polynomial bounds of the interior-point algorithms and efficiency of these algorithms. Strategies that were important to the computational efficiency became barriers in the proof of good polynomial bounds. The more the strategies were used in algorithms, the worse the polynomial bounds became. To further exacerbate the problem, Mehrotra's predictor-corrector (MPC) algorithm (the most popular and efficient interior-point algorithm until recently) uses all good strategies and fails to prove the convergence. Therefore, MPC does not have polynomiality, a critical issue with the simplex method.This book discusses recent developments that resolves the dilemma. It has three major parts. The first, including Chapters 1, 2, 3, and 4, presents some of the most important algorithms during the development of the interior-point method around the 1990s, most of them are widely known. The main purpose of this part is to explain the dilemma described above by analyzing these algorithms'polynomial bounds and summarizing the computational experience associated with them. The second part, including Chapters 5, 6, 7, and 8, describes how to solve the dilemma step-by-step using arc-search techniques. At the end of this part, a very efficient algorithm with the lowest polynomial bound is presented. The last part, including Chapters 9, 10, 11, and 12, extends arc-search techniques to some more general problems, such as convex quadratic programming, linear complementarity problem, and semi-definite programming.

The book presents eight well-known and often used algorithms besides nine newly developed algorithms by the first author and his students in a practical implementation framework. Matlab codes and some benchmark structural optimization problems are provided. The aim is to provide an efficient context for experienced researchers or readers not familiar with theory, applications and computational developments of the considered metaheuristics. The information will also be of interest to readers interested in application of metaheuristics for hard optimization, comparing conceptually different metaheuristics and designing new metaheuristics.

This work reviews the most important results regarding the use of the α-point in Scheduling Theory. It provides a number of different LP-relaxations for scheduling problems and seeks to explain their polyhedral consequences. It also explains the concept of the α-point and how the conversion algorithm works, pointing out the relations to the sum of the weighted completion times. Lastly, the book explores the latest techniques used for many scheduling problems with different constraints, such as release dates, precedences, and parallel machines. This reference book is intended for advanced undergraduate and postgraduate students who are interested in scheduling theory. It is also inspiring for researchers wanting to learn about sophisticated techniques and open problems of the field.

This book covers all the relevant dictionary learning algorithms, presenting them in full detail and showing their distinct characteristics while also revealing the similarities. It gives implementation tricks that are often ignored but that are crucial for a successful program. Besides MOD, K-SVD, and other standard algorithms, it provides the significant dictionary learning problem variations, such as regularization, incoherence enforcing, finding an economical size, or learning adapted to specific problems like classification. Several types of dictionary structures are treated, including shift invariant; orthogonal blocks or factored dictionaries; and separable dictionaries for multidimensional signals. Nonlinear extensions such as kernel dictionary learning can also be found in the book. The discussion of all these dictionary types and algorithms is enriched with a thorough numerical comparison on several classic problems, thus showing the strengths and weaknesses of each algorithm. A few selected applications, related to classification, denoising and compression, complete the view on the capabilities of the presented dictionary learning algorithms. The book is accompanied by code for all algorithms and for reproducing most tables and figures.Presents all relevant dictionary learning algorithms - for the standard problem and its main variations - in detail and ready for implementation;Covers all dictionary structures that are meaningful in applications;Examines the numerical properties of the algorithms and shows how to choose the appropriate dictionary learning algorithm.

This book provides the reader with a basic understanding of the formal concepts of the cluster, clustering, partition, cluster analysis etc. The book explains feature-based, graph-based and spectral clustering methods and discusses their formal similarities and differences. Understanding the related formal concepts is particularly vital in the epoch of Big Data; due to the volume and characteristics of the data, it is no longer feasible to predominantly rely on merely viewing the data when facing a clustering problem. Usually clustering involves choosing similar objects and grouping them together. To facilitate the choice of similarity measures for complex and big data, various measures of object similarity, based on quantitative (like numerical measurement results) and qualitative features (like text), as well as combinations of the two, are described, as well as graph-based similarity measures for (hyper) linked objects and measures for multilayered graphs. Numerous variants demonstrating how such similarity measures can be exploited when defining clustering cost functions are also presented. In addition, the book provides an overview of approaches to handling large collections of objects in a reasonable time. In particular, it addresses grid-based methods, sampling methods, parallelization via Map-Reduce, usage of tree-structures, random projections and various heuristic approaches, especially those used for community detection.

Machine learning, one of the top emerging sciences, has an extremely broad range of applications. However, many books on the subject provide only a theoretical approach, making it difficult for a newcomer to grasp the subject material. This book provides a more practical approach by explaining the concepts of machine learning algorithms and describing the areas of application for each algorithm, using simple practical examples to demonstrate each algorithm and showing how different issues related to these algorithms are applied.

The 14 contributed chapters in this book survey the most recent developments in high-performance algorithms for NGS data, offering fundamental insights and technical information specifically on indexing, compression and storage; error correction; alignment; and assembly. The book will be of value to researchers, practitioners and students engaged with bioinformatics, computer science, mathematics, statistics and life sciences.

This book provides state-of-the-art and interdisciplinary topics on solving matrix eigenvalue problems, particularly by using recent petascale and upcoming post-petascale supercomputers. It gathers selected topics presented at the International Workshops on Eigenvalue Problems: Algorithms; Software and Applications, in Petascale Computing (EPASA2014 and EPASA2015), which brought together leading researchers working on the numerical solution of matrix eigenvalue problems to discuss and exchange ideas – and in so doing helped to create a community for researchers in eigenvalue problems. The topics presented in the book, including novel numerical algorithms, high-performance implementation techniques, software developments and sample applications, will contribute to various fields that involve solving large-scale eigenvalue problems.

This interdisciplinary reference and guide provides an introduction to modeling methodologies and models which form the starting point for deriving efficient and effective solution techniques, and presents a series of case studies that demonstrate how heuristic and analytical approaches may be used to solve large and complex problems. Topics and features: introduces the key modeling methods and tools, including heuristic and mathematical programming-based models, and queueing theory and simulation techniques; demonstrates the use of heuristic methods to not only solve complex decision-making problems, but also to derive a simpler solution technique; presents case studies on a broad range of applications that make use of techniques from genetic algorithms and fuzzy logic, tabu search, and queueing theory; reviews examples incorporating system dynamics modeling, cellular automata and agent-based simulations, and the use of big data; supplies expanded descriptions and examples in the appendices.

The purpose of a DIMACS Challenge is to encourage and coordinate research in the experimental analysis of algorithms. The First DIMACS Challenge encouraged experimental work in the area of network flow and matchings. The Second DIMACS Challenge, on which this volume is based, took place in conjunction with the DIMACS Special Year on Combinatorial Optimization. Addressed here are three difficult combinatorial optimization problems: finding cliques in a graph, coloring the vertices of a graph, and solving instances of the satisfiability problem. These problems were chosen both for their practical interest and because of their theoretical intractability.

This volume gathers contributions reflecting topics presented during an INDAM workshop held in Rome in May 2016. The event brought together many prominent researchers in both Mathematical Analysis and Numerical Computing, the goal being to promote interdisciplinary collaborations. Accordingly, the following thematic areas were developed:1. Lagrangian discretizations and wavefront tracking for synchronization models;2. Astrophysics computations and post-Newtonian approximations;3. Hyperbolic balance laws and corrugated isometric embeddings;4. “Caseology” techniques for kinetic equations;5. Tentative computations of compressible non-standard solutions;6. Entropy dissipation, convergence rates and inverse design issues. Most of the articles are presented in a self-contained manner; some highlight new achievements, while others offer snapshots of the “state of the art” in certain fields. The book offers a unique resource, both for young researchers looking to quickly enter a given area of application, and for more experienced ones seeking comprehensive overviews and extensive bibliographic references.

Cryptographic Boolean Functions and Applications, Second Edition is designed to be a comprehensive reference for the use of Boolean functions in modern cryptography. While the vast majority of research on cryptographic Boolean functions has been achieved since the 1970s, when cryptography began to be widely used in everyday transactions, in particular banking, relevant material is scattered over hundreds of journal articles, conference proceedings, books, reports and notes, some of them only available online. This book follows the previous edition in sifting through this compendium and gathering the most significant information in one concise reference book. The work therefore encompasses over 600 citations, covering every aspect of the applications of cryptographic Boolean functions. Since 2008, the subject has seen a very large number of new results, and in response, the authors have prepared a new chapter on special functions. The new edition brings 100 completely new references and an expansion of 50 new pages, along with heavy revision throughout the text. - Presents a foundational approach, beginning with the basics of the necessary theory, then progressing to more complex content - Includes major concepts that are presented with complete proofs, with an emphasis on how they can be applied - Includes an extensive list of references, including 100 new to this edition that were chosen to highlight relevant topics - Contains a section on special functions and all-new numerical examples

This volume contains contributions from the 11th International Conference on Management Science (CMS 2014), held at Lisbon, Portugal, on May 29-31, 2014. Its contents reflect the wide scope of Management Science, covering different theoretical aspects for a quite diverse set of applications. Computational Management Science provides a unique perspective in relevant decision-making processes by focusing on all its computational aspects. These include computational economics, finance and statistics; energy; scheduling; supply chains; design, analysis and applications of optimization algorithms; deterministic, dynamic, stochastic, robust and combinatorial optimization models; solution algorithms, learning and forecasting such as neural networks and genetic algorithms; models and tools of knowledge acquisition, such as data mining; and all other topics in management science with the emphasis on computational paradigms.

Describing a new optimization algorithm, the “Teaching-Learning-Based Optimization (TLBO),” in a clear and lucid style, this book maximizes reader insights into how the TLBO algorithm can be used to solve continuous and discrete optimization problems involving single or multiple objectives. As the algorithm operates on the principle of teaching and learning, where teachers influence the quality of learners'results, the elitist version of TLBO algorithm (ETLBO) is described along with applications of the TLBO algorithm in the fields of electrical engineering, mechanical design, thermal engineering, manufacturing engineering, civil engineering, structural engineering, computer engineering, electronics engineering, physics and biotechnology. The book offers a valuable resource for scientists, engineers and practitioners involved in the development and usage of advanced optimization algorithms.

This book is a source of valuable and useful information on the topics of dynamics of number systems and scientific computation with arbitrary precision. It is addressed to scholars, scientists and engineers, and graduate students. The treatment is elementary and self-contained with relevance both for theory and applications. The basic prerequisite of the book is linear algebra and matrix calculus.

Systems with mechanical degrees of freedom containing unstable objects are analysed in this monograph and algorithms for their control are developed, discussed, and numerically tested. This is achieved by identifying unstable modes of motion and using all available resources to suppress them. By using this approach the region of states from which a stable regime can be reached is maximised. The systems discussed in this book are models for pendula and vehicles and find applications in mechatronics, robotics as well as in mechanical and automotive engineering.

This book brings together research on numerical methods adapted for Graphics Processing Units (GPUs). It explains recent efforts to adapt classic numerical methods, including solution of linear equations and FFT, for massively parallel GPU architectures. This volume consolidates recent research and adaptations, covering widely used methods that are at the core of many scientific and engineering computations. Each chapter is written by authors working on a specific group of methods; these leading experts provide mathematical background, parallel algorithms and implementation details leading to reusable, adaptable and scalable code fragments. This book also serves as a GPU implementation manual for many numerical algorithms, sharing tips on GPUs that can increase application efficiency. The valuable insights into parallelization strategies for GPUs are supplemented by ready-to-use code fragments. Numerical Computations with GPUs targets professionals and researchers working in high performance computing and GPU programming. Advanced-level students focused on computer science and mathematics will also find this book useful as secondary text book or reference.

Iterative Optimization in Inverse Problems brings together a number of important iterative algorithms for medical imaging, optimization, and statistical estimation. It incorporates recent work that has not appeared in other books and draws on the author's considerable research in the field, including his recently developed class of SUMMA algorithms

Mathematical algorithms are a fundamental component of Computer Aided Design and Manufacturing (CAD/CAM) systems. This book provides a bridge between algebraic geometry and geometric modelling algorithms, formulated within a computer science framework.Apart from the algebraic geometry topics covered, the entire book is based on the unifying concept of using algebraic techniques – properly specialized to solve geometric problems – to seriously improve accuracy, robustness and efficiency of CAD-systems. It provides new approaches as well as industrial applications to deform surfaces when animating virtual characters, to automatically compare images of handwritten signatures and to improve control of NC machines.This book further introduces a noteworthy representation based on 2D contours, which is essential to model the metal sheet in industrial processes. It additionally reviews applications of numerical algebraic geometry to differential equations systems with multiple solutions and bifurcations.Future Vision and Trends on Shapes, Geometry and Algebra is aimed specialists in the area of mathematics and computer science on the one hand and on the other hand at those who want to become familiar with the practical application of algebraic geometry and geometric modelling such as students, researchers and doctorates.

This book is concerned with recent advances in fitness landscapes. The concept of fitness landscapes originates from theoretical biology and refers to a framework for analysing and visualizing the relationships between genotypes, phenotypes and fitness. These relationships lay at the centre of attempts to mathematically describe evolutionary processes and evolutionary dynamics.The book addresses recent advances in the understanding of fitness landscapes in evolutionary biology and evolutionary computation. In the volume, experts in the field of fitness landscapes present these findings in an integrated way to make it accessible to a number of audiences: senior undergraduate and graduate students in computer science, theoretical biology, physics, applied mathematics and engineering, but also researcher looking for a reference or/and entry point into using fitness landscapes for analysing algorithms. Also practitioners wanting to employ fitness landscape techniques for evaluating bio- and nature-inspired computing algorithms can find valuable material in the book. For teaching proposes, the book could also be used as a reference handbook.

Markov chains are a fundamental class of stochastic processes. They are widely used to solve problems in a large number of domains such as operational research, computer science, communication networks and manufacturing systems. The success of Markov chains is mainly due to their simplicity of use, the large number of available theoretical results and the quality of algorithms developed for the numerical evaluation of many metrics of interest. The author presents the theory of both discrete-time and continuous-time homogeneous Markov chains. He carefully examines the explosion phenomenon, the Kolmogorov equations, the convergence to equilibrium and the passage time distributions to a state and to a subset of states. These results are applied to birth-and-death processes. He then proposes a detailed study of the uniformization technique by means of Banach algebra. This technique is used for the transient analysis of several queuing systems. Contents 1. Discrete-Time Markov Chains 2. Continuous-Time Markov Chains 3. Birth-and-Death Processes 4. Uniformization 5. Queues About the Authors Bruno Sericola is a Senior Research Scientist at Inria Rennes – Bretagne Atlantique in France. His main research activity is in performance evaluation of computer and communication systems, dependability analysis of fault-tolerant systems and stochastic models.

Despite decades of work in evolutionary algorithms, there remains a lot of uncertainty as to when it is beneficial or detrimental to use recombination or mutation. This book provides a characterization of the roles that recombination and mutation play in evolutionary algorithms. It integrates prior theoretical work and introduces new theoretical techniques for studying evolutionary algorithms. An aggregation algorithm for Markov chains is introduced which is useful for studying not only evolutionary algorithms specifically, but also complex systems in general. Practical consequences of the theory are explored and a novel method for comparing search and optimization algorithms is introduced. A focus on discrete rather than real-valued representations allows the book to bridge multiple communities, including evolutionary biologists and population geneticists.

Combinatorial optimization is the process of finding the best, or optimal, so­ lution for problems with a discrete set of feasible solutions. Applications arise in numerous settings involving operations management and logistics, such as routing, scheduling, packing, inventory and production management, lo­ cation, logic, and assignment of resources. The economic impact of combi­ natorial optimization is profound, affecting sectors as diverse as transporta­ tion (airlines, trucking, rail, and shipping), forestry, manufacturing, logistics, aerospace, energy (electrical power, petroleum, and natural gas), telecommu­ nications, biotechnology, financial services, and agriculture. While much progress has been made in finding exact (provably optimal) so­ lutions to some combinatorial optimization problems, using techniques such as dynamic programming, cutting planes, and branch and cut methods, many hard combinatorial problems are still not solved exactly and require good heuristic methods. Moreover, reaching'optimal solutions'is in many cases meaningless, as in practice we are often dealing with models that are rough simplifications of reality. The aim of heuristic methods for combinatorial op­ timization is to quickly produce good-quality solutions, without necessarily providing any guarantee of solution quality. Metaheuristics are high level procedures that coordinate simple heuristics, such as local search, to find solu­ tions that are of better quality than those found by the simple heuristics alone: Modem metaheuristics include simulated annealing, genetic algorithms, tabu search, GRASP, scatter search, ant colony optimization, variable neighborhood search, and their hybrids.

This monograph deals with a general class of solution approaches in deterministic global optimization, namely the geometric branch-and-bound methods which are popular algorithms, for instance, in Lipschitzian optimization, d.c. programming, and interval analysis.It also introduces a new concept for the rate of convergence and analyzes several bounding operations reported in the literature, from the theoretical as well as from the empirical point of view. Furthermore, extensions of the prototype algorithm for multicriteria global optimization problems as well as mixed combinatorial optimization problems are considered. Numerical examples based on facility location problems support the theory. Applications of geometric branch-and-bound methods, namely the circle detection problem in image processing, the integrated scheduling and location makespan problem, and the median line location problem in the three-dimensional space are also presented.The book is intended for both researchers and students in the areas of mathematics, operations research, engineering, and computer science.

This monograph reports a thought experiment with a mathematical structure intended to illustrate the workings of a mind. It presents a mathematical theory of human thought based on pattern theory with a graph-based approach to thinking. The method illustrated and produced by extensive computer simulations is related to neural networks. Based mainly on introspection, it is speculative rather than empirical such that it differs radically in attitude from the conventional wisdom of current cognitive science.

This application-oriented work concerns the design of efficient, robust and reliable algorithms for the numerical simulation of multiscale phenomena. To this end, various modern techniques from scattered data modelling, such as splines over triangulations and radial basis functions, are combined with customized adaptive strategies, which are developed individually in this work. The resulting multiresolution methods include thinning algorithms, multi­ levelapproximation schemes, and meshfree discretizations for transport equa­ tions. The utility of the proposed computational methods is supported by their wide range of applications, such as image compression, hierarchical sur­ face visualization, and multiscale flow simulation. Special emphasis is placed on comparisons between the various numerical algorithms developed in this work and comparable state-of-the-art methods. To this end, extensive numerical examples, mainly arising from real-world applications, are provided. This research monograph is arranged in six chapters: 1. Introduction; 2. Algorithms and Data Structures; 3. Radial Basis Functions; 4. Thinning Algorithms; 5. Multilevel Approximation Schemes; 6. Meshfree Methods for Transport Equations. Chapter 1 provides a preliminary discussion on basic concepts, tools and principles of multiresolution methods, scattered data modelling, multilevel methods and adaptive irregular sampling. Relevant algorithms and data structures, such as triangulation methods, heaps, and quadtrees, are then introduced in Chapter 2.

Decades of innovations in combinatorial problem solving have produced better and more complex algorithms. These new methods are better since they can solve larger problems and address new application domains. They are also more complex which means that they are hard to reproduce and often harder to fine-tune to the peculiarities of a given problem. This last point has created a paradox where efficient tools are out of reach of practitioners.Autonomous search (AS) represents a new research field defined to precisely address the above challenge. Its major strength and originality consist in the fact that problem solvers can now perform self-improvement operations based on analysis of the performances of the solving process -- including short-term reactive reconfiguration and long-term improvement through self-analysis of the performance, offline tuning and online control, and adaptive control and supervised control. Autonomous search'crosses the chasm'and provides engineers and practitioners with systems that are able to autonomously self-tune their performance while effectively solving problems. This is the first book dedicated to this topic, and it can be used as a reference for researchers, engineers, and postgraduates in the areas of constraint programming, machine learning, evolutionary computing, and feedback control theory. After the editors'introduction to autonomous search, the chapters are focused on tuning algorithm parameters, autonomous complete (tree-based) constraint solvers, autonomous control in metaheuristics and heuristics, and future autonomous solving paradigms.Autonomous search (AS) represents a new research field defined to precisely address the above challenge. Its major strength and originality consist in the fact that problem solvers can now perform self-improvement operations based on analysis of the performances of the solving process -- including short-term reactive reconfiguration and long-term improvement through self-analysis of the performance, offline tuning and online control, and adaptive control and supervised control. Autonomous search'crosses the chasm'and provides engineers and practitioners with systems that are able to autonomously self-tune their performance while effectively solving problems. This is the first book dedicated to this topic, and it can be used as a reference for researchers, engineers, and postgraduates in the areas of constraint programming, machine learning, evolutionary computing, and feedback control theory. After the editors'introduction to autonomous search, the chapters are focused on tuning algorithm parameters, autonomous complete (tree-based) constraint solvers, autonomous control in metaheuristics and heuristics, and future autonomous solving paradigms.This is the first book dedicated to this topic, and it can be used as a reference for researchers, engineers, and postgraduates in the areas of constraint programming, machine learning, evolutionary computing, and feedback control theory. After the editors'introduction to autonomous search, the chapters are focused on tuning algorithm parameters, autonomous complete (tree-based) constraint solvers, autonomous control in metaheuristics and heuristics, and future autonomous solving paradigms.This is the first book dedicated to this topic, and it can be used as a reference for researchers, engineers, and postgraduates in the areas of constraint programming, machine learning, evolutionary computing, and feedback control theory. After the editors'introduction to autonomous search, the chapters are focused on tuning algorithm parameters, autonomous complete (tree-based) constraint solvers, autonomous control in metaheuristics and heuristics, and future autonomous solving paradigms.

Das Buch ist eine praxisnahe Einführung in die Numerische Mathematik zu grundlegenden Aufgabengebieten wie lineare und nichtlineare Gleichungen und Systeme, Eigenwerte von Matrizen, Approximation, Interpolation, Splines, Quadratur, Kubatur und es behandelt Anfangswertprobleme bei gewöhnlichen Differentialgleichungen. Die Autoren beschreiben die mathematischen und numerischen Prinzipien wichtiger Verfahren und stellen leistungsfähige Algorithmen für deren Durchführung dar. Zahlreiche Beispiele und erläuternde Skizzen erleichtern das Verständnis. Für jeden Problemkreis werden Entscheidungshilfen für die Auswahl der geeigneten Methode angegeben. Zu allen Verfahren wurden Programme in C entwickelt, die vom Server des Springer-Verlags abrufbar sind.

Agent based evolutionary search is an emerging paradigm in computational int- ligence offering the potential to conceptualize and solve a variety of complex problems such as currency trading, production planning, disaster response m- agement, business process management etc. There has been a significant growth in the number of publications related to the development and applications of agent based systems in recent years which has prompted special issues of journals and dedicated sessions in premier conferences. The notion of an agent with its ability to sense, learn and act autonomously - lows the development of a plethora of efficient algorithms to deal with complex problems. This notion of an agent differs significantly from a restrictive definition of a solution in an evolutionary algorithm and opens up the possibility to model and capture emergent behavior of complex systems through a natural age- oriented decomposition of the problem space. While this flexibility of represen- tion offered by agent based systems is widely acknowledged, they need to be - signed for specific purposes capturing the right level of details and description. This edited volume is aimed to provide the readers with a brief background of agent based evolutionary search, recent developments and studies dealing with various levels of information abstraction and applications of agent based evo- tionary systems. There are 12 peer reviewed chapters in this book authored by d- tinguished researchers who have shared their experience and findings spanning across a wide range of applications.

The first book to offer a comprehensive view of the LLL algorithm, this text surveys computational aspects of Euclidean lattices and their main applications. It includes many detailed motivations, explanations and examples.

'Medical Image Reconstruction: A Conceptual Tutorial'introduces the classical and modern image reconstruction technologies, such as two-dimensional (2D) parallel-beam and fan-beam imaging, three-dimensional (3D) parallel ray, parallel plane, and cone-beam imaging. This book presents both analytical and iterative methods of these technologies and their applications in X-ray CT (computed tomography), SPECT (single photon emission computed tomography), PET (positron emission tomography), and MRI (magnetic resonance imaging). Contemporary research results in exact region-of-interest (ROI) reconstruction with truncated projections, Katsevich's cone-beam filtered backprojection algorithm, and reconstruction with highly undersampled data with l0-minimization are also included. This book is written for engineers and researchers in the field of biomedical engineering specializing in medical imaging and image processing with image reconstruction. Gengsheng Lawrence Zeng is an expert in the development of medical image reconstruction algorithms and is a professor at the Department of Radiology, University of Utah, Salt Lake City, Utah, USA.

This monograph, derived from an advanced computer science course at Stanford University, builds on the fundamentals of combinatorial analysis and complex variable theory to present many of the major paradigms used in the precise analysis of algorithms, emphasizing the more difficult notions. The authors cover recurrence relations, operator methods, and asymptotic analysis in a format that is terse enough for easy reference yet detailed enough for those with little background. Approximately half the book is devoted to original problems and solutions from examinations given at Stanford.

Algorithms and Programming is primarily intended for a first-year undergraduate course in programming. It is structured in a problem-solution format that requires the student to think through the programming process, thus developing an understanding of the underlying theory. The book is easily readable by a student taking a basic introductory course in computer science as well as useful for a graduate-level course in the analysis of algorithms and/or compiler construction. Each chapter is more or less independent, containing classical and well-known problems supplemented by clear and in-depth explanations. The material covered includes such topics as combinatorics, sorting, searching, queues, grammar and parsing, selected well-known algorithms and much more. Students and teachers will find this both an excellent text for learning programming and a source of problems for a variety of courses.

This self-contained introduction to the distributed control of robotic networks offers a distinctive blend of computer science and control theory. The book presents a broad set of tools for understanding coordination algorithms, determining their correctness, and assessing their complexity; and it analyzes various cooperative strategies for tasks such as consensus, rendezvous, connectivity maintenance, deployment, and boundary estimation. The unifying theme is a formal model for robotic networks that explicitly incorporates their communication, sensing, control, and processing capabilities--a model that in turn leads to a common formal language to describe and analyze coordination algorithms. Written for first- and second-year graduate students in control and robotics, the book will also be useful to researchers in control theory, robotics, distributed algorithms, and automata theory. The book provides explanations of the basic concepts and main results, as well as numerous examples and exercises. Self-contained exposition of graph-theoretic concepts, distributed algorithms, and complexity measures for processor networks with fixed interconnection topology and for robotic networks with position-dependent interconnection topology Detailed treatment of averaging and consensus algorithms interpreted as linear iterations on synchronous networks Introduction of geometric notions such as partitions, proximity graphs, and multicenter functions Detailed treatment of motion coordination algorithms for deployment, rendezvous, connectivity maintenance, and boundary estimation

Algorithmic composition – composing by means of formalizable methods – has a century old tradition not only in occidental music history. This is the first book to provide a detailed overview of prominent procedures of algorithmic composition in a pragmatic way rather than by treating formalizable aspects in single works. In addition to an historic overview, each chapter presents a specific class of algorithm in a compositional context by providing a general introduction to its development and theoretical basis and describes different musical applications. Each chapter outlines the strengths, weaknesses and possible aesthetical implications resulting from the application of the treated approaches. Topics covered are: markov models, generative grammars, transition networks, chaos and self-similarity, genetic algorithms, cellular automata, neural networks and artificial intelligence are covered. The comprehensive bibliography makes this work ideal for the musician and the researcher alike.

Text classification is becoming a crucial task to analysts in different areas. In the last few decades, the production of textual documents in digital form has increased exponentially. Their applications range from web pages to scientific documents, including emails, news and books. Despite the widespread use of digital texts, handling them is inherently difficult - the large amount of data necessary to represent them and the subjectivity of classification complicate matters. This book gives a concise view on how to use kernel approaches for inductive inference in large scale text classification; it presents a series of new techniques to enhance, scale and distribute text classification tasks. It is not intended to be a comprehensive survey of the state-of-the-art of the whole field of text classification. Its purpose is less ambitious and more practical: to explain and illustrate some of the important methods used in this field, in particular kernel approaches and techniques.