Search

In response to a growing interest in Total Least Squares (TLS) and Errors-In-Variables (EIV) modeling by researchers and practitioners, well-known experts from several disciplines were invited to prepare an overview paper and present it at the third international workshop on TLS and EIV modeling held in Leuven, Belgium, August 27-29, 2001. These invited papers, representing two-thirds of the book, together with a selection of other presented contributions yield a complete overview of the main scientific achievements since 1996 in TLS and Errors-In-Variables modeling. In this way, the book nicely completes two earlier books on TLS (SIAM 1991 and 1997). Not only computational issues, but also statistical, numerical, algebraic properties are described, as well as many new generalizations and applications. Being aware of the growing interest in these techniques, it is a strong belief that this book will aid and stimulate users to apply the new techniques and models correctly to their own practical problems.

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 features selected papers from the 5th International Conference on Mathematics and Computing (ICMC 2019), organized by the School of Computer Engineering, Kalinga Institute of Industrial Technology Bhubaneswar, India, on February 6 – 9, 2019. Covering recent advances in the field of mathematics, statistics and scientific computing, the book presents innovative work by leading academics, researchers and experts from industry.

In recent years global optimization has found applications in many interesting areas of science and technology including molecular biology, chemical equilibrium problems, medical imaging and networks. The collection of papers in this book indicates the diverse applicability of global optimization. Furthermore, various algorithmic, theoretical developments and computational studies are presented. Audience: All researchers and students working in mathematical programming.

The two-volume set LNCS 8269 and 8270 constitutes the refereed proceedings of the 19th International Conference on the Theory and Application of Cryptology and Information, Asiacrypt 2013, held in Bengaluru, India, in December 2013. The 54 revised full papers presented were carefully selected from 269 submissions. They are organized in topical sections named: zero-knowledge, algebraic cryptography, theoretical cryptography, protocols, symmetric key cryptanalysis, symmetric key cryptology: schemes and analysis, side-channel cryptanalysis, message authentication codes, signatures, cryptography based upon physical assumptions, multi-party computation, cryptographic primitives, analysis, cryptanalysis and passwords, leakage-resilient cryptography, two-party computation, hash functions.

The two-volume set LNCS 8269 and 8270 constitutes the refereed proceedings of the 19th International Conference on the Theory and Application of Cryptology and Information, Asiacrypt 2013, held in Bengaluru, India, in December 2013. The 54 revised full papers presented were carefully selected from 269 submissions. They are organized in topical sections named: zero-knowledge, algebraic cryptography, theoretical cryptography, protocols, symmetric key cryptanalysis, symmetric key cryptology: schemes and analysis, side-channel cryptanalysis, message authentication codes, signatures, cryptography based upon physical assumptions, multi-party computation, cryptographic primitives, analysis, cryptanalysis and passwords, leakage-resilient cryptography, two-party computation, hash functions.

This book constitutes the refereed proceedings of the 18th International Conference on the Theory and Application of Cryptology and Information Security, Asiacrypt 2012, held in Beijing, China, in December 2012. The 43 full papers presented were carefully reviewed and selected from 241 submissions. They are organized in topical sections named: public-key cryptography, foundation, symmetric cipher, security proof, lattice-based cryptography and number theory, hash function, cryptographic protocol, and implementation issues.

This monograph is a slightly revised version of my PhD thesis [86], com­ pleted in the Department of Computer Science at the University of Edin­ burgh in June 1988, with an additional chapter summarising more recent developments. Some of the material has appeared in the form of papers [50,88]. The underlying theme of the monograph is the study of two classical problems: counting the elements of a finite set of combinatorial structures, and generating them uniformly at random. In their exact form, these prob­ lems appear to be intractable for many important structures, so interest has focused on finding efficient randomised algorithms that solve them ap­ proxim~ly, with a small probability of error. For most natural structures the two problems are intimately connected at this level of approximation, so it is natural to study them together. At the heart of the monograph is a single algorithmic paradigm: sim­ ulate a Markov chain whose states are combinatorial structures and which converges to a known probability distribution over them. This technique has applications not only in combinatorial counting and generation, but also in several other areas such as statistical physics and combinatorial optimi­ sation. The efficiency of the technique in any application depends crucially on the rate of convergence of the Markov chain.

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.

