Главная    Ex Libris    Книги    Журналы    Статьи    Серии    Каталог    Wanted    Загрузка    ХудЛит    Справка    Поиск по индексам    Поиск    Форум   
blank
Авторизация

       
blank
Поиск по указателям

blank
blank
blank
Красота
blank
Papadimitriou C.H., Steiglitz K. — Combinatorial Optimization: Algorithms and Complexity
Papadimitriou C.H., Steiglitz K. — Combinatorial Optimization: Algorithms and Complexity

Читать книгу
бесплатно

Скачать книгу с нашего сайта нельзя

Обсудите книгу на научном форуме



Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter


Название: Combinatorial Optimization: Algorithms and Complexity

Авторы: Papadimitriou C.H., Steiglitz K.

Аннотация:

This clearly written , mathematically rigorous text includes a novel algorithmic exposition of the simplex method and also discusses the Soviet ellipsoid algorithm for linear programming; efficient algorithms for network flow, matching, spanning trees, and matroids; the theory of NP-complete problems; approximation algorithms, local search heuristics for NP-complete problems, more. All chapters are supplemented by thought-provoking problems. A useful work for graduate-level students with backgrounds in computer science, operations research, and electrical engineering.


Язык: en

Рубрика: Математика/

Серия: Сделано в холле

Статус предметного указателя: Готов указатель с номерами страниц

ed2k: ed2k stats

Год издания: 1998

Количество страниц: 496

Добавлена в каталог: 09.10.2010

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID
blank
Предметный указатель
$\Delta$-change neighborhood      463
$\Delta$TSP      see “Triangle inequality TSP”
$\epsilon$-approximate algorithm      409
$\epsilon$-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, $\epsilon$-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
1 2 3
blank
Реклама
blank
blank
HR
@Mail.ru
       © Электронная библиотека попечительского совета мехмата МГУ, 2004-2018
Электронная библиотека мехмата МГУ | Valid HTML 4.01! | Valid CSS! О проекте