Muutke küpsiste eelistusi

Assignment Problems Second Revised Edition [Kõva köide]

4.67/5 (3 hinnangut Goodreads-ist)
, ,
  • Formaat: Hardback, 415 pages, kõrgus x laius x paksus: 229x152x23 mm, kaal: 896 g, illustrations
  • Ilmumisaeg: 30-Mar-2012
  • Kirjastus: Society for Industrial & Applied Mathematics,U.S.
  • ISBN-10: 1611972221
  • ISBN-13: 9781611972221
Teised raamatud teemal:
Assignment Problems Second Revised EditionSuurem pilt
  • Formaat: Hardback, 415 pages, kõrgus x laius x paksus: 229x152x23 mm, kaal: 896 g, illustrations
  • Ilmumisaeg: 30-Mar-2012
  • Kirjastus: Society for Industrial & Applied Mathematics,U.S.
  • ISBN-10: 1611972221
  • ISBN-13: 9781611972221
Teised raamatud teemal:
Püsilink: https://www.kriso.ee/db/9781611972221.html
Märksõnad:
Provides a comprehensive treatment of assignment problems from their conceptual beginnings in the 1920s through present-day theoretical, algorithmic, and practical developments. The authors have organized the book into 10 self-contained chapters to make it easy for readers to use the specific chapters of interest to them without having to read the book linearly.

The topics covered include bipartite matching algorithms, linear assignment problems, quadratic assignment problems, multi-index assignment problems, and many variations of these problems.

