|
|
 |
| Авторизация |
|
|
|
| Поиск по указателям |
|
|
|
|
|
|
|
 |
|
|
|
| Papadimitriou C.H., Steiglitz K. — Combinatorial Optimization: Algorithms and Complexity |
|
|
|
| Предметный указатель |
NP-complete problem 2 342—401 353
NP-complete problem, strongly 378—81 430
NP-hard problem 397—98
Off-shore natural gas pipeline system 462—65
OPTIMIZATION 0—1 KNAPSACK 421
Optimization problem 1 3—6 343—47 472
Optimization version of a combinatorial optimization problem 345
OR 314
Orchard-Hayes, W. 103
Orden, A. 341
Orlova, G.I. 405
Out-of-kilter algorithm 153
Outdegree 21
Outer node 219 260
p-quantile 301
Padberg, M.W. 325
Papadimitriou, C.H. 155 192 246 270 325 382 405 406 485 486
Parsimonious transformation 402
Partition 375 397 431
Partition matroid 288
Path 21
Path, alternating 219 292
Path, augmenting (or augmentation) 114 121 219 291
Path, directed 21
Perfect (or complete) matching 219 267
Permutation schedule 445 470
Pidgin algol 24—25
Pivot 44
Pivoting rule, all-variable gradient 51
Pivoting rule, Bland's rule 53—55 85 90
Pivoting rule, greatest increment 50—51
Pivoting rule, nonbasic gradient 50—51
PLANAR CLIQUE 393 402
Planar graph 302
Polynomial-time algorithm 163—66 347
Polynomial-time approximation scheme (or PTAS) 419—27
Polynomial-time approximation scheme (or PTAS), fully 426 430
Polynomial-time transformation 151 352
Polynomialrtime reduction 351—53 395—97
Polytope (or convex polytope) 34—42 59—62 472
Positive-definitive matrix 174 379
Post's correspondence problem 185 187
Post, E.L. 190
Pratt, V.R. 306 404
Precedence relation 310 363
PRECISION 182—85 339
Prim, R.C. 305
Primal integer algorithm 339
Primal linear program 69
Primal linear program, restricted 105 106
Primal-dual algorithm 104—15 138 141 144—48 150 256
PRIMES 402
Principal of optimality 448
Probabilistic algorithm 401
Problem, combinatorial optimization 1 3—6 343—47 472
Problem, decidable 157
Problem, master 99
Problem, NP-complete 2 342—401 353 378—81 430
Problem, NP-hard 397—98
Problem, optimization 1 3—6 343—47 472
Problem, PSPACE-complete 400
Problem, recognition 347
Problem, undecidable 157
Processing time 310
Processor 243 310
Proper alternating sequence 294
PS PACE 399
Pseudonode 260
Pseudopolynomial algorithm 165 387—91 402
PSPACE-complete problem 400
PTAS see “Polynomial-time approximation scheme”
Pull 207
push 207 209—10
Quadratic programming 379
Quandt, R.E. 51 66
QUEUE 196
R (real number line) 19
Rabin, M.O. 246
Rank of a matrix 288
Rank of a matroid 286 296
Rao, M.R. 381
Rate of growth 159
Recognition problem 347
Recognition version of a combinatorial optimization problem 345
Recursion 187
Recursive algorithm 187
Reduce 351
Reduction 148 225 244 266 298 see
Reduction (in local search) 471
Reduction, polynomial-time 351—53
Reid, J.K. 51 66
Reinversion 91
Reiter, S. 456
Reject 355
Relative cost 47
Relaxation 327
Resource 310
RESTRICTED HAMILTON CIRCUIT 477
Restricted primal (or RP) 105 106
Revised simplex algorithm 88—97
Rinooy Kan, A.H.G. 381
Rivest, R.L. 306
Robinson, A. 190
Rockafellar, R.T. 66 485
Rosenbaum, D.M. 484
Rosenkrantz, D.J. 432
Rota, G-C 306
Rotation 175
Rothfarb, B. 484
RP see “Restricted primal”
s-t connectivity 215
Sadri, F. 82 85
Sahni, S. 432
Salkin, H.M. 341
Satisfiability 314 347 350 356—58 377 394 400
Savage, S.L. 485
Scaling method 153
Scarf, H.E. 341
Scheduling 310—12 363
Scheduling, flowshop 444—48 470
Scheduling, multiprocessor 363—66 393 402 431
Scheduling, two-processor 243
Schrage, L. 446 452
Schrijver, A. 192
Search, binary 171 172 346
Search, local 401 454—81
Search, of a digraph 197
Search, of a graph 194—200
Semiellipsoid 178
Sequence, alternating 292
Sequence, augmenting 293
Sequence, proper 294
Sethi, R. 445 453
SFTP see “Sum-finishing-time problem”
Shamos, M.I. 306
Sherman, G.S. 456
Shiloach, Y. 217
Shor, N.Z. 191
Shortest-path problem (or SP) 75 109—13 303 439 451
Shrink a blossom 230
Simon, J. 404
Simonnard, M. 65
Simple network 213 225 458
| Simplex algorithm 2 26—115 163 166—70 475
Simplex algorithm, dual 80—85
Simplex algorithm, primal-dual 104—15 138 141 144—48 150 256
Simplex algorithm, revised 88—97
Size of the input 159—62 171
Slack variable 29
Sleator, D.D. 217
Sorting 187—88
Source 23
Source row 329
sp see “Shortest-path problem”
span 286
Spanning tree 5 22 272 439
Spanning tree, capacitated 152
Stage 206 224 276
Stearns, R.E. 432
Steiglitz, K. 484 485 486
Steinberg, D. 65 66
Stigler, G.J. 66
Stockmeyer, L.J. 486
Stoer, J. 18
Stone, R.E. 191
String (or sequence of symbols) 159 349
Strongly connected digraph 214
Strongly NP-complete problem 387—91 430
Subgraph Isomorphism 392
subproblem 98 434
Subset system 280 472
Subspace, affinc 34
Subspace, linear 34
Subtour 309 441
Sum-finishing-time problem (or SFTP) 444—45
Supporting hyperplane 36
Surplus variable 28
SURVIVABLE NETWORK DESIGN 392 456 483
Swap neighborhood 466—67
Sweeny, D.W. 452
Symmetric difference 220
Tableau 44—46 79—85
Tail-partition matroid 288
Talman, A.J J. 341
Tarjan, R.E. 216 217 246 305 306
Task 310
Terminal 23
Tf-TH HEAVIEST SUBSET 397 400
Thomason, A.G. 486
THREE PARTITION 390 403
Three-matroid intersection 300—301
Throughput 207
Tiling problem 186
Todd, M.J. 191
Tolstoi, A.N. 154
Tomlin, J.A. 155
Tompkins, C.B. 325
Totally unimodular (or TUM) 249 316—18
Toueg, S. 486
Tour 4
Tour, embedded 413
Tower of Hanoi 16 187
transform 352
Transformation 148 359 392
Transformation, affine 174
Transformation, polynomial-time 151 352
Transitive closure 403
TRANSITIVE REDUCTION BY ELIMINATION 404
Transversal matroid 303
Traveling salesman problem (or TSP) 3 4 7—10 157 283 303 308—10 344 349 371 379 384 427 439—42 450 455—56 469 472 477—81
Traveling salesman problem (or TSP), asymmetric 392
Traveling salesman problem (or TSP), Euclidean 379 411
Traveling salesman problem (or TSP), triangle-inequality 410—18
TREE 22
Tree algorithm 414
Tree, spanning 5 22 272 439
Treybig, L.B. 325
Triangle inequality 410
Triangle inequality TSP 410—18
Triangle operation 130
TRUE 314
Truth assignment 314
TSP see “Traveling salesman problem”
TSP SUBOPTIMALITY 481
Tucker, A.W. 87 309 324
TUM see “Totally unimodular”
Turing machine 157 347—48
Turing machine, nondeterministic 398
Turing, A.M. 157 190 355 382
Tutte matrix 243
Tutte, W.T. 246 306
Two-phase method 55—58
Two-processor scheduling 243
UGP see “Uniform graph partitioning”
Ullman, J.D. 24 136 190 381 382
Undecidable problem 157
Undirected graph 20
Uniform graph partitioning (or UGP) 465 481
Uniform partition 465
Unimodular matrix 316
Unimodular matrix, totally 316
Unit capacity 212—14 225
Unit sphere 174
Valiant, L.G. 404 405
Value of a flow 23
van Emde Boas, P. 341
Van Sickle, L. 155
Variable, admissible 106 144 257
Variable, artificial 55 106
Variable, basic 29
Variable, Boolean 314
Variable, slack 29
Variable, surplus 28
Variable-depth local search 468
Vazirani, V.V. 246
Veinott, A.F.Jr. 324
Vertex see “Node”
Vertex connectivity 457
Vertex of a polytope 36 39
von Neumann, J. 86 190
Voronoi polygon see “Dirichlet cell”
Wagner, H.M. 155
Walk 21
Walk, directed 21
Walk, Eulerian 412
Walk, Hamilton 431
Wandering salesman problem 303
Warshall, S.M. 136
Weighted graph 22
Weighted matching problem 247—66 282
Weighted matroid intersection 298—99
Weiner, P. 456 484 485
while statement 25
Whitney, H. 306
Witzgall, C 18
Wolfe, P. 103 341
X-change 460
X-change neighborhood 460
X-change, favorable 460
Yannakakis, M. 246 270 405 432
Yao, A.C. 305
Yudin, D.B. 65 87 191
Z (set of integers) 19
Zadeh, N. 153 154 191 192
Zemlin, R.A. 342
ZOLP see 0—1 “Linear program”
|
|
|
| Реклама |
|
|
|
|
|
О проекте