Least squares is probably the best known method for fitting linear models and by far the most widely used. Surprisingly, the discrete L 1 analogue, least absolute deviations (LAD) seems to have been considered first. Possibly the LAD criterion was forced into the background because of the com­ putational difficulties associated with it. Recently there has been a resurgence of interest in LAD. It was spurred on by work that has resulted in efficient al­ gorithms for obtaining LAD fits. Another stimulus came from robust statistics. LAD estimates resist undue effects from a feyv, large errors. Therefore. in addition to being robust, they also make good starting points for other iterative, robust procedures. The LAD criterion has great utility. LAD fits are optimal for linear regressions where the errors are double exponential. However they also have excellent properties well outside this narrow context. In addition they are useful in other linear situations such as time series and multivariate data analysis. Finally, LAD fitting embodies a set of ideas that is important in linear optimization theory and numerical analysis. viii PREFACE In this monograph we will present a unified treatment of the role of LAD techniques in several domains. Some of the material has appeared in recent journal papers and some of it is new. This presentation is organized in the following way. There are three parts, one for Theory, one for Applicatior.s and one for Algorithms.

This book constitutes the proceedings of the 17th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2011, held in Seoul, Korea, in December 2011. The 40 revised papers included in this volume were carefully reviewed and selected from 266 submissions. The contributions are organized in topical sections on lattices and quantum cryptography; public key encryption; database privacy; hash function; symmetric key encryption; zero knowledge proof; universal composability; foundation; secure computation and secret sharing; public key signature; and leakage resilient cryptography.

This book constitutes the refereed proceedings of the Second International Workshop on Experimental and Efficient Algorithms, WEA 2003, held in Ascona, Switzerland in May 2003. The 19 revised full papers presented together with 3 invited contributions were carefully reviewed and selected from 40 submissions. The focus of the volume is on applications of efficient algorithms for combinatorial problems.

This book collects selected contributions presented at the INdAM Workshop'Geometric Challenges in Isogeometric Analysis', held in Rome, Italy on January 27-31, 2020. It gives an overview of the forefront research on splines and their efficient use in isogeometric methods for the discretization of differential problems over complex and trimmed geometries. A variety of research topics in this context are covered, including (i) high-quality spline surfaces on complex and trimmed geometries, (ii) construction and analysis of smooth spline spaces on unstructured meshes, (iii) numerical aspects and benchmarking of isogeometric discretizations on unstructured meshes, meshing strategies and software. Given its scope, the book will be of interest to both researchers and graduate students working in the areas of approximation theory, geometric design and numerical simulation.Chapter 10 is available open access under a Creative Commons Attribution 4.0 International License via link.springer.com.

Anja Schedel analyzes two models in the field of algorithmic game theory which both constitute bilevel problems in networks. The first model is a game-theoretic variant of the well-known Steiner forest problem, and one is interested in an optimal sharing of the cost of the Steiner forest. The author provides (and partially exactly characterizes) network structures which allow for cost-minimal pure Nash equilibria. The second model is motivated from privatized public roads, in which private, selfishly acting firms build roads, and as compensation for their investment, are allowed to set prices for using the roads. For a basic model of this situation, the author shows existence and uniqueness of pure Nash equilibria. The existence result requires a non-standard proof approach since techniques like Kakutani's fixed point theorem cannot be applied directly.

