Books in Analysis of algorithms and problem complexity

Network Routing

1st Edition
March 29, 2007
English
Hardback
9 7 8 0 1 2 0 8 8 5 8 8 6
eBook
9 7 8 0 0 8 0 4 7 4 9 7 7

Network routing can be broadly categorized into Internet routing, PSTN routing, and telecommunication transport network routing. This book systematically considers these routing paradigms, as well as their interoperability. The authors discuss how algorithms, protocols, analysis, and operational deployment impact these approaches. A unique feature of the book is consideration of both macro-state and micro-state in routing; that is, how routing is accomplished at the level of networks and how routers or switches are designed to enable efficient routing.In reading this book, one will learn about 1) the evolution of network routing, 2) the role of IP and E.164 addressing in routing, 3) the impact on router and switching architectures and their design, 4) deployment of network routing protocols, 5) the role of traffic engineering in routing, and 6) lessons learned from implementation and operational experience. This book explores the strengths and weaknesses that should be considered during deployment of future routing schemes as well as actual implementation of these schemes. It allows the reader to understand how different routing strategies work and are employed and the connection between them. This is accomplished in part by the authors' use of numerous real-world examples to bring the material alive.

Stochastic Local Search

1st Edition
September 16, 2004
Holger H. Hoos + 1 more
English
Hardback
9 7 8 1 5 5 8 6 0 8 7 2 6
eBook
9 7 8 0 0 8 0 4 9 8 2 4 9

Stochastic local search (SLS) algorithms are among the most prominent and successful techniques for solving computationally difficult problems in many areas of computer science and operations research, including propositional satisfiability, constraint satisfaction, routing, and scheduling. SLS algorithms have also become increasingly popular for solving challenging combinatorial problems in many application areas, such as e-commerce and bioinformatics.Hoos and Stützle offer the first systematic and unified treatment of SLS algorithms. In this groundbreaking new book, they examine the general concepts and specific instances of SLS algorithms and carefully consider their development, analysis and application. The discussion focuses on the most successful SLS methods and explores their underlying principles, properties, and features. This book gives hands-on experience with some of the most widely used search techniques, and provides readers with the necessary understanding and skills to use this powerful tool.

Computational Complexity: A Quantitative Perspective

1st Edition
Volume 196
July 7, 2004
Marius Zimand
English
eBook
9 7 8 0 0 8 0 4 7 6 6 6 7

There has been a common perception that computational complexity is a theory of "bad news" because its most typical results assert that various real-world and innocent-looking tasks are infeasible. In fact, "bad news" is a relative term, and, indeed, in some situations (e.g., in cryptography), we want an adversary to not be able to perform a certain task. However, a "bad news" result does not automatically become useful in such a scenario. For this to happen, its hardness features have to be quantitatively evaluated and shown to manifest extensively.The book undertakes a quantitative analysis of some of the major results in complexity that regard either classes of problems or individual concrete problems. The size of some important classes are studied using resource-bounded topological and measure-theoretical tools. In the case of individual problems, the book studies relevant quantitative attributes such as approximation properties or the number of hard inputs at each length.One chapter is dedicated to abstract complexity theory, an older field which, however, deserves attention because it lays out the foundations of complexity. The other chapters, on the other hand, focus on recent and important developments in complexity. The book presents in a fairly detailed manner concepts that have been at the centre of the main research lines in complexity in the last decade or so, such as: average-complexity, quantum computation, hardness amplification, resource-bounded measure, the relation between one-way functions and pseudo-random generators, the relation between hard predicates and pseudo-random generators, extractors, derandomization of bounded-error probabilistic algorithms, probabilistically checkable proofs, non-approximability of optimization problems, and others.The book should appeal to graduate computer science students, and to researchers who have an interest in computer science theory and need a good understanding of computational complexity, e.g., researchers in algorithms, AI, logic, and other disciplines.

Art and Complexity

1st Edition
February 19, 2003
J. Casti + 1 more
English
Hardback
9 7 8 0 4 4 4 5 0 9 4 4 4
eBook
9 7 8 0 0 8 0 5 2 7 5 8 1

