Series: Cambridge Texts in Applied Mathematics
ISBN: 9781107007512 hard cover
ISBN: 9780521189439 soft cover
44 b/w illus. 102 exercises
Dimensions: 228 x 152 mm
available from June 2011
With the advent of approximation algorithms for NP-hard combinatorial optimization problems, several techniques from exact optimization such as the primal-dual method have proven their staying power and versatility. This book describes a simple and powerful method that is iterative in essence, and similarly useful in a variety of settings for exact and approximate optimization. The authors highlight the commonality and uses of this method to prove a variety of classical polyhedral results on matchings, trees, matroids, and flows. The presentation style is elementary enough to be accessible to anyone with exposure to basic linear algebra and graph theory, making the book suitable for introductory courses in combinatorial optimization at the upper undergraduate and beginning graduate levels. Discussions of advanced applications illustrate their potential for future application in research in approximation algorithms.
Features
* This book presents a unified way of looking at several problems
* This book offers new ways of deriving classical results in optimization
* Provides extensions to hard variants of classical problems, and how to identify them
* Offers elementary presentation appealing to a broad mathematically interested audience
1. Introduction
2. Preliminaries
3. Matching and vertex cover in bipartite graphs
4. Spanning trees
5. Matroids
6. Arborescence and rooted connectivity
7. Submodular flows and applications
8. Network matrices
9. Matchings
10. Network design
11. Constrained optimization problems
12. Cut problems
13. Iterative relaxation: early and recent examples
14. Summary.
Series: London Mathematical Society Lecture Note Series (No. 386)
ISBN: 9780521149341 Paperback
20 b/w illus.
Dimensions: 228 x 152 mm
available from April 2011
Bringing together over twenty years of research, this book gives a complete overview of independence-friendly logic. It emphasizes the game-theoretical approach to logic, according to which logical concepts such as truth and falsity are best understood via the notion of semantic games. The book pushes the paradigm of game-theoretical semantics further than the current literature by showing how mixed strategies and equilibria can be used to analyze independence-friendly formulas on finite models. The book is suitable for graduate students and advanced undergraduates who have taken a course on first-order logic. It contains a primer of the necessary background in game theory, numerous examples and full proofs.
Features
* Collects and systematizes results from the last 20 years
* Provides the necessary background in game theory
* Includes numerous examples and full proofs
Preface
1. Introduction
2. Game theory
3. First-order logic
4. Independence-friendly (IF) logic
5. Properties of IF logic
6. Expressive power of IF logic
7. Probabilistic IF logic
8. Further topics
References
Index.
ISBN: 9780521196765 Hardback
125 b/w illus. 25 tables
Dimensions: 247 x 174 mm
available from May 2011
'What's going to happen next*' Time series data hold the answers, and Bayesian methods represent the cutting edge in learning what they have to say. This ambitious book is the first unified treatment of the emerging knowledge-base in Bayesian time series techniques. Exploiting the unifying framework of probabilistic graphical models, the book covers approximation schemes, both Monte Carlo and deterministic, and introduces switching, multi-object, non-parametric and agent-based models in a variety of application environments. It demonstrates that the basic framework supports the rapid creation of models tailored to specific applications and gives insight into the computational complexity of their implementation. The authors span traditional disciplines such as statistics and engineering and the more recently established areas of machine learning and pattern recognition. Readers with a basic understanding of applied probability, but no experience with time series analysis, are guided from fundamental concepts to the state-of-the-art in research and practice.
Features
* The first unified treatment of the emerging knowledge-base in Bayesian time series techniques
* Real-world examples range from bioinformatics to control theory
* Treats classical models as well as the more advanced
Contributors
Preface
1. Inference and estimation in probabilistic time series models David Barber, A. Taylan Cemgil and Silvia Chiappa
Part I. Monte Carlo: 2. Adaptive Markov chain Monte Carlo: theory and methods Yves Atchade, Gersende Fort, Eric Moulines and Pierre Priouret
3. Auxiliary particle filtering: recent developments Nick Whiteley and Adam M. Johansen
4. Monte Carlo probabilistic inference for diffusion processes: a methodological framework Omiros Papaspiliopoulos
Part II. Deterministic Approximations: 5. Two problems with variational expectation maximisation for time series models Richard Eric Turner and Maneesh Sahani
6. Approximate inference for continuous-time Markov processes Cedric Archambeau and Manfred Opper
7. Expectation propagation and generalised EP methods for inference in switching linear dynamical systems Onno Zoeter and Tom Heskes
8. Approximate inference in switching linear dynamical systems using Gaussian mixtures David Barber
Part III. Change-Point Models: 9. Analysis of change-point models Idris A. Eckley, Paul Fearnhead and Rebecca Killick
Part IV. Multi-Object Models: 10. Approximate likelihood estimation of static parameters in multi-target models Sumeetpal S. Singh, Nick Whiteley and Simon J. Godsill
11. Sequential inference for dynamically evolving groups of objects Sze Kim Pang, Simon J. Godsill, Jack Li, Francois Septier and Simon Hill
12. Non-commutative harmonic analysis in multi-object tracking Risi Kondor
13. Physiological monitoring with factorial switching linear dynamical systems John A. Quinn and Christopher K. I. Williams
Part V. Non-Parametric Models: 14. Markov chain Monte Carlo algorithms for Gaussian processes Michalis K. Titsias, Magnus Rattray and Neil D. Lawrence
15. Non-parametric hidden Markov models Jurgen Van Gael and Zoubin Ghahramani
16. Bayesian Gaussian process models for multi-sensor time series prediction Michael A. Osborne, Alex Rogers, Stephen J. Roberts, Sarvapali D. Ramchurn and Nick R. Jennings
Part VI. Agent Based Models: 17. Optimal control theory and the linear Bellman equation Hilbert J. Kappen
18. Expectation-maximisation methods for solving (PO)MDPs and optimal control problems Marc Toussaint, Amos Storkey and Stefan Harmeling
Index.
Series: London Mathematical Society Lecture Note Series (No. 387)
ISBN: 9780521279031 Paperback
22 b/w illus. 6 tables
Dimensions: 228 x 152 mm
available from May 2011
Groups St Andrews 2009 was held in the University of Bath in August 2009 and this first volume of a two-volume book contains selected papers from the international conference. Five main lecture courses were given at the conference, and articles based on their lectures form a substantial part of the proceedings. This volume contains the contributions by Gerhard Hiss (RWTH Aachen) and Volodymyr Nekrashevych (Texas A&M). Apart from the main speakers, refereed survey and research articles were contributed by other conference participants. Arranged in alphabetical order, these articles cover a wide spectrum of modern group theory. The regular proceedings of Groups St Andrews conferences have provided snapshots of the state of research in group theory throughout the past 30 years. Earlier volumes have had a major impact on the development of group theory and it is anticipated that this volume will be equally important.
Features
* Contains expository articles by leading mathematicians in group theory
* Forms part of an extensive four-yearly series of such volumes which have shaped the direction of research in group theory
* Provides a snapshot of the state of research in group theory
Introduction C. M. Campbell and E. F. Robertson
A speech in honour of John Cannon and Derek Holt Charles Leedham-Green
1. Finite groups of Lie type and their representations Gerhard Hiss
2. Iterated monodromy groups Volodymyr Nekrashevych
3. Engel elements in groups Alireza Abdollahi
4. Some classes of finite semigroups with kite-like egg-boxes of D-classes K. Ahmadidelir and H. Doostie
5. Structure of finite groups having few conjugacy class sizes Antonio Beltran and Maria Jose Felipe
6. Group theory in cryptography Simon R. Blackburn, Carlos Cid and Ciaran Mullan
7. A survey of recent results in groups and orderings: word problems, embeddings and amalgamations V. V. Bludov and A. M. W. Glass
8. A survey on the minimum genus and maximum order problems for bordered Klein surfaces E. Bujalance, F. J. Cirre, J. J. Etayo, G. Gromadzki and E. Martinez
9. On one-relator quotients of the modular group Marston Conder, George Havas and M. F. Newman
Miscellaneous results on supersolvable groups K. Corradi, P. Z. Hermann, L. Hethelyi and E. Horvath
10. Automorphisms of products of finite groups M. John Curran
11. A rational property of the irreducible characters of a finite group M. R. Darafsheh, A. Iranmanesh and S. A. Moosavi
12. Automotives Marian Deaconescu and Gary Walls
13. On n-abelian groups and their generalizations Costantino Delizia and Antonio Tortora
14. Computing with matrix groups over infinite fields A. S. Detinko, B. Eick and D. L. Flannery
15. Trends in infinite dimensional linear groups Martyn R. Dixon, Leonid A. Kurdachenko, Jose M. Munoz-Escolano and Javier Otal
16. Engel conditions on orderable groups and in combinatorial problems (a survey) Marcel Herzog, Patrizia Longobardi and Mercede Maj.
Series: London Mathematical Society Lecture Note Series (No. 388)
ISBN: 9780521279048 Paperback
13 b/w illus.
Dimensions: 228 x 152 mm
available from May 2011
Groups St Andrews 2009 was held in the University of Bath in August 2009 and this second volume of a two-volume book contains selected papers from the international conference. Five main lecture courses were given at the conference, and articles based on their lectures form a substantial part of the proceedings. This volume contains the contributions by Eammon O'Brien (Auckland), Mark Sapir (Vanderbilt) and Dan Segal (Oxford). Apart from the main speakers, refereed survey and research articles were contributed by other conference participants. Arranged in alphabetical order, these articles cover a wide spectrum of modern group theory. The regular proceedings of Groups St Andrews conferences have provided snapshots of the state of research in group theory throughout the past 30 years. Earlier volumes have had a major impact on the development of group theory and it is anticipated that this volume will be equally important.
Features
* Contains expository articles by leading mathematicians in group theory
* Forms part of an extensive four-yearly series of such volumes which have shaped the direction of research in group theory
* Provides a snapshot of the state of research in group theory
Introduction C. M. Campbell and E. F. Robertson
1. Algorithms for matrix groups E. A. O'Brien
2. Residual properties of 1-relator groups Mark Sapir
3. Words and groups Dan Segal
4. The modular isomorphism problem for the groups of order 512 Bettina Eick and Alexander Konovalov
5. Recent progress in the symmetric generation of groups Ben Fairbairn
6. Discriminating groups: a comprehensive overview Benjamin Fine, Anthony M. Gaglione, Alexei Myasnikov, Gerhard Rosenberger and Dennis Spellman
7. Extending the Kegel*Wielandt theorem through ƒÎ-decomposable groups L. S. Kazarin, A. Martinez-Pastor and M. D. Perez-Ramos
8. On the prime graph of a finite group Behrooz Khosravi
9. Applications of Lie rings with finite cyclic grading E. I. Khukhro
10. Pronormal subgroups and transitivity of some subgroup properties Leonid A. Kurdachenko, Javier Otal and Igor Ya. Subbotin
11. On Engel and positive laws O. Macedo*ska and W. Tomaszewski
12. Maximal subgroups of odd index in finite groups with simple classical socle N. V. Maslova
13. Some classic and nearly classic problems on varieties of groups Peter M. Neumann
14. Generalizations of the Sylow theorem Danila O. Revin and Evgeny P. Vdovin
15. Engel groups Gunnar Traustason
16. Lie methods in Engel groups Michael Vaughan-Lee
17. On the degree of commutativity of p-groups of maximal class A. Vera-Lopez and M. A. Garcia-Sanchez
18. Class preserving automorphisms of finite p-groups: a survey Manoj K. Yadav
19. Symmetric colorings of finite groups Yuliya Zelenyuk.