We are proud to introduce the proceedings of the Seventh International C- ference on Parallel Problem Solving from Nature, PPSN VII, held in Granada, Spain, on 7–11 September 2002. PPSN VII was organized back-to-back with the Foundations of Genetic Algorithms (FOGA) conference, which took place in Torremolinos, Malaga, Spain, in the preceding week. ThePPSNseriesofconferencesstartedinDortmund,Germany[1].Fromthat pioneering meeting, the event has been held biennially, in Brussels, Belgium [2], Jerusalem, Israel [3], Berlin, Germany [4], Amsterdam, The Netherlands [5], and Paris, France [6]. During the Paris conference, several bids to host PPSN 2002 were put forward; it was decided that the conference would be held in Granada with Juan J. Merelo Guerv´ os as General Chairman. The scienti?c content of the PPSN conference focuses on problem-solving paradigms gleaned from natural models, with an obvious emphasis on those that display an innate parallelism, such as evolutionary algorithms and ant-colony optimization algorithms. The majority of the papers, however, concentrate on evolutionary and hybrid algorithms, as is shown in the contents of this book and itspredecessors.Thiseditionoftheconferenceproceedingshasalargesectionon applications,betheytoclassicalproblemsortoreal-worldengineeringproblems, which shows how bioinspired algorithms are extending their use in the realms of business and enterprise.

This Festschrift is in honor of Ker-I Ko, Professor in the Stony Brook University, USA. Ker-I Ko was one of the founding fathers of computational complexity over real numbers and analysis. He and Harvey Friedman devised a theoretical model for real number computations by extending the computation of Turing machines. He contributed significantly to advancing the theory of structural complexity, especially on polynomial-time isomorphism, instance complexity, and relativization of polynomial-time hierarchy. Ker-I also made many contributions to approximation algorithm theory of combinatorial optimization problems. This volume contains 17 contributions in the area of complexity and approximation. Those articles are authored by researchers over the world, including North America, Europe and Asia. Most of them are co-authors, colleagues, friends, and students of Ker-I Ko.

This textbook is a concise introduction to the basic toolbox of structures that allow efficient organization and retrieval of data, key algorithms for problems on graphs, and generic techniques for modeling, understanding, and solving algorithmic problems. The authors aim for a balance between simplicity and efficiency, between theory and practice, and between classical results and the forefront of research. Individual chapters cover arrays and linked lists, hash tables and associative arrays, sorting and selection, priority queues, sorted sequences, graph representation, graph traversal, shortest paths, minimum spanning trees, optimization, collective communication and computation, and load balancing. The authors also discuss important issues such as algorithm engineering, memory hierarchies, algorithm libraries, and certifying algorithms. Moving beyond the sequential algorithms and data structures of the earlier related title, this book takes into account the paradigm shift towards the parallel processing required to solve modern performance-critical applications and how this impacts on the teaching of algorithms. The book is suitable for undergraduate and graduate students and professionals familiar with programming and basic mathematical language. Most chapters have the same basic structure: the authors discuss a problem as it occurs in a real-life situation, they illustrate the most important applications, and then they introduce simple solutions as informally as possible and as formally as necessary so the reader really understands the issues at hand. As they move to more advanced and optional issues, their approach gradually leads to a more mathematical treatment, including theorems and proofs. The book includes many examples, pictures, informal explanations, and exercises, and the implementation notes introduce clean, efficient implementations in languages such as C++ and Java.

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.

Recent results on non-convex multi-objective optimization problems and methods are presented in this book, with particular attention to expensive black-box objective functions. Multi-objective optimization methods facilitate designers, engineers, and researchers to make decisions on appropriate trade-offs between various conflicting goals. A variety of deterministic and stochastic multi-objective optimization methods are developed in this book. Beginning with basic concepts and a review of non-convex single-objective optimization problems; this book moves on to cover multi-objective branch and bound algorithms, worst-case optimal algorithms (for Lipschitz functions and bi-objective problems), statistical models based algorithms, and probabilistic branch and bound approach. Detailed descriptions of new algorithms for non-convex multi-objective optimization, their theoretical substantiation, and examples for practical applications to the cell formation problem in manufacturing engineering, the process design in chemical engineering, and business process management are included to aide researchers and graduate students in mathematics, computer science, engineering, economics, and business management.

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.