This title is the result of a one-week workshop sponsored by the Swedish research agency, FRN, on the interface between complexity and art. Among others, it includes discussions on whether "good" art is "complex" art, how artists see the term "complex", and what poets try to convey in word about complex behavior in nature.

Mathematical Logic

1st Edition
Volume 4
December 5, 2001
R.O. Gandy + 1 more
English
eBook
9 7 8 0 0 8 0 5 3 5 9 2 0

Mathematical Logic is a collection of the works of one of the leading figures in 20th-century science. This collection of A.M. Turing's works is intended to include all his mature scientific writing, including a substantial quantity of unpublished material. His work in pure mathematics and mathematical logic extended considerably further; the work of his last years, on morphogenesis in plants, is also of the greatest originality and of permanent importance. This book is divided into three parts. The first part focuses on computability and ordinal logics and covers Turing's work between 1937 and 1938. The second part covers type theory; it provides a general introduction to Turing's work on type theory and covers his published and unpublished works between 1941 and 1948. Finally, the third part focuses on enigmas, mysteries, and loose ends. This concluding section of the book discusses Turing's Treatise on the Enigma, with excerpts from the Enigma Paper. It also delves into Turing's papers on programming and on minimum cost sequential analysis, featuring an excerpt from the unpublished manuscript. This book will be of interest to mathematicians, logicians, and computer scientists.

Handbook of Computability Theory

1st Edition
Volume 140
October 1, 1999
E.R. Griffor
English
eBook
9 7 8 0 0 8 0 5 3 3 0 4 9

The chapters of this volume all have their own level of presentation. The topics have been chosen based on the active research interest associated with them. Since the interest in some topics is older than that in others, some presentations contain fundamental definitions and basic results while others relate very little of the elementary theory behind them and aim directly toward an exposition of advanced results. Presentations of the latter sort are in some cases restricted to a short survey of recent results (due to the complexity of the methods and proofs themselves). Hence the variation in level of presentation from chapter to chapter only reflects the conceptual situation itself. One example of this is the collective efforts to develop an acceptable theory of computation on the real numbers. The last two decades has seen at least two new definitions of effective operations on the real numbers.

Compression Algorithms for Real Programmers

1st Edition
September 30, 1999
Peter Wayner
English
eBook
9 7 8 0 0 8 0 5 0 2 4 3 4

In life, time is money, and on the Internet, the size of data is money. Small programs and small files take less disk space and cost less to send over the Internet. Compression Algorithms for Real Programmers describes the basic algorithms and approaches for compressing information so you can create the smallest files possible. These new algorithms are making it possible for people to take impossibly large audio and video files and compress them enough that they can flow over the Internet.

Recursive Model Theory

1st Edition
Volume 1
November 30, 1998
Y.L. Ershov + 3 more
English
eBook
9 7 8 0 0 8 0 5 3 3 6 9 8

Recursive Algebra, Analysis and Combinatorics

1st Edition
Volume 2
November 30, 1998
Y.L. Ershov + 3 more
English
eBook
9 7 8 0 0 8 0 5 3 3 7 0 4

Handbook of Proof Theory

1st Edition
Volume 137
July 9, 1998
S.R. Buss
English
Hardback
9 7 8 0 4 4 4 8 9 8 4 0 1
eBook
9 7 8 0 0 8 0 5 3 3 1 8 6

This volume contains articles covering a broad spectrum of proof theory, with an emphasis on its mathematical aspects. The articles should not only be interesting to specialists of proof theory, but should also be accessible to a diverse audience, including logicians, mathematicians, computer scientists and philosophers. Many of the central topics of proof theory have been included in a self-contained expository of articles, covered in great detail and depth.The chapters are arranged so that the two introductory articles come first; these are then followed by articles from core classical areas of proof theory; the handbook concludes with articles that deal with topics closely related to computer science.

Life Sciences

Physical Sciences & Engineering

Social Sciences & Humanities

Health