Exercises in the form of numerical examples provide readers with a method of self-study or students with homework problems, and an associated webpage offers applets that readers can use to execute some of the basic algorithms as well as links to computer codes that are available online.
List of Figures
xiii
List of Tables
xv
List of Algorithms
xvii
Foreword to the Revised Reprint xix
Preface xxi
1 Introduction
1(12)
1.1 Assignments
1(3)
1.2 Linear assignment problems
4(3)
1.3 Quadratic assignment problems
7(1)
1.4 Multi-index assignment problems
8(3)
1.5 Research lines for assignment problems
11(2)
2 Theoretical foundations
13(22)
2.1 The marriage theorem and the existence of perfect matchings
13(11)
2.2 The assignment polytope
24(11)
3 Bipartite matching algorithms
35(38)
3.1 Bipartite matching
35(1)
3.2 A labeling method for finding a maximum cardinality matching
36(6)
3.3 The Hopcroft-Karp algorithm
42(5)
3.4 Improvements by Alt, Blum, Mehlhorn, and Paul
47(5)
3.5 Matchings in convex bipartite graphs
52(5)
3.5.1 Algorithms
53(2)
3.5.2 Applications
55(2)
3.6 Maximum matchings and matrix algorithms
57(2)
3.7 Perfect matchings in bipartite random graphs
59(6)
3.8 Applications of maximum matching problems
65(8)
3.8.1 Vehicle scheduling problems
65(1)
3.8.2 Time slot assignment problem
66(7)
4 Linear sum assignment problem
73(72)
4.1 Introduction
73(6)
4.1.1 Mathematical model
74(1)
4.1.2 Complementary slackness
75(2)
4.1.3 Historical notes, books, and surveys
77(2)
4.2 Primal-dual algorithms
79(10)
4.2.1 The Hungarian algorithm
79(6)
4.2.2 An O(n3) implementation of the Hungarian algorithm
85(2)
4.2.3 Cost-scaling algorithms
87(2)
4.3 The Dinic-Kronrod algorithm
89(4)
4.4 Shortest path implementation of the Hungarian algorithm
93(11)
4.4.1 Transformation to a minimum cost flow problem
94(1)
4.4.2 Basic implementation
95(3)
4.4.3 Efficient implementations
98(1)
4.4.4 Preprocessing
99(5)
4.5 Primal algorithms
104(8)
4.5.1 Non-simplex algorithms
104(2)
4.5.2 Simplex-based algorithms
106(6)
4.6 Dual algorithms
112(14)
4.6.1 Non-simplex algorithms
112(2)
4.6.2 Simplex-based algorithms
114(5)
4.6.3 Auction algorithms
119(4)
4.6.4 Pseudoflow algorithms
123(3)
4.7 Other algorithms
126(1)
4.8 Summary of sequential algorithms
127(1)
4.9 Software
127(5)
4.9.1 Computer codes
129(3)
4.10 Experimental analysis
132(6)
4.10.1 Classes of instances
132(1)
4.10.2 Experiments
133(5)
4.11 Parallel algorithms
138(7)
4.11.1 Theoretical results
139(1)
4.11.2 Auction algorithms
140(1)
4.11.3 Shortest path algorithms
141(2)
4.11.4 Primal simplex algorithms
143(2)
5 Further results on the linear sum assignment problem
145(26)
5.1 Asymptotic analysis
145(5)
5.1.1 Expected optimum value
145(4)
5.1.2 Asymptotic analysis of algorithms
149(1)
5.2 Monge matrices and the linear sum assignment problem
150(3)
5.3 Max-algebra and the linear sum assignment problem
153(5)
5.4 Variants
158(7)
5.4.1 Ranking solutions
158(5)
5.4.2 k-cardinality assignment problem
163(1)
5.4.3 Semi-assignment problem
164(1)
5.4.4 Rectangular cost matrix
165(1)
5.5 Applications
165(6)
5.5.1 Mean flow time minimization on parallel machines
166(1)
5.5.2 Categorized assignment scheduling
167(1)
5.5.3 Optimal depletion of inventory
168(1)
5.5.4 Personnel assignment with seniority and job priority
168(1)
5.5.5 Navy personnel planning
168(3)
6 Other types of linear assignment problems
171(34)
6.1 Introduction
171(1)
6.2 Bottleneck assignment problem
172(19)
6.2.1 Background
172(2)
6.2.2 Threshold algorithms
174(3)
6.2.3 A dual method
177(1)
6.2.4 Augmenting path methods
178(7)
6.2.5 Sparse subgraph techniques
185(1)
6.2.6 Special cases
186(1)
6.2.7 Asymptotic results
187(1)
6.2.8 Variants and applications
188(3)
6.2.9 Software
191(1)
6.3 Algebraic assignment problem
191(4)
6.4 Sum-k assignment problem
195(1)
6.5 Balanced assignment problem
195(3)
6.6 Lexicographic bottleneck assignment problem
198(4)
6.7 Inverse assignment problems
202(3)
7 Quadratic assignment problems: Formulations and bounds
205(48)
7.1 Introduction
205(8)
7.1.1 Models and applications
205(3)
7.1.2 Traveling salesman problem
208(1)
7.1.3 Minimum weight feedback arc set problem
208(1)
7.1.4 Graph partitioning and maximum clique problem
209(2)
7.1.5 Graph isomorphism and graph packing problems
211(1)
7.1.6 Quadratic bottleneck assignment problem
212(1)
7.1.7 Complexity issues
212(1)
7.2 Formulations
213(6)
7.2.1 Trace formulation
214(1)
7.2.2 Kronecker product formulation
215(1)
7.2.3 Convex and concave integer models
216(2)
7.2.4 Mean objective value of feasible solutions
218(1)
7.3 Linearizations
219(6)
7.3.1 Kaufman-Broeckx
220(1)
7.3.2 Balas-Mazzola
221(2)
7.3.3 Frieze-Yadegar
223(1)
7.3.4 Adams-Johnson
223(1)
7.3.5 Higher level linearizations
224(1)
7.4 Quadratic assignment polytopes
225(2)
7.5 Gilmore-Lawler bound and reduction methods
227(8)
7.5.1 Gilmore-Lawler bound
227(5)
7.5.2 Reduction methods
232(3)
7.6 Admissible transformations and other bounds
235(6)
7.6.1 Admissible transformations
236(1)
7.6.2 General Gilmore-Lawler bound
237(4)
7.7 Eigenvalue bounds
241(7)
7.7.1 Symmetric Koopmans-Beckmann problems
241(5)
7.7.2 Nonsymmetric Koopmans-Beckmann problems
246(2)
7.8 Bounds by semidefinite programming
248(3)
7.9 Bounds by convex quadratic programming
251(2)
8 Quadratic assignment problems: Algorithms
253(34)
8.1 Exact algorithms
253(7)
8.1.1 Benders' decomposition
253(1)
8.1.2 Branch-and-bound
254(3)
8.1.3 Branch-and-cut
257(1)
8.1.4 Parallel and massively parallel algorithms
258(2)
8.2 Heuristics
260(11)
8.2.1 Construction algorithms
260(1)
8.2.2 Limited exact algorithms
260(2)
8.2.3 Basic elements of metaheuristic methods
262(2)
8.2.4 Simulated annealing
264(1)
8.2.5 Tabu search
265(1)
8.2.6 Genetic algorithms
266(1)
8.2.7 Greedy randomized adaptive search procedure
267(1)
8.2.8 Ant colony optimization
268(1)
8.2.9 Scatter search and path relinking
269(1)
8.2.10 Large scale and variable neighborhood search
270(1)
8.3 Computer codes
271(1)
8.4 Easy and hard special cases
272(15)
8.4.1 Sum and product matrices
272(9)
8.4.2 Diagonally structured matrices
281(3)
8.4.3 Ordered matrices
284(1)
8.4.4 Problems generated by a special underlying graph
285(2)
9 Other types of quadratic assignment problems
287(24)
9.1 Quadratic bottleneck assignment problem
287(4)
9.1.1 Gilmore-Lawler bound for the Koopmans-Beckmann form
288(2)
9.1.2 Gilmore-Lawler bound for the general form
290(1)
9.2 Asymptotic results
291(6)
9.2.1 Generic combinatorial optimization problem
291(5)
9.2.2 Quadratic assignment problem
296(1)
9.2.3 Quadratic bottleneck assignment problem
297(1)
9.3 Cubic and quartic assignment problem
297(2)
9.4 Quadratic semi-assignment problem
299(12)
9.4.1 Applications
301(5)
9.4.2 Solution methods
306(5)
10 Multi-index assignment problems
311(16)
10.1 Introduction
311(1)
10.2 Axial 3-index assignment problem
311(7)
10.2.1 Applications
313(1)
10.2.2 Polyhedral aspects
313(1)
10.2.3 Complexity and approximation
314(1)
10.2.4 Lower bounds and exact solution methods
314(2)
10.2.5 Heuristic algorithms
316(1)
10.2.6 Special cases
316(1)
10.2.7 Asymptotic behavior
317(1)
10.3 Planar 3-index assignment problem
318(3)
10.3.1 Applications and special cases
320(1)
10.3.2 Polyhedral aspects, lower bounds, and algorithms
320(1)
10.4 General multi-index assignment problems
321(6)
10.4.1 Applications
323(1)
10.4.2 Algorithms and asymptotic behavior
324(3)
Bibliography 327(51)
Author Index 378(10)
Index 388
Rainer Burkard is Professor Emeritus of Mathematics at Graz University of Technology, Austria. He has published several books and over 150 papers on discrete optimisation and related areas. His main research focus is combinatorial optimisation and its applications. Mauro Dell'Amico is a Professor of Operations Research at the University of Modena and Reggio Emilia, Italy. His research interests are combinatorial optimisation as applied to transportation, telecommunications, routing and scheduling. Silvano Martello is a Professor of Operations Research at the University of Bologna, Italy. He is author of Knapsack Problems: Algorithms and Computer Implementations (1990) and Editor-in-Chief of 4OR: A Quarterly Journal of Operations Research. His research focus is the design of algorithms for combinatorial optimisation and graph theory problems and their application in packing, routing and scheduling.