This book offers a theoretical and computational presentation of a variety of linear programming algorithms and methods with an emphasis on the revised simplex method and its components. A theoretical background and mathematical formulation is included for each algorithm as well as comprehensive numerical examples and corresponding MATLAB® code. The MATLAB® implementations presented in this book are sophisticated and allow users to find solutions to large-scale benchmark linear programs. Each algorithm is followed by a computational study on benchmark problems that analyze the computational behavior of the presented algorithms. As a solid companion to existing algorithmic-specific literature, this book will be useful to researchers, scientists, mathematical programmers, and students with a basic knowledge of linear algebra and calculus. The clear presentation enables the reader to understand and utilize all components of simplex-type methods, such as presolve techniques, scaling techniques, pivoting rules, basis update methods, and sensitivity analysis.

The contributions gathered here provide an overview of current research projects and selected software products of the Fraunhofer Institute for Algorithms and Scientific Computing SCAI. They show the wide range of challenges that scientific computing currently faces, the solutions it offers, and its important role in developing applications for industry. Given the exciting field of applied collaborative research and development it discusses, the book will appeal to scientists, practitioners, and students alike. The Fraunhofer Institute for Algorithms and Scientific Computing SCAI combines excellent research and application-oriented development to provide added value for our partners. SCAI develops numerical techniques, parallel algorithms and specialized software tools to support and optimize industrial simulations. Moreover, it implements custom software solutions for production and logistics, and offers calculations on high-performance computers. Its services and products are based on state-of-the-art methods from applied mathematics and information technology.

This textbook discusses the most fundamental and puzzling questions about the foundations of computing. In 23 lecture-sized chapters it provides an exciting tour through the most important results in the field of computability and time complexity, including the Halting Problem, Rice's Theorem, Kleene's Recursion Theorem, the Church-Turing Thesis, Hierarchy Theorems, and Cook-Levin's Theorem. Each chapter contains classroom-tested material, including examples and exercises. Links between adjacent chapters provide a coherent narrative.Fundamental results are explained lucidly by means of programs written in a simple, high-level imperative programming language, which only requires basic mathematical knowledge. Throughout the book, the impact of the presented results on the entire field of computer science is emphasised. Examples range from program analysis to networking, from database programming to popular games and puzzles. Numerous biographical footnotes about the famous scientists who developed the subject are also included.'Limits of Computation'offers a thorough, yet accessible, introduction to computability and complexity for the computer science student of the 21st century.

Optimization in Computational Chemistry and Molecular Biology: Local and Global Approaches covers recent developments in optimization techniques for addressing several computational chemistry and biology problems. A tantalizing problem that cuts across the fields of computational chemistry, biology, medicine, engineering and applied mathematics is how proteins fold. Global and local optimization provide a systematic framework of conformational searches for the prediction of three-dimensional protein structures that represent the global minimum free energy, as well as low-energy biomolecular conformations. Each contribution in the book is essentially expository in nature, but of scholarly treatment. The topics covered include advances in local and global optimization approaches for molecular dynamics and modeling, distance geometry, protein folding, molecular structure refinement, protein and drug design, and molecular and peptide docking. Audience: The book is addressed not only to researchers in mathematical programming, but to all scientists in various disciplines who use optimization methods in solving problems in computational chemistry and biology.

Optimization is of central importance in all sciences. Nature inherently seeks optimal solutions. For example, light travels through the'shortest'path and the folded state of a protein corresponds to the structure with the'minimum'potential energy. In combinatorial optimization, there are numerous computationally hard problems arising in real world applications, such as floorplanning in VLSI designs and Steiner trees in communication networks. For these problems, the exact optimal solution is not currently real-time computable. One usually computes an approximate solution with various kinds of heuristics. Recently, many approaches have been developed that link the discrete space of combinatorial optimization to the continuous space of nonlinear optimization through geometric, analytic, and algebraic techniques. Many researchers have found that such approaches lead to very fast and efficient heuristics for solving large problems. Although almost all such heuristics work well in practice there is no solid theoretical analysis, except Karmakar's algorithm for linear programming. With this situation in mind, we decided to teach a seminar on nonlinear optimization with emphasis on its mathematical foundations. This book is the result of that seminar. During the last decades many textbooks and monographs in nonlinear optimization have been published. Why should we write this new one? What is the difference of this book from the others? The motivation for writing this book originated from our efforts to select a textbook for a graduate seminar with focus on the mathematical foundations of optimization.

