|
|
 |
| Авторизация |
|
|
|
| Поиск по указателям |
|
|
|
|
|
|
|
 |
|
|
|
| Papadimitriou C.H., Steiglitz K. — Combinatorial Optimization: Algorithms and Complexity |
|
|
|
| Предметный указатель |
 -change neighborhood 463
TSP see “Triangle inequality TSP”
 -approximate algorithm 409
-approximate solution 409 483
0—1 KNAPSACK 374—75 419
0—1 linear program (or ZOLP) 315 323
1-tree 441
2-change neighborhood 7—8 455
3-DIMENSIONAL MATCHING 371—73
3-EXACT COVER 374 391
3-Satisfiability 359
ACCEPT 354
Addressing 355
Adjacency lists 160
Adjacency neighborhood 62 475
Adjacent basic feasible solutions 61 169
adjacent nodes 21
Adjacent vertices of a polytope 61 473
Admissible column (or variable) 106 144 257
Admissible edge 257
Admissible graph 258
Admissible odd set 257
Affinc subspace 34
Affinc transformation 174
Aho, A.V. 24 136 190 382
Algorithm 1—2 156—57 347—48
Algorithm buildup 141—43
Algorithm cycle 138—40
Algorithm, -approximate 409
Algorithm, alphabeta 143—48 249
Algorithm, approximation 401 406—30
Algorithm, Bland's 53—55
Algorithm, certificate-checking 349 354—55 378
Algorithm, Christofides' 416
Algorithm, cutting plane 326—39
Algorithm, Dijkstra's 113 128—29 133 250
Algorithm, ellipsoid 2 153 170—85
Algorithm, exponential 164 343 401
Algorithm, Floyd-Warshall 129—33
Algorithm, fractional-dual 330
Algorithm, greedy 278—80 282 285
Algorithm, heuristic 401
Algorithm, Hungarian 144 248—55 267
Algorithm, labeling 120—28 162—63 200—202
Algorithm, out-of-kilter 153
Algorithm, polynomial-time 163—66 347
Algorithm, primal-dual 104—15 138 141 144—48 150 256 299
Algorithm, primal-integer 339
Algorithm, probabilistic 401
Algorithm, pseudopolynomial 165 387—91
Algorithm, recursive 187
Algorithm, revised simplex 88—97
Algorithm, simplex 2 26—66 49 163 166—70
Algorithm, two-phase 55—58
All-variable gradient pivoting rule 51
Alphabeta algorithm 143—48 249
Alternating path 219 292
Alternating sequence 292
Alternating sequence, proper 294
Analog computer 134
Analysis of Algorithms 162—63
AND 314
Antibranching 402
Aoki, M. 18
Approximation algorithm 401 406—30
Approximation scheme 419—27
ARC 20
Arc, backward 121 203
Arc, forward 121 203
Arc-chain incidence matrix 92
Arithmetic operation 158 162
Arithmetic precision 182—85 339
Artificial variable 55 106
Aspvall, B. 191
Assignment problem 154 248—55 439
assignment statement 24
ASYMMETRIC TSP 392
Augmenting (or augmentation) path 114 121 219 291
Augmenting capacity 203
Augmenting sequence 293
Augmenting sequence, proper 294
Auxiliary digraph 200 223 295
Auxiliary network 205
b-matching 245 268
Backward arc 121 203
Bagchi, A. 485
Barr, R.S. 154
Basic column 29
Basic feasible solution (or bfs) 29—33 39—40 42—46 61—62
Basic feasible solution (or bfs), degenerate 41 44
Basic solution 29
Basic variable 29
Basis of a blossom 230
Basis of a matrix 29
Basis of a matroid 286
Bazaraa, M.S. 65 136
Beale, E.M.L. 66 103 105
Begin statement 25
Bellman, R.E. 453
Berge, C 216 245 305
BFS see “Basic feasible solution”
Biconnected graph 214
Bidirected flow 244
Bidirected graph 244
Bidirected network 244
Bin packing 245
Binary search 171 172 346
Bipartite graph 21
Bipartite matching problem 221—26 248—55
Bland's anticycling algorithm 53—55
Bland, R.G. 53 66
Blattner, W.O. 381
Blossom 226—34
Blum, M. 306
Bock, F. 455 484
Boolean formula 314
Boolean variable 314
Borosh, I. 325
Boruvka, O. 305
Bottleneck 215
Bottleneck matching problem 245
Bound 438
Bound (or capacity) of an arc 23
Branch 401 436 438
Branch-and-bound algorithm 401 433—48
Branching 290
Browne, M.W. 380
Buildup (algorithm) 141—43
Busacker, R.G. 152
Camion, P. 325
Capacitated spanning tree 152
Capacity of a cut 118
Capacity of a node 134 215
Capacity of an arc 23
Capacity of an arc, augmenting 203
CARRY matrix 88
Caterer problem 151—52
Certificate 348
Certificate-checking algorithm 349 354—55 378
Chain 92
Chandy, M.K. 155
Cheriton, D. 305
Cherkaski, B.V. 216
Chinese postman problem 268
Chinese postman problem, directed 268
Chinese postman problem, mixed 379
Chordal graph 403
Christofidcs' algorithm 416
Christofidcs, N. 416 432
Chvatal, V. 87
| Circuit (or cycle) 21
Circuit (or cycle), directed 21
Circuit of a matroid 286
Circular search 470
Circulation 138 151
Clause 314
CLIQUE 344
Closure 411
Closure, transitive 403
Co-NP 383—86
Cobham, A. 190 380
Coffman, E.G.Jr. 324 431 452
Combinatorial optimization problem 2 3—6 343—47
Combinatorial optimization problem, instance of 4 344
Combinatorialize (the cost or the right-hand side) 113 138 141 147
Comment statement 25
Complement 384
Complementary slackness 71—73
Complete (or perfect) matching 219 267
compound statement 25
Computer 156 158 162 347—48
Computer, analog 134
Concave function 13
Conditional statement 24
Cone 73
Conjunction 313
Conjunctive normal form 315
Connected component 214 276
Connected graph 22 196
Connected graph, strongly 214
Connectivity 215
Connectivity matrix 457
Constraint 26
Convex combination 10
Convex function 10—13
Convex hull 37
Convex polytope 34—42 59—62 472
Convex program 13—16
Convex programming problem 1 13—16
Convex set 10—13
Conway, R.W. 445 453
Cook, S.A. 355 381
Cooper, L. 65
Cost function 4 343
Coupling equation 99
Crapo, H.H. 306
Croes, G.A. 455 484
cube 166
Current graph 260
Cut 118 379
Cut (or cutting plane) 328
Cut (or cutting plane), Gomory 328
Cutting plane algorithm 326—29
CYCLE 21
Cycle (algorithm) 138—40
Cycling in simplex 51—55 63 124—28
d-dimensional cube 166
d-hypercube 166
Dakin, R.J. 437 452
Dantzig, G.B. 2 65 66 103 116 191 324 325 341 381
Dantzig-Wolfe decomposition 97—102 152
Dead node 436
Deadline 310 363
Decidable problem 157
Decomposition see “Dantzig-Wolfe decomposition”
Deficiency 458
Degenerate basic feasible solution 41 44
Degree 21
Dependent set 286
Diameter of a graph 482
diamond 478
Diet problem 27 71
Digraph 20
Digraph, auxiliary 200 273 295
Digraph, strongly connected 214
Dijkstra's algorithm 113 128—29 133 250
Dijkstra, E.W. 116 305
Dimension of a subspace 34
Dinits, E.A. 216
Directed circuit 21
Directed graph see “Digraph”
DIRECTED HAMILTON CIRCUIT 391 404
Directed path 21
Dirichlet cell 302
Dirichlet neighbor 302
Discrete linear subset (or DLS) problem 472
Distance matrix 4—5 410—11
Distance matrix, Euclidean 411
DLS see “Discrete linear subset problem”
Dominance relation 442
Dominate 443
Dorfman, Y.G. 405
Double star 268
Dreyfus, S.E. 453
Drive out a variable 56
DRP see “Dual of the restricted primal”
Dual matroid 305
Dual of a linear program 69
Dual of the restricted primal (or DRP) 105 107
Dual simplex algorithm 80—85
Duality 67—85
Dunham, B. 484
Dynamic programming 419 448—51
Eastman, W.L. 439 452
EDGE 20
Edge cover 243
Edge cover, minimum cost 268
Edge of a polytope 36 61—62
Edge, admissible 257
Edge, free 219
Edge, incident 21
Edge, matched 219
Edmonds, J. 126 135 153 190 216 246 256. 299 306 381
Egervary, J. 154
Elementary row operation 45
Elgot, C.C. 190
Ellipsoid 174
Ellipsoid algorithm 2 153 170—85
Embedded tour 413
Euclidean Distance Matrix 411
EUCLIDEAN TSP 379 411
Euler, L. 412 432
Eulerian multigraph 412
Eulerian spanning graph 413
Eulerian walk 412
Evaluation version of a combinatorial optimization problem 345
Even, S. 192 217 246 405
Exact neighborhood 10 62—63 471—81
Exact neighborhood, minimal 475
Exponential algorithm 164 343 401
Exposed node 219
Face 36
Facet 36
FALSE 314
Farkas' Lemma 73 85 86 319
Farkas, J. 73 87
Favorable X-change 460
Feasible solution 4 343
Feasible solution, basic 29—33 39—40 42—46 61—62
Feature denial 471
Feedback arc set 378
FEEDBACK Vertex Set 378
Fiacco, A.V. 17
Finiteness of the fractional-dual algorithm 337—39
Finiteness of the labeling algorithm 124—28
Flow see also “Max-flow problem”
Flow, bidirected 244
Flow, maximal 206
Flow, maximum (or max-) 23
Flow, min-cost 137—51
|
|
|
| Реклама |
|
|
|
|
|
О проекте