Bøger i Combinatorial Optimization serien

The technique of randomization has been employed to solve numerous prob­ lems of computing both sequentially and in parallel. Examples of randomized algorithms that are asymptotically better than their deterministic counterparts in solving various fundamental problems abound. Randomized algorithms have the advantages of simplicity and better performance both in theory and often in practice. This book is a collection of articles written by renowned experts in the area of randomized parallel computing. A brief introduction to randomized algorithms In the aflalysis of algorithms, at least three different measures of performance can be used: the best case, the worst case, and the average case. Often, the average case run time of an algorithm is much smaller than the worst case. 2 For instance, the worst case run time of Hoare's quicksort is O(n ), whereas its average case run time is only O( n log n). The average case analysis is conducted with an assumption on the input space. The assumption made to arrive at the O( n log n) average run time for quicksort is that each input permutation is equally likely. Clearly, any average case analysis is only as good as how valid the assumption made on the input space is. Randomized algorithms achieve superior performances without making any assumptions on the inputs by making coin flips within the algorithm. Any analysis done of randomized algorithms will be valid for all p0:.sible inputs.

The research and development of pattern recognition have proven to be of importance in science, technology, and human activity. Many useful concepts and tools from different disciplines have been employed in pattern recognition. Among them is string matching, which receives much theoretical and practical attention. String matching is also an important topic in combinatorial optimization. This book is devoted to recent advances in pattern recognition and string matching. It consists of twenty eight chapters written by different authors, addressing a broad range of topics such as those from classifica­ tion, matching, mining, feature selection, and applications. Each chapter is self-contained, and presents either novel methodological approaches or applications of existing theories and techniques. The aim, intent, and motivation for publishing this book is to pro­ vide a reference tool for the increasing number of readers who depend upon pattern recognition or string matching in some way. This includes students and professionals in computer science, mathematics, statistics, and electrical engineering. We wish to thank all the authors for their valuable efforts, which made this book a reality. Thanks also go to all reviewers who gave generously of their time and expertise.

This book is a collection of articles studying various Steiner tree prob­ lems with applications in industries, such as the design of electronic cir­ cuits, computer networking, telecommunication, and perfect phylogeny. The Steiner tree problem was initiated in the Euclidean plane. Given a set of points in the Euclidean plane, the shortest network interconnect­ ing the points in the set is called the Steiner minimum tree. The Steiner minimum tree may contain some vertices which are not the given points. Those vertices are called Steiner points while the given points are called terminals. The shortest network for three terminals was first studied by Fermat (1601-1665). Fermat proposed the problem of finding a point to minimize the total distance from it to three terminals in the Euclidean plane. The direct generalization is to find a point to minimize the total distance from it to n terminals, which is still called the Fermat problem today. The Steiner minimum tree problem is an indirect generalization. Schreiber in 1986 found that this generalization (i.e., the Steiner mini­ mum tree) was first proposed by Gauss.

The technique of randomization has been employed to solve numerous prob- lems of computing both sequentially and in parallel. Examples of randomized algorithms that are asymptotically better than their deterministic counterparts in solving various fundamental problems abound. Randomized algorithms have the advantages of simplicity and better performance both in theory and often in practice. This book is a collection of articles written by renowned experts in the area of randomized parallel computing. A brief introduction to randomized algorithms In the aflalysis of algorithms, at least three different measures of performance can be used: the best case, the worst case, and the average case. Often, the average case run time of an algorithm is much smaller than the worst case. 2 For instance, the worst case run time of Hoare's quicksort is O(n ), whereas its average case run time is only O( n log n). The average case analysis is conducted with an assumption on the input space. The assumption made to arrive at the O( n log n) average run time for quicksort is that each input permutation is equally likely. Clearly, any average case analysis is only as good as how valid the assumption made on the input space is. Randomized algorithms achieve superior performances without making any assumptions on the inputs by making coin flips within the algorithm. Any analysis done of randomized algorithms will be valid for all p0:.sible inputs.