An important objective of the study of mathematics is to analyze and visualize phenomena of nature and real world problems for its proper understanding. Gradually, it is also becoming the language of modem financial instruments. To project some of these developments, the conference was planned under the joint auspices of the Indian Society of Industrial and Applied mathematics (ISlAM) and Guru Nanak Dev University (G. N. D. U.), Amritsar, India. Dr. Pammy Manchanda, chairperson of Mathematics Department, G. N. D. U., was appointed the organizing secretary and an organizing committee was constituted. The Conference was scheduled in World Mathematics Year 2000 but, due one reason or the other, it could be held during 22. -25. January 2001. How­ ever, keeping in view the suggestion of the International Mathematics union, we organized two symposia, Role of Mathematics in industrial development and vice-versa and How image of Mathematics can be improved in public. These two symposia aroused great interest among the participants and almost everyone participated in the deliberations. The discussion in these two themes could be summarized in the lengthy following lines:'Tradition of working in isolation is a barrier for interaction with the workers in the other fields of science and engineering, what to talk of non-academic areas, specially the private sector of finance and industry. Therefore, it is essential to build bridges within in­ stitutions and between institutions.

This comprehensive and self-contained textbook presents an accessible overview of the state of the art of multivariate algorithmics and complexity. Increasingly, multivariate algorithmics is having significant practical impact in many application domains, with even more developments on the horizon. The text describes how the multivariate framework allows an extended dialog with a problem, enabling the reader who masters the complexity issues under discussion to use the positive and negative toolkits in their own research. Features: describes many of the standard algorithmic techniques available for establishing parametric tractability; reviews the classical hardness classes; explores the various limitations and relaxations of the methods; showcases the powerful new lower bound techniques; examines various different algorithmic solutions to the same problems, highlighting the insights to be gained from each approach; demonstrates how complexity methods and ideas have evolved over the past 25 years.

This volume addresses some of the research areas in the general field of stability studies for differential equations, with emphasis on issues of concern for numerical studies. Topics considered include: (i) the long time integration of Hamiltonian Ordinary DEs and highly oscillatory systems, (ii) connection between stochastic DEs and geometric integration using the Markov chain Monte Carlo method, (iii) computation of dynamic patterns in evolutionary partial DEs, (iv) decomposition of matrices depending on parameters and localization of singularities, and (v) uniform stability analysis for time dependent linear initial value problems of ODEs. The problems considered in this volume are of interest to people working on numerical as well as qualitative aspects of differential equations, and it will serve both as a reference and as an entry point into further research.

This monograph investigates algorithms for determining power integral bases in algebraic number fields. It introduces the best-known methods for solving several types of diophantine equations using Baker-type estimates, reduction methods, and enumeration algorithms. Particular emphasis is placed on properties of number fields and new applications. The text is illustrated with several tables of various number fields, including their data on power integral bases. Good resource for solving classical types of diophantine equations. Aimed at advanced undergraduate/graduate students and researchers.

A Source Book for the History of Mathematics, but one which offers a different perspective by focusinng on algorithms. With the development of computing has come an awakening of interest in algorithms. Often neglected by historians and modern scientists, more concerned with the nature of concepts, algorithmic procedures turn out to have been instrumental in the development of fundamental ideas: practice led to theory just as much as the other way round. The purpose of this book is to offer a historical background to contemporary algorithmic practice.

