**Table of Contents**

- Introduction
- 24. The Branch and Bound Method
- 24.1. 24.1 An example: the Knapsack Problem
- 24.2. 24.2 The general frame of the B&B method
- 24.3. 24.3 Mixed integer programming with bounded variables
- 24.3.1. 24.3.1 The geometric analysis of a numerical example
- 24.3.2. 24.3.2 The linear programming background of the method
- 24.3.3. 24.3.3 Fast bounds on lower and upper branches
- 24.3.4. 24.3.4 Branching strategies
- 24.3.5. 24.3.5 The selection of the branching variable
- 24.3.6. 24.3.6 The numerical example is revisited

- 24.4. 24.4 On the enumeration tree
- 24.5. 24.5 The use of information obtained from other sources
- 24.6. 24.6 Branch and Cut
- 24.7. 24.7 Branch and Price

- 25. Comparison Based Ranking
- 25.1. 25.1 Introduction to supertournaments
- 25.2. 25.2 Introduction to -tournaments
- 25.3. 25.3 Existence of -tournaments with prescribed score sequence
- 25.4. 25.4 Existence of an -tournament with prescribed score sequence
- 25.5. 25.5 Existence of an -tournament with prescribed score sequence
- 25.5.1. 25.5.1 Existence of a tournament with arbitrary degree sequence
- 25.5.2. 25.5.2 Description of a naive reconstructing algorithm
- 25.5.3. 25.5.3 Computation of
- 25.5.4. 25.5.4 Description of a construction algorithm
- 25.5.5. 25.5.5 Computation of and
- 25.5.6. 25.5.6 Description of a testing algorithm
- 25.5.7. 25.5.7 Description of an algorithm computing and
- 25.5.8. 25.5.8 Computing of and in linear time
- 25.5.9. 25.5.9 Tournament with and
- 25.5.10. 25.5.10 Description of the score slicing algorithm
- 25.5.11. 25.5.11 Analysis of the minimax reconstruction algorithm

- 25.6. 25.6 Imbalances in -tournaments
- 25.7. 25.7 Supertournaments
- 25.8. 25.8 Football tournaments
- 25.9. 25.9 Reconstruction of the tested sequences

- 26. Complexity of Words
- 27. Conflict Situations
- 28. General Purpose Computing on Graphics Processing Units
- 29. Perfect Arrays
- 29.1. 29.1 Basic concepts
- 29.2. 29.2 Necessary condition and earlier results
- 29.3. 29.3 One-dimensional perfect arrays
- 29.4. 29.4 Two-dimensional perfect arrays
- 29.5. 29.5 Three-dimensional perfect arrays
- 29.6. 29.6 Construction of growing arrays using colouring
- 29.7. 29.7 The existence theorem of perfect arrays
- 29.8. 29.8 Superperfect arrays
- 29.9. 29.9 -complexity of one-dimensional arrays
- 29.9.1. 29.9.1 Definitions
- 29.9.2. 29.9.2 Bounds of complexity measures
- 29.9.3. 29.9.3 Recurrence relations
- 29.9.4. 29.9.4 Pseudocode of the algorithm
`Quick-Martin`

- 29.9.5. 29.9.5 Pseudocode of algorithm -
`Complexity`

- 29.9.6. 29.9.6 Pseudocode of algorithm
`Super`

- 29.9.7. 29.9.7 Pseudocode of algorithm
`MaxSub`

- 29.9.8. 29.9.8 Construction and complexity of extremal words

- 29.10. 29.10 Finite two-dimensional arrays with maximal complexity

- 30. Score Sets and Kings
- Bibliography

**List of Figures**

- 24.1. The first seven steps of the solution.
- 24.2. The geometry of linear programming relaxation of Problem (24.36) including the feasible region (triangle ), the optimal solution (), and the optimal level of the objective function represented by the line .
- 24.3. The geometry of the course of the solution. The co-ordinates of the points are: O=(0,0), A=(0,3), B=(2.5,1.5), C=(2,1.8), D=(2,1.2), E=(,2), F=(0,2), G=(,1), H=(0,1), I=(1,2.4), and J=(1,2). The feasible regions of the relaxation are as follows. Branch 1: , Branch 2: , Branch 3: empty set, Branch 4: , Branch 5: , Branch 6: , Branch 7: empty set (not on the figure). Point J is the optimal solution.
- 24.4. The course of the solution of Problem (24.36). The upper numbers in the circuits are explained in subsection 24.3.2. They are the corrections of the previous bounds obtained from the first pivoting step of the simplex method. The lower numbers are the (continuous) upper bounds obtained in the branch.
- 24.5. The elements of the dual simplex tableau.
- 25.1. Point matrix of a chess+last trick-bridge tournament with players.
- 25.2. Point matrix of a -tournament with for .
- 25.3. The point table of a -tournament .
- 25.4. The point table of reconstructed by
`Score-Slicing`

- 25.5. The point table of reconstructed by
`Mini-Max`

