SIAM Monographs on Discrete Mathematics and Applications – serie

This volume presents the locality-sensitive approach to distributed network algorithms - the utilization of locality to simplify control structures and algorithms and reduce their costs. The author begins with an introductory exposition of distributed network algorithms focusing on topics that illustrate the role of locality in distributed algorithmic techniques. He then introduces locality-preserving network representations and describes sequential and distributed techniques for their construction. Finally, the applicability of the locality-sensitive approach is demonstrated through several applications.Distributed Computing: A Locality-Sensitive Approach is the only book that gives a thorough exposition of network spanners and other locality-preserving network representations such as sparse covers and partitions. The book is useful for computer scientists interested in distributed computing, electrical engineers interested in network architectures and protocols, and for discrete mathematicians and graph theorists.

Combinatorial data analysis (CDA) refers to a wide class of methods for the study of relevant data sets in which the arrangement of a collection of objects is absolutely central. The focus of this monograph is on the identification of arrangements, which are then further restricted to where the combinatorial search is carried out by a recursive optimization process based on the general principles of dynamic programming (DP).The authors provide a comprehensive and self-contained review delineating a very general DP paradigm or schema that can serve two functions. First, the paradigm can be applied in various special forms to encompass all previously proposed applications suggested in the classification literature. Second, the paradigm can lead directly to many more novel uses. An appendix is included as a user's manual for a collection of programs available as freeware.The incorporation of a wide variety of CDA tasks under one common optimization framework based on DP is one of the book's strongest points. The authors include verifiably optimal solutions to nontrivially sized problems over the array of data analysis tasks discussed.

Discrete Convex Analysis is a novel paradigm for discrete optimization that combines the ideas in continuous optimization (convex analysis) and combinatorial optimization (matroid/submodular function theory) to establish a unified theoretical framework for nonlinear discrete optimization. The study of this theory is expanding with the development of efficient algorithms and applications to a number of diverse disciplines like matrix theory, operations research, and economics.This self-contained book is designed to provide a novel insight into optimization on discrete structures and should reveal unexpected links among different disciplines. It is the first and only English-language monograph on the theory and applications of discrete convex analysis.

This monograph offers a systematic quantitative approach to the analysis, evaluation, and design of electoral systems. Today, electoral reform is of concern to newborn democracies as well as many old ones. The authors use mathematical models and automatic procedures, when possible, to solve some of the problems that arise in the comparison of existing systems as well as in the construction of new ones. One distinctive feature of the book is the emphasis on single- and multiple-criteria optimization methods. This powerful tool kit will help political researchers evaluate and choose an appropriate electoral system.A general formal model is included as well as a coding system to describe, identify, and classify electoral systems. Evaluation criteria and the corresponding performance indicators are discussed. A treatment of electoral formulas as algorithms to minimize actual cost functions or disproportionality indexes is also included. Neutral automatic procedures for political districting are presented, and the process of electoral reform is analyzed from historical and political points of view.