This IMA Volume in Mathematics and its Applications ALGORITHMS FOR PARALLEL PROCESSING is based on the proceedings of a workshop that was an integral part of the 1996-97 IMA program on'MATHEMATICS IN HIGH-PERFORMANCE COMPUTING.'The workshop brought together algorithm developers from theory, combinatorics, and scientific computing. The topics ranged over models, linear algebra, sorting, randomization, and graph algorithms and their analysis. We thank Michael T. Heath of University of lllinois at Urbana (Com­ puter Science), Abhiram Ranade of the Indian Institute of Technology (Computer Science and Engineering), and Robert S. Schreiber of Hewlett­ Packard Laboratories for their excellent work in organizing the workshop and editing the proceedings. We also take this opportunity to thank the National Science Founda­ tion (NSF) and the Army Research Office (ARO), whose financial support made the workshop possible. A vner Friedman Robert Gulliver v PREFACE The Workshop on Algorithms for Parallel Processing was held at the IMA September 16 - 20, 1996; it was the first workshop of the IMA year dedicated to the mathematics of high performance computing. The work­ shop organizers were Abhiram Ranade of The Indian Institute of Tech­ nology, Bombay, Michael Heath of the University of Illinois, and Robert Schreiber of Hewlett Packard Laboratories. Our idea was to bring together researchers who do innovative, exciting, parallel algorithms research on a wide range of topics, and by sharing insights, problems, tools, and methods to learn something of value from one another.

In 1994 Peter Shor [65] published a factoring algorithm for a quantum computer that finds the prime factors of a composite integer N more efficiently than is possible with the known algorithms for a classical com­ puter. Since the difficulty of the factoring problem is crucial for the se­ curity of a public key encryption system, interest (and funding) in quan­ tum computing and quantum computation suddenly blossomed. Quan­ tum computing had arrived. The study of the role of quantum mechanics in the theory of computa­ tion seems to have begun in the early 1980s with the publications of Paul Benioff [6]'[7] who considered a quantum mechanical model of computers and the computation process. A related question was discussed shortly thereafter by Richard Feynman [35] who began from a different perspec­ tive by asking what kind of computer should be used to simulate physics. His analysis led him to the belief that with a suitable class of'quantum machines'one could imitate any quantum system.

Semidefinite programs constitute one of the largest classes of optimization problems that can be solved with reasonable efficiency - both in theory and practice. They play a key role in a variety of research areas, such as combinatorial optimization, approximation algorithms, computational complexity, graph theory, geometry, real algebraic geometry and quantum computing. This book is an introduction to selected aspects of semidefinite programming and its use in approximation algorithms. It covers the basics but also a significant amount of recent and more advanced material. There are many computational problems, such as MAXCUT, for which one cannot reasonably expect to obtain an exact solution efficiently, and in such case, one has to settle for approximate solutions. For MAXCUT and its relatives, exciting recent results suggest that semidefinite programming is probably the ultimate tool. Indeed, assuming the Unique Games Conjecture, a plausible but as yet unproven hypothesis, it was shown that for these problems, known algorithms based on semidefinite programming deliver the best possible approximation ratios among all polynomial-time algorithms. This book follows the “semidefinite side” of these developments, presenting some of the main ideas behind approximation algorithms based on semidefinite programming. It develops the basic theory of semidefinite programming, presents one of the known efficient algorithms in detail, and describes the principles of some others. It also includes applications, focusing on approximation algorithms.

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.

During the last three decades several different styles of semantics for program­ ming languages have been developed. This book compares two of them: the operational and the denotational approach. On the basis of several exam­ ples we show how to define operational and denotational semantic models for programming languages. Furthermore, we introduce a general technique for comparing various semantic models for a given language. We focus on different degrees of nondeterminism in programming lan­ guages. Nondeterminism arises naturally in concurrent languages. It is also an important concept in specification languages. In the examples discussed, the degree of non determinism ranges from a choice between two alternatives to a choice between a collection of alternatives indexed by a closed interval of the real numbers. The former arises in a language with nondeterministic choices. A real time language with dense choices gives rise to the latter. We also consider the nondeterministic random assignment and parallel composition, both couched in a simple language. Besides non determinism our four example languages contain some form of recursion, a key ingredient of programming languages.