- 25.6. Number of binomial, head halfing and good sequences, further the ratio of the numbers of good sequences for neighbouring values of .
- 25.7. Sport table belonging to the sequence .
- 26.1. The De Bruijn graph .
- 26.2. The De Bruijn graph .
- 26.3. The De Bruijn tree .
- 26.4. Rauzy graphs for the infinite Fibonacci word.
- 26.5. Rauzy graphs for the power word.
- 26.6. Complexity of several binary words.
- 26.7. Complexity of all 3-length binary words.
- 26.8. Complexity of all 4-length binary words.
- 26.9. Values of , , and .
- 26.10. Frequency of words with given total complexity.
- 26.11. Graph for -subwords when .
- 26.12. -complexity for rainbow words of length 6 and 7.
- 26.13. The -complexity of words of length .
- 26.14. Values of .
- 27.1. Planning of a sewage plant.
- 27.2. The image of set .
- 27.3. The image of set .
- 27.4. Minimizing distance.
- 27.5. Maximizing distance.
- 27.6. The image of the normalized set .
- 27.7. Direction-dependent methods.
- 27.8. The graphical solution of Example 27.6.
- 27.9. The graphical solution of Example 27.7.
- 27.10. Game with no equilibrium.
- 27.11. Group decision-making table.
- 27.12. The database of Example 27.17.
- 27.13. The preference graph of Example 27.17.
- 27.14. Group decision-making table.
- 27.15. Group decision-making table.
- 27.16. The database of Example 27.18.
- 27.17.
- 27.18. Kalai–Smorodinsky solution.
- 27.19. Solution of Example 27.20.
- 27.20. The method of monotonous area.
- 28.1. GPU programming models for shader APIs and for CUDA. We depict here a Shader Model 4 compatible GPU. The programmable stages of the shader API model are red, the fixed-function stages are green.
- 28.2. Incremental image synthesis process.
- 28.3. Blending unit that computes the new pixel color of the frame buffer as a function of its old color (destination) and the new fragment color (source).
- 28.4. GPU as a vector processor.
- 28.5. An example for parallel reduction that sums the elements of the input vector.
- 28.6. Implementation of scatter.
- 28.7. Caustics rendering is a practical use of histogram generation. The illumination intensity of the target will be proportional to the number of photons it receives (images courtesy of Dávid Balambér).
- 28.8. Finite element representations of functions. The texture filtering of the GPU directly supports finite element representations using regularly placed samples in one-, two-, and three-dimensions and interpolating with piece-wise constant and piece-wise linear basis functions.
- 28.9. A time step of the Eulerian solver updates textures encoding the velocity field.
- 28.10. Computation of the simulation steps by updating three-dimensional textures. Advection utilizes the texture filtering hardware. The linear equations of the viscosity damping and projection are solved by Jacobi iteration, where a texel (i.e. voxel) is updated with the weighted sum of its neighbors, making a single Jacobi iteration step equivalent to an image filtering operation.
- 28.11. Flattened 3D velocity (left) and display variable (right) textures of a simulation.
- 28.12. Snapshots from an animation rendered with Eulerian fluid dynamics.
- 28.13. Data structures stored in arrays or textures. One-dimensional float3 arrays store the particles' position and velocity. A one-dimensional float2 texture stores the computed density and pressure. Finally, a two-dimensional texture identifies nearby particles for each particle.
- 28.14. A time step of the Lagrangian solver. The considered particle is the red one, and its neighbors are yellow.
- 28.15. Animations obtained with a Lagrangian solver rendering particles with spheres (upper image) and generating the isosurface (lower image) [ 114 ].
- 29.1. a) A (2,2,4,4)-square; b) Indexing scheme of size
- 29.2. Binary colouring matrix of size
- 29.3. A (4,2,2,16)-square generated by colouring
- 29.4. A (2,2,4,4)-square
- 29.5. Sixteen layers of the -perfect output of
`Shift`

- 29.6. Values of jumping function of rainbow words of length .
- 30.1. A round-robin competition involving 4 players.
- 30.2. A tournament with score set .
- 30.3. Out-degree matrix of the tournament represented in Figure 30.2.
- 30.4. Construction of tournament with odd number of distinct scores.
- 30.5. Construction of tournament with even number of distinct scores.
- 30.6. Out-degree matrix of the tournament .
- 30.7. Out-degree matrix of the tournament .
- 30.8. Out-degree matrix of the tournament .
- 30.9. An oriented graph with score sequence and score set .
- 30.10. A tournament with three kings and three serfs . Note that is neither a king nor a serf and are both kings and serfs.
- 30.11. A tournament with three kings and two strong kings
- 30.12. Construction of an -tournament with even .
- 30.13. Six vertices and six weak kings.
- 30.14. Six vertices and five weak kings.
- 30.15. Six vertices and four weak kings.
- 30.16. Six vertices and three weak kings.
- 30.17. Six vertices and two weak kings.
- 30.18. Vertex of maximum score is not a king.
- 30.19. Construction of an -oriented graph.