Atnaujinkite slapukų nuostatas

Assignment Problems [Kietas viršelis]

(Naujas leidimas: 9781611972221)
4.67/5 (6 ratings by Goodreads)
, ,
  • Formatas: Hardback, 395 pages, aukštis x plotis x storis: 247x170x23 mm, weight: 870 g, Illustrations
  • Išleidimo metai: 19-Mar-2009
  • Leidėjas: Society for Industrial & Applied Mathematics,U.S.
  • ISBN-10: 0898716632
  • ISBN-13: 9780898716634 (Naujas leidimas: 9781611972221)
Kitos knygos pagal šią temą:
Assignment ProblemsDidesnis paveikslėlis
  • Formatas: Hardback, 395 pages, aukštis x plotis x storis: 247x170x23 mm, weight: 870 g, Illustrations
  • Išleidimo metai: 19-Mar-2009
  • Leidėjas: Society for Industrial & Applied Mathematics,U.S.
  • ISBN-10: 0898716632
  • ISBN-13: 9780898716634 (Naujas leidimas: 9781611972221)
Kitos knygos pagal šią temą:
Pastovi nuoroda: https://www.kriso.lt/db/9780898716634.html
Raktažodžiai:
Assignment Problems is a useful tool for researchers, practitioners, and graduate students. It 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 organised the book into 10 self-contained chapters to make it easy for readers to use the specific chapters 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. Researchers will benefit from the detailed exposition of theory and algorithms related to assignment problems, including the basic linear sum assignment problem and its variations. Practitioners will learn about practical applications of the methods, the performance of exact and heuristic algorithms, and software options. This book also can serve as a text for advanced courses in discrete mathematics, integer programming, combinatorial optimization, and algorithmic computer science.
List of Figures
xiii
List of Tables
xv
List of Algorithms
xvii
Preface xix
Introduction
1(12)
Assignments
1(3)
Linear assignment problems
4(3)
Quadratic assignment problems
7(1)
Multi-index assignment problems
8(3)
Research lines for assignment problems
11(2)
Theoretical foundations
13(22)
The marriage theorem and the existence of perfect matchings
13(11)
The assignment polytope
24(11)
Bipartite matching algorithms
35(38)
Bipartite matching
35(1)
A labeling method for finding a maximum cardinality matching
36(6)
The Hopcroft-Karp algorithm
42(5)
Improvements by Alt, Blum, Mehlhorn, and Paul
47(5)
Matchings in convex bipartite graphs
52(5)
Algorithms
53(2)
Applications
55(2)
Maximum matchings and matrix algorithms
57(2)
Perfect matchings in bipartite random graphs
59(5)
Applications of maximum matching problems
64(9)
Vehicle scheduling problems
65(1)
Time slot assignment problem
66(7)
Linear sum assignment problem
73(72)
Introduction
73(6)
Mathematical model
74(1)
Complementary slackness
75(2)
Historical notes, books, and surveys
77(2)
Primal-dual algorithms
79(10)
The Hungarian algorithm
79(6)
An O(n3) implementation of the Hungarian algorithm
85(2)
Cost-scaling algorithms
87(2)
The Dinic---Kronrod algorithm
89(4)
Shortest path implementation of the Hungarian algorithm
93(11)
Transformation to a minimum cost flow problem
93(1)
Basic implementation
94(4)
Efficient implementations
98(1)
Preprocessing
99(5)
Primal algorithms
104(8)
Non-simplex algorithms
104(2)
Simplex-based algorithms
106(6)
Dual algorithms
112(14)
Non-simplex algorithms
112(2)
Simplex-based algorithms
114(5)
Auction algorithms
119(4)
Pseudoflow algorithms
123(3)
Other algorithms
126(1)
Summary of sequential algorithms
127(1)
Software
127(4)
Computer codes
129(2)
Experimental analysis
131(7)
Classes of instances
132(1)
Experiments
133(5)
Parallel algorithms
138(7)
Theoretical results
138(1)
Auction algorithms
139(2)
Shortest path algorithms
141(1)
Primal simplex algorithms
142(3)
Further results on the linear sum assignment problem
145(26)
Asymptotic analysis
145(5)
Expected optimum value
145(4)
Asymptotic analysis of algorithms
149(1)
Monge matrices and the linear sum assignment problem
150(3)
Max-algebra and the linear sum assignment problem
153(5)
Variants
158(7)
Ranking solutions
158(5)
k-cardinality assignment problem
163(1)
Semi-assignment problem
164(1)
Rectangular cost matrix
165(1)
Applications
165(6)
Mean flow time minimization on parallel machines
166(1)
Categorized assignment scheduling
167(1)
Optimal depletion of inventory
167(1)
Personnel assignment with seniority and job priority
168(1)
Navy personnel planning
168(3)
Other types of linear assignment problems
171(32)
Introduction
171(1)
Bottleneck assignment problem
172(19)
Background
172(2)
Threshold algorithms
174(3)
A dual method
177(1)
Augmenting path methods
178(7)
Sparse subgraph techniques
185(1)
Special cases
186(1)
Asymptotic results
187(1)
Variants and applications
188(3)
Software
191(1)
Algebraic assignment problem
191(4)
Sum-k assignment problem
195(1)
Balanced assignment problem
195(3)
Lexicographic bottleneck assignment problem
198(5)
Quadratic assignment problems: Formulations and bounds
203(46)
Introduction
203(8)
Models and applications
203(3)
Traveling salesman problem
206(1)
Minimum weight feedback are set problem
206(1)
Graph partitioning and maximum clique problem
207(2)
Graph isomorphism and graph packing problems
209(1)
Quadratic bottleneck assignment problem
210(1)
Complexity issues
210(1)
Formulations
211(6)
Trace formulation
212(1)
Kronecker product formulation
213(1)
Convex and concave integer models
214(2)
Mean objective value of feasible solutions
216(1)
Linearizations
217(8)
Kaufman---Broeckx
218(1)
Balas---Mazzola
219(2)
Frieze---Yadegar
221(1)
Adams---Johnson
221(1)
Higher level linearizations
222(3)
Quadratic assignment polytopes
225(1)
Gilmore---Lawler bound
225(8)
Reduction methods
229(4)
Admissible transformations and other bounds
233(5)
Admissible transformations
233(2)
General Gilmore---Lawler bound
235(3)
Eigenvalue bounds
238(7)
Symmetric Koopmans---Beckmann problems
238(6)
Nonsymmetric Koopmans---Beckmann problems
244(1)
Bounds by semidefinite programming
245(2)
Bounds by convex quadratic programming
247(2)
Quadratic assignment problems: Algorithms
249(32)
Exact algorithms
249(6)
Benders' decomposition
249(1)
Branch-and-bound
250(3)
Branch-and-cut
253(1)
Parallel and massively parallel algorithms
253(2)
Heuristics
255(11)
Construction algorithms
255(1)
Limited exact algorithms
255(2)
Basic elements of metaheuristic methods
257(2)
Simulated annealing
259(1)
Tabu search
260(1)
Genetic algorithms
261(1)
Greedy randomized adaptive search procedure
262(1)
Ant colony optimization
263(1)
Scatter search and path relinking
264(1)
Large scale and variable neighborhood search
265(1)
Computer codes
266(1)
Easy and hard special cases
267(14)
Sum and product matrices
267(8)
Diagonally structured matrices
275(4)
Ordered matrices
279(1)
Problems generated by a special underlying graph
279(2)
Other types of quadratic assignment problems
281(24)
Quadratic bottleneck assignment problem
281(4)
Gilmore---Lawler bound for the Koopmans---Beckmann form
282(2)
Gilmore---Lawler bound for the general form
284(1)
Asymptotic results
285(6)
Generic combinatorial optimization problem
285(5)
Quadratic assignment problem
290(1)
Quadratic bottleneck assignment problem
291(1)
Cubic and quartic assignment problem
291(2)
Quadratic semi-assignment problem
293(12)
Applications
295(5)
Solution methods
300(5)
Multi-index assignment problems
305(14)
Introduction
305(1)
Axial 3-index assignment problem
305(7)
Applications
307(1)
Polyhedral aspects
307(1)
Complexity and approximation
308(1)
Lower bounds and exact solution methods
308(2)
Heuristic algorithms
310(1)
Special cases
310(1)
Asymptotic behavior
311(1)
Planar 3-index assignment problem
312(3)
Applications and special cases
313(1)
Polyhedral aspects, lower bounds, and algorithms
314(1)
General multi-index assignment problems
315(4)
Applications
317(1)
Algorithms and asymptotic behavior
317(2)
Bibliography 319(78)
Author Index 397
Index 377
Rainer Burkard is a Professor of Mathematics at Graz University of Technology, Austria. He has published several books and over 150 papers on discrete optimization and related areas, and he serves as an editor for numerous journals in discrete applied mathematics. His main research focus is combinatorial optimization 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 optimization 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 (Wiley, 1990) and Editor-in-Chief of 4OR: A Quarterly Journal of Operations Research. His research focus is the design of algorithms for combinatorial optimization and graph theory problems and their application in packing, routing, and scheduling.