VII Preface In many fields of mathematics, geometry has established itself as a fruitful method and common language for describing basic phenomena and problems as well as suggesting ways of solutions.

Steiner's Problem concerns finding a shortest interconnecting network for a finite set of points in a metric space. The worst case for this ratio running over all finite sets is called the Steiner ratio of the space.

Nonlinear Assignment Problems (NAPs) are natural extensions of the classic Linear Assignment Problem, and despite the efforts of many researchers over the past three decades, they still remain some of the hardest combinatorial optimization problems to solve exactly.

applications to general combinatorial optimization problems such as graph partitioning and the traveling salesman problem; Additional chapters discuss optimization in reconfigurable computing, convergence in multilevel optimization, and model problems with PDE constraints.

This book gives a comprehensive presentation of cutting-edge research in communication networks with a combinatorial optimization component. The objective of the book is to advance and promote the theory and applications of combinatorial optimization in communication networks.

This book gives a comprehensive presentation of cutting-edge research in communication networks with a combinatorial optimization component. The objective of the book is to advance and promote the theory and applications of combinatorial optimization in communication networks.

The aim in this graduate level text is to outline the key mathematical concepts that underpin these important questions in applied mathematics. These concepts involve discrete mathematics (particularly graph theory), optimization, computer science, and several ideas in biology.

This book is the only recent title to present polyhedral results and exact solution methods for location problems encountered in telecommunications, but which also have applications in other areas, such as transportation and supply chain management.

Nonlinear Assignment Problems (NAPs) are natural extensions of the classic Linear Assignment Problem, and despite the efforts of many researchers over the past three decades, they still remain some of the hardest combinatorial optimization problems to solve exactly.

A brief introduction to randomized algorithms In the analysis of algorithms, at least three different measures of performance can be used: the best case, the worst case, and the average case. 2 For instance, the worst case run time of Hoare's quicksort is O(n ), whereas its average case run time is only O(nlogn).

Three basic classes can be identified in location analysis: continuous location, network location and dis crete location.

The protection approach preas signs spare capacity to protect each element of the network independently, while the restoration approach spreads the redundant capacity over the whole network and uses it as required in order to restore the disrupted traffic.

The research and development of pattern recognition have proven to be of importance in science, technology, and human activity. The aim, intent, and motivation for publishing this book is to pro vide a reference tool for the increasing number of readers who depend upon pattern recognition or string matching in some way.

The book covers all important areas of study on TSP, including polyhedral theory for symmetric and asymmetric TSP, branch and bound, and branch and cut algorithms, probabilistic aspects of TSP, and includes a thorough computational analysis of heuristic and metaheuristic algorithms.

Three basic classes can be identified in location analysis: continuous location, network location and dis crete location.

The protection approach preas signs spare capacity to protect each element of the network independently, while the restoration approach spreads the redundant capacity over the whole network and uses it as required in order to restore the disrupted traffic.

Presents a morphological approach to the combinatorial design/synthesis of decomposable systems. The applications involve: design (information systems; user's interfaces; educational courses); planning (problem-solving strategies; product life cycles; investment); metaheuristics for combinatorial optimization; and information retrieval.

applications to general combinatorial optimization problems such as graph partitioning and the traveling salesman problem; Additional chapters discuss optimization in reconfigurable computing, convergence in multilevel optimization, and model problems with PDE constraints.

Steiner's Problem concerns finding a shortest interconnecting network for a finite set of points in a metric space. The worst case for this ratio running over all finite sets is called the Steiner ratio of the space.

This is the first book about the discrete ordered median problem (DOMP), which unifies many classical and new facility location problems.

The given set ofpoints are 3 Figure 1: Euclidean Steiner Problem in E usually referred to as terminals and the set ofpoints that may be added to reduce the overall length of the network are referred to as Steiner points.

The book covers all important areas of study on TSP, including polyhedral theory for symmetric and asymmetric TSP, branch and bound, and branch and cut algorithms, probabilistic aspects of TSP, and includes a thorough computational analysis of heuristic and metaheuristic algorithms.