Martello S., Toth P. — Knapsack problems: algorithms and computer implementations :: Электронная библиотека попечительского совета мехмата МГУ

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

Авторизация

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

Martello S., Toth P. — Knapsack problems: algorithms and computer implementations

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

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

Название: Knapsack problems: algorithms and computer implementations

Авторы: Martello S., Toth P.

Аннотация:

Here is a state of art examination on exact and approximate algorithms for a number of important NP-hard problems in the field of integer linear programming, which the authors refer to as ``knapsack.'' Includes not only the classical knapsack problems such as binary, bounded, unbounded or binary multiple, but also less familiar problems such as subset-sum and change-making. Well known problems that are not usually classified in the knapsack area, including generalized assignment and bin packing, are also covered. The text fully develops an algorithmic approach without losing mathematical rigor.

Язык:

Рубрика: Технология/

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

ed2k: ed2k stats

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

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

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

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID

Предметный указатель

Polytope, meaning of term      74
Probabilistic analysis      10
Probabilistic analysis, KP      56—57
Probabilistic analysis, SSP      126 128
Problems, AVIS      129
Problems, AVIS, computational experiments using      129
Problems, EVEN/ODD      128
Problems, EVEN/ODD, computational experiments using      129 133
Problems, TODD      128
Problems, TODD, computational experiments using      129 134
Procedures, $GL(\epsilon)$       125—126
Procedures, $GL(\epsilon)$ , computational experiments using      131—134
Procedures, $GL(\epsilon)$ , example using      126 127
Procedures, $IK(\epsilon)$       53—54
Procedures, $IK(\epsilon)$ , dynamic programming phase of      53 55
Procedures, $IK(\epsilon)$ , example using      55
Procedures, $IK(\epsilon)$ , greedy phase of      54 56
Procedures, $IK(\epsilon)$ , SSP solved using      125
Procedures, ADJUST      198—200
Procedures, ADJUST, example using      200
Procedures, BOUND AND BOUND      171
Procedures, BZ      60
Procedures, BZC      58—59
Procedures, CORE      63—64 72
Procedures, CRITICAL_ITEM      18
Procedures, CRITICAL_ITEM, BCMP solved using      155
Procedures, DP1      39
Procedures, DP1, compared with DP2      44
Procedures, DP1, example using      42
Procedures, DP2      41—42
Procedures, DP2, compared with DP1      44
Procedures, DP2, example using      42 44
Procedures, DP2, states of      42
Procedures, DPS      109
Procedures, example using      83—84
Procedures, GREEDY      28—29
Procedures, GREEDY, SSP solved using      117
Procedures, GREEDYB      86—87
Procedures, GREEDYB, computational experiments using      89—91
Procedures, GREEDYS      179
Procedures, GREEDYS, use in MTHM      180 181
Procedures, GREEDYU      95
Procedures, GREEDYUM      141
Procedures, GREEDYUM, BCMP solved using      155
Procedures, GREEDYUM, example using      141
Procedures, GS      50 118
Procedures, H      59
Procedures, HS      30—31
Procedures, HS, decision-tree of      33
Procedures, HS, example using      32
Procedures, IKR      46
Procedures, IKR, example using      46—47
Procedures, IKRM      176
Procedures, IKRM, computational experiments using      183 184
Procedures, IKRM, time complexity of      177
Procedures, J(k)      120 122
Procedures, J(k), compared with procedure MTTS (K)      122—123
Procedures, J(k), computational experiments using      131—135
Procedures, J(k), example using      121
Procedures, L2      231—232
Procedures, L2, computational experiments using      241—244
Procedures, L2, example using      236
Procedures, L2, main variables in      231
Procedures, L2, worst-case performance ratio of      232—233
Procedures, L3      235—236
Procedures, L3, computational experiments using      241—244
Procedures, L3, example using      236 240
Procedures, LISTS      110—111
Procedures, LISTS, example using      111
Procedures, LOWER      173
Procedures, MNT      144—145
Procedures, MNT, example using      145
Procedures, MT1      34—36
Procedures, MT1'      64
Procedures, MT1, computational experiments using      69 70
Procedures, MT1, decision-tree of      37
Procedures, MT1, example using      36
Procedures, MT1, Fortran implementation of      247 248—249
Procedures, MT1R      247 249—251
Procedures, MT2      66—67
Procedures, MT2, computational experiments using      70 71
Procedures, MT2, Fortran implementation of      247 251—252
Procedures, MT2, heuristic version of      72
Procedures, MTC1      147—148
Procedures, MTC1, computational experiments using      151—153
Procedures, MTC1, decision-tree for      149
Procedures, MTC1, example using      149
Procedures, MTC2      150
Procedures, MTC2, computational experiments using      152
Procedures, MTC2, Fortran implementation of      247 258—259
Procedures, MTCB      155
Procedures, MTCB, computational experiments using      156
Procedures, MTCB, Fortran implementation of      247 259—261
Procedures, MTGS      118 121
Procedures, MTGSM      123—124
Procedures, MTGSM, example using      124
Procedures, MTHG      206—207
Procedures, MTHG, computational experiments using      219—220
Procedures, MTHG, example using      208
Procedures, MTHG, Fortran implementation of      247 268—270
Procedures, MTHM      180—181
Procedures, MTHM, computational experiments using      185—187
Procedures, MTHM, example using      182
Procedures, MTHM, Fortran implementation of      247 263—265
Procedures, MTM      173—174
Procedures, MTM, computational experiments using      183—186
Procedures, MTM, decision-tree for      175
Procedures, MTM, example using      175
Procedures, MTM, Fortran implementation of      247 261—263
Procedures, MTM, modified version of      176
Procedures, MTR      48—49
Procedures, MTR'      64—65
Procedures, MTR, computational experiments using      69
Procedures, MTR, example using      49
Procedures, MTRG1      209—210
Procedures, MTRG1, decision-tree when used      212
Procedures, MTRG1, example using      211—213
Procedures, MTRG2      210—211
Procedures, MTRP      234
Procedures, MTRP, example using      236 240
Procedures, MTRP, time complexity of      237
Procedures, MTS      113—114
Procedures, MTS, decision-tree for      115
Procedures, MTS, example using      115
Procedures, MTSL      116—117
Procedures, MTSL, computational experiments using      129—130
Procedures, MTSL, Fortran implementation of      247 256—257
Procedures, MTSS(k)      121—122
Procedures, MTSS(k), compared with procedure J(k)      122—123
Procedures, MTSS(k), computational experiments using      131—136
Procedures, MTSS(k), example using      123
Procedures, MTSS(k), worst-case performance ratio of      122
Procedures, MTU1      96—97
Procedures, MTU1, computational experiments using      103
Procedures, MTU1, decision-tree for      99
Procedures, MTU1, example using      98
Procedures, MTU2      100
Procedures, MTU2, computational experiments using      103
Procedures, MTU2, decision-tree for      102
Procedures, MTU2, example using      101
Procedures, MTU2, Fortran implementation of      247 254—255
Procedures, R      59
Procedures, REC1      38—39
Procedures, REC2      40—41
Procedures, REC2, dynamic programming algorithm using      41—42
Procedures, REC2, example using      44