Starting with Cook's pioneering work on NP-completeness in 1970, polynomial complexity theory, the study of polynomial-time com­ putability, has quickly emerged as the new foundation of algorithms. On the one hand, it bridges the gap between the abstract approach of recursive function theory and the concrete approach of analysis of algorithms. It extends the notions and tools of the theory of computability to provide a solid theoretical foundation for the study of computational complexity of practical problems. In addition, the theoretical studies of the notion of polynomial-time tractability some­ times also yield interesting new practical algorithms. A typical exam­ ple is the application of the ellipsoid algorithm to combinatorial op­ timization problems (see, for example, Lovasz [1986]). On the other hand, it has a strong influence on many different branches of mathe­ matics, including combinatorial optimization, graph theory, number theory and cryptography. As a consequence, many researchers have begun to re-examine various branches of classical mathematics from the complexity point of view. For a given nonconstructive existence theorem in classical mathematics, one would like to find a construc­ tive proof which admits a polynomial-time algorithm for the solution. One of the examples is the recent work on algorithmic theory of per­ mutation groups. In the area of numerical computation, there are also two tradi­ tionally independent approaches: recursive analysis and numerical analysis.

Recently, a variety ofresults on the complexitystatusofthegraph isomorphism problem has been obtained. These results belong to the so-called structural part of Complexity Theory. Our idea behind this book is to summarize such results which might otherwise not be easily accessible in the literature, and also, to give the reader an understanding of the aims and topics in Structural Complexity Theory, in general. The text is basically self contained; the only prerequisite for reading it is some elementary knowledge from Complexity Theory and Probability Theory. It can be used to teach a seminar or a monographic graduate course, but also parts of it (especially Chapter 1) provide a source of examples for a standard graduate course on Complexity Theory. Many people have helped us in different ways III the process of writing this book. Especially, we would like to thank V. Arvind, R.V. Book, E. May­ ordomo, and the referee who gave very constructive comments. This book project was especially made possible by a DAAD grant in the'Acciones In­ tegrada'program. The third author has been supported by the ESPRIT project ALCOM-II.

­The present book provides an introduction to using space-filling curves (SFC) as tools in scientific computing. Special focus is laid on the representation of SFC and on resulting algorithms. For example, grammar-based techniques are introduced for traversals of Cartesian and octree-type meshes, and arithmetisation of SFC is explained to compute SFC mappings and indexings.­The locality properties of SFC are discussed in detail, together with their importance for algorithms. Templates for parallelisation and cache-efficient algorithms are presented to reflect the most important applications of SFC in scientific computing. Special attention is also given to the interplay of adaptive mesh refinement and SFC, including the structured refinement of triangular and tetrahedral grids. For each topic, a short overview is given on the most important publications and recent research activities.

... that is what learning is. You suddenly understand something you've un­ derstood all your life, but in a new way. Various transforms have been widely used in diverse applications of science, engineering and technology. New transforms are emerging to solve many problems, which may have been left unsolved in the past, or newly created by modern science or technologies. Various meth­ ods have been continuously reported to improve the implementation of these transforms. Early developments of fast algorithms for discrete transforms have significantly stimulated the advance of digital signal processing technologies. More than 40 years after fast Fourier transform algorithms became known, several discrete transforms, including the discrete Hart­ ley transform and discrete cosine transform, were proposed and widely used for numerous applications. Although they all are related to the discrete Fourier transform, different fast algorithms and their implementations have to be separately developed to minimize compu­ tational complexity and implementation costs. In spite of the tremendous increase in the speed of computers or processors, the demands for higher processing throughout seemingly never ends. Fast algorithms have become more important than ever for modern applications to become a reality. Many new algorithms recently reported in the literature have led to important improvements upon a number of issues, which will be addressed in this book. Some discrete transforms are not suitable for signals that have time-varying frequency components. Although several approaches are available for such applications, various inher­ ent problems still remain unsolved.

Als mehrbändiges Nachschlagewerk ist das Springer-Handbuch der Mathematik in erster Linie für wissenschaftliche Bibliotheken, akademische Institutionen und Firmen sowie interessierte Individualkunden in Forschung und Lehre gedacht. Es ergänzt das einbändige themenumfassende Springer-Taschenbuch der Mathematik (ehemaliger Titel Teubner-Taschenbuch der Mathematik), das sich in seiner begrenzten Stoffauswahl besonders an Studierende richtet. Teil III des Springer-Handbuchs enthält neben den Kapiteln 5-9 des Springer-Taschenbuchs zusätzliches Material zu stochastischen Prozessen.​

