Table of contents (shortened):

PART I. - Advanced methods in combinatorial optimization

1. Linear and integer programming (Motivation: optimum assignment. The basic LP problem. Solvability. Duality. Integer programming. Total unimodularity. The simplex method.)
2. Matroids (Basic concepts. Dual, minors. Matrices and matroids. Union and intersection of matroids. Matroid matching. Algebraic representability. Characterization of matroidal properties.)
3. Approximation algorithms (Small additive error. Small multiplicative error, set covering, Steiner-trees, the travelling salesman problem. The Euclidean TSP problem, constructions, improvements.)
4. Scheduling algorithms (Basic concepts and problem types. Single machine scheduling. Scheduling parallel machines, list scheduling for P║C_max, the P│prec│C_max problem. Two solved cases. Bin packing.

PART II. - Engineering case studies

5. Reliable network design (Reliability of telecommunication networks. Connectivity of graphs, its computation. Multiply connected subgraphs, minimum cost directed rooted trees, minimum size 2-connected subgraphs, connectivity augmentation. Disjoint arborescences and spanning trees, highly connected orientations.)
6. VLSI routing (Mathematical model of the detailed routing problem. The algorithm of Gallai (also called left-edge-algorithm) and its applications, single row routing in 1 or 2 layers, channel routing on k layers, graph theoretic aspects. Channel routing on few layers in the Manhattan and in the unconstrained model. Switchbox routing. Edge-disjoint routing.)
7. Electric network theory (Resistor networks. Kirchhoff's topological formulae. Generalizations for 1-port networks. Generalizations for multiport networks (ideal transformers, gyrators, general linear multiports). Duality. Algorithmic aspects.)
8. Statics of bar-and-joints frameworks (Rigidity matrix, real and infinitesimal motions. Calculation of the stresses, Maxwell-Cremona diagrams. Generic rigidity, theorems of Laman, Lovász and Yemini. Pin-down structures. 3-dimensional frameworks. Square grids with diagonals. Cubic grids with diagonals. Tensegrity frameworks.)

The topics of the first four chapters are each covered by many thick volumes in several languages. The novelty of this book is that here we only give the necessary minimum for engineers and in the later chapters the applicability of these advanced mathematical tools is illustrated by detailed case studies in electrical engineering, in design of telecommunication networks or VLSI chips and in structural topology for civil engineers.

This text is used since 2002 for the graduate class "System optimization" for informatics majors at the Budapest University of Technology and Economics. Its content is covered in one semester (14 weeks) with four lectures per week.

The English version will also contain some 50 exercises from past exams and full solutions of the odd numbered exercises.