Procedures, RECS      108
Procedures, S(k)      51
Procedures, S(k), example using      52
Procedures, TB01      83
Procedures, UPPER      172—173
Pseudo-polynomial algorithm      7
Pseudo-polynomial transformation      8
Puech, C.      126 275
Pulleyblank, W.R.      74 281
Rao, M.R.      76 191 277 278
REC1 procedure      38—39
REC2 procedure      40—41
REC2 procedure, dynamic programming algorithm using      41—42
REC2 procedure, example using      44
Recognition problem      6
RECS procedure      108
Reduction algorithms, BPP solution involving      233—237
Reduction algorithms, GAP solution involving      209—213
Reduction algorithms, KP solution involving      45—50
Reduction algorithms, MKP solution involving      176—177
Reduction procedures, Balas — Zemel method use of      59
Reduction procedures, first used      14
References listed      275
Relaxations      11 see "Lagrangian "Surrogate
Relaxations, BCMP      153—154
Relaxations, BPP      224—227
Relaxations, GAP      192—204
Relaxations, KP      16—20
Relaxations, MKP      158—165
Rinnooy Kan, A.H.G.      10 50 57 279 280 281
Ross — Soland algorithm, GAP computational experiments using      214—218
Ross — Soland bound      193 197 201
Ross — Soland bound, computational experiments using      72—73
Ross, G.T.      30 163 192 193 197 204 213 218 275 281
Roveda, C.      191 276
Ryder, B.F.      248 281
S(k) algorithm      51 see
S(k) algorithm, examples using      52
Sahni polynomial-time approximation scheme      51 53 56
Sahni, S.      10 29 32 39 43 50 68 71 121 278 281
Salkin, H.M.      5 281
Schreck, H.      128 281
Schrijver, A.      5 74 281
Sequential lifting procedure      76
Shetty, C.M.      88 275
Simultaneous lifting procedure      76
Single knapsack problems      see "Bounded Change-Making Problem" "Bounded "Change-Making "Multiple-Choice "Subset-Sum "Unbounded "Unbounded
Sinha, P.      80 275 281
Soland, R.M.      163 192 193 197 204 213 218 281
Spielberg, K.      30 278
Srinivasan, V.      191 281
States, meaning of term      38
States, procedure DP2      42
Steiglitz, K.      5 281
Stickstacking Problem      105 see
Stougie, L.      57 280
Subset-Sum Problem (SSP)      3 105—136
Subset-Sum Problem (SSP), approximate algorithms used      117—128
Subset-Sum Problem (SSP), computational experiments for      130—136
Subset-Sum Problem (SSP), computational experiments for solution of      128—136
Subset-Sum Problem (SSP), core problem of      116
Subset-Sum Problem (SSP), definition of      105
Subset-Sum Problem (SSP), dynamic programming used      106—109
Subset-Sum Problem (SSP), exact algorithms used      106—117
Subset-Sum Problem (SSP), exact algorithms used, computational experiments for      129—130
Subset-Sum Problem (SSP), Fortran-coded algorithm used      247 256—257
Subset-Sum Problem (SSP), fully polynomial-time approximation schemes used      125—126
Subset-Sum Problem (SSP), greedy algorithm used      117—119
Subset-Sum Problem (SSP), hybrid algorithm used      109—116
Subset-Sum Problem (SSP), large-size problems solved      116—117
Subset-Sum Problem (SSP), NP-hardness of      6
Subset-Sum Problem (SSP), polynomial-time approximation schemes used      120—125
Subset-Sum Problem (SSP), polynomial-time approximation schemes used, computational experiments involving      131—136
Subset-Sum Problem (SSP), probabilistic result for      126 128
Subset-Sum Problem (SSP), recursive formulae for      7
Suhl, U.      32 281
Surrogate relaxations      11
Surrogate relaxations, BPP      225—226
Surrogate relaxations, MKP      158—162
Syslo, M.M.      5 32 281
Szkatula, K.      57 281
Taha, H.A.      5 281
TB01 algorithm      83
TB01 algorithm, example using      83—84
Terminology      2—5
Thompson, G.L.      191 281
Tien, B.N.      142 145 281
Tinhofer, G.      128 281
TODD problem      128 129 133
Todd, M.      128 281
Toth dynamic programming algorithm      44
Toth dynamic programming algorithm, computational experiments using      69
Toth, P.      5 14 20 22 24 32 36 38 39 44 45 48 60 61 68 85 88 91 93 96 98 100 101 107 109 116 118 119 121 122 131 135 139 145 146 149 154 159 162 168 169 170 172 175 179 180 182 184 185 191 195 204 206 209 212 213 218 228 233 237 248 261 263 276 277 279 280 281
Tree-search, combined with dynamic programming to solve SSP      109—116
Trotter, L.E.      76 280
Trotter, L.E., Jr.      95 142 143 279
Ullman, J.D.      10 15 18 223 233 275 278
Ullmann, Z.      88 281
Unbounded Change-Making Problem      4 see
Unbounded Change-Making Problem, Fortran-coded algorithms used      247 258—259
Unbounded Equality Constrained Min-Knapsack Problem (UEMK)      141
Unbounded Knapsack Problem (UKP)      3 91—103
Unbounded Knapsack Problem (UKP), approximate algorithms used      93—95
Unbounded Knapsack Problem (UKP), computational experiments for solution of      102—103
Unbounded Knapsack Problem (UKP), core problem of      98
Unbounded Knapsack Problem (UKP), definition of      91—92
Unbounded Knapsack Problem (UKP), exact algorithms used      95—98
Unbounded Knapsack Problem (UKP), Fortran-coded algorithm used      247 254—255
Unbounded Knapsack Problem (UKP), large-size problems      98 100—102
Unbounded Knapsack Problem (UKP), minimization form of, UEMK containing      141
Unbounded Knapsack Problem (UKP), upper bounds of      92—94
Upper bounds      11
Upper bounds, BKP      84—86
Upper bounds, GAP      192—204
Upper bounds, KP      16—20
Upper bounds, MKP, techniques to obtain      158—165
Upper bounds, MKP, worst-case performance of      165—166
Upper bounds, UKP      92—94
UPPER procedure      172—173
Value Independent Knapsack Problem      105 see
Van Wassenhove, L.N.      197 206 213 218 219 277
Variable splitting method, GAP relaxed by      201—204
Veliev, G.P.      30 282
Vercellis, C.      57 279 280
Verebriusova, A.      107 282
Villela, P.R.C.      22 282
Walker, J.      80 276
Walukiewicz, S.      5 23 24 26 80 276
Weingartner, H.M.      282
Wolsey, L.A.      5 74 75 76 281 282
Wong, C.K.      92 278
Worst-case analysis      9—10
Worst-case performance ratio, BPP algorithms      222
Worst-case performance ratio, BPP lower bounds      224 228 232
Worst-case performance ratio, definition of      9
Worst-case performance ratio, L2 algorithm      232—233
Worst-case performance ratio, MKP upper bounds      165—166
Worst-case performance ratio, MTSS(k) algorithm      122
Worst-case relative error      10
Worst-Fit Decreasing (WFD) algorithm      238
Wright algorithm      146
Wright algorithm, computational experiments using      151
Wright, J.W.      146 151 282
XYGAP      201
Zemel, E.      14 17 47 57 58 59 60 62 68 76 77 80 275 278 282
Zoltners algorithm      60
Zoltners, A.A.      32 60 80 275 281 282

1 2 3

О проекте