“The book is outstanding and admirable in many respects.... is necessary reading for all kinds of readers from undergraduate students to top authorities in the field.” Journal of Symbolic Logic Written by two experts in the field, this is the only comprehensive and unified treatment of the central ideas and applications of Kolmogorov complexity. The book presents a thorough treatment of the subject with a wide range of illustrative applications. Such applications include the randomness of finite objects or infinite sequences, Martin-Loef tests for randomness, information theory, computational learning theory, the complexity of algorithms, and the thermodynamics of computing. It will be ideal for advanced undergraduate students, graduate students, and researchers in computer science, mathematics, cognitive sciences, philosophy, artificial intelligence, statistics, and physics. The book is self-contained in that it contains the basic requirements from mathematics and computerscience. Included are also numerous problem sets, comments, source references, and hints to solutions of problems. New topics in this edition include Omega numbers, Kolmogorov–Loveland randomness, universal learning, communication complexity, Kolmogorov's random graphs, time-limited universal distribution, Shannon information and others.

This concise textbook presents the mathematics that is foundational to multimedia applications. Featuring a rigorous survey of selected results from algebra and analysis, the work examines tools used to create application software for multimedia signal processing and communication. Key features include: • Over 100 exercises with complete solutions; • Useful algorithms presented in pseudocode and Standard C to help readers with programming, experimentation, and the solution of exercises; • Numerous illustrations based on data from real studies; • Suggestions for further reading at the end of each chapter; • A companion website—maintained by the author—providing computer programs described in the book as well as additional references and data files, such as images and sounds, to enhance the reader's understanding of key topics; • A supplementary manual—containing several hundred exercises, solutions, and sample programs not included in the book—available to instructors upon request; • Minimal prerequisites—only an undergraduate-level knowledge of mathematics, not including statistics, is required. Mathematics for Multimedia is an ideal textbook for upper undergraduate and beginning graduate students in pure and applied mathematics, engineering, and computer science seeking an innovative approach to contemporary mathematics with practical applications. The work may also serve as a useful reference for multimedia applications developers and other researchers and practitioners interested in the mathematics underlying multimedia software design and implementation.

“To this reviewer's knowledge, this is the first book accessible to the upper division undergraduate or beginning graduate student that surveys linear programming from the Simplex Method…via the Ellipsoid algorithm to Karmarkar's algorithm. Moreover, its point of view is algorithmic and thus it provides both a history and a case history of work in complexity theory. The presentation is admirable; Karloff's style is informal...without sacrificing anything necessary for understanding. Diagrams...aid in providing clarity. The end-of-chapter notes are helpful...Recommended highly for acquisition, since it is not only a textbook, but can also be used for independent reading and study.” (Choice Reviews) “The reader will be well served by reading the monograph from cover to cover.” (Mathematics of Computing) “This is a textbook intended for advanced undergraduate or graduate students. It contains both theory and computational practice.” (Zentralblatt Math) “The exposition is clear and elementary; it also contains many exercises and illustrations.” (Mathematical Reviews) “A self-contained, concise mathematical introduction to the theory of linear programming.” (Journal of Economic Literature)

This book introduces the reader to a recent theory in Computer Vision yielding elementary techniques to analyse digital images. These techniques are inspired from and are a mathematical formalization of the Gestalt theory. Gestalt theory, which had never been formalized is a rigorous realm of vision psychology developped between 1923 and 1975. From the mathematical viewpoint the closest field to it is stochastic geometry, involving basic probability and statistics, in the context of image analysis. The book is intended for a multidisciplinary audience of researchers and engineers. It is self contained in three aspects: mathematics, vision and algorithms, and requires only a background of elementary calculus and probability. A large number of illustrations, exercises and examples are included. The authors maintain a public software, MegaWave, containing implementations of most of the image analysis techniques developed in the book.