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

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

Generalized Assignment Problem (GAP), reduction algorithms used      209—213
Generalized Assignment Problem (GAP), relaxation of capacity constraints for      192—195
Generalized Assignment Problem (GAP), relaxation of semi-assignment constraints for      195—197
Generalized Assignment Problem (GAP), relaxations of      192—204
Generalized Assignment Problem (GAP), upper bounds of      192—204
Gens — Levner algorithm      see " $GL(\epsilon)$ algorithm"
Gens, G.V.      56 125 126 131 277 279
Geoffrion, A.      163 277
Gill, A.      142 143 145 151 276
Gilmore, P.C.      14 88 95 96 146 277
Glossary      272
Glover, F.      80 81 158 277
Goldberg, A.V.      57 59 277
Gomory, R.E.      14 88 95 96 146 277
Gonzalez, T.      10 281
Gottlieb, E.S.      76 191 277 278
Graham, R.L.      10 223 233 278
Greedy algorithm      28—29
Greedy algorithms      28
Greedy algorithms, BCMP solved using      155
Greedy algorithms, classes of knapsack problems solved by      142—145
Greedy algorithms, CMP solved using      140—142
Greedy algorithms, CMP solved using, computational experiments involving      151
Greedy algorithms, KP solved using      27—29
Greedy algorithms, MKP solved using      166—167
Greedy algorithms, SSP solved using      117—119
GREEDYB algorithm      86—87
GREEDYB algorithm, computational experiments using      89—91
GREEDYS algorithm      179
GREEDYS algorithm, use in MTHM      180 181
GREEDYU algorithm      95
GREEDYUM algorithm      141
GREEDYUM algorithm, BCMP solved using      155
GREEDYUM algorithm, example using      141
Greenberg, H.      29 88 96 278
Groetschel, M.      74 275
GS algorithm      118 50
Guignard, M.M.      30 201 278
Hall, A.D.      248 281
Hammer, P.L.      47 75 276 278
Hartvigsen, D.      77 278
Hegerich, R.L.      29 88 278
Heuristic procedures used Balas — Zemel algorithm for KP      59
Heuristic procedures used Martello — Toth algorithm for GAP      206—208 268—270
Heuristic procedures used Martello — Toth algorithm for MKP      180—182 263—265
Hirschberg, D.S.      92 278
Hopcroft, J.E.      15 18 223 275
Horowitz — Sahni branch-and-bound algorithm      30—32
Horowitz — Sahni branch-and-bound algorithm, compared with Martello — Toth algorithm      32—34
Horowitz — Sahni branch-and-bound algorithm, computational experiments using      69
Horowitz — Sahni branch-and-bound algorithm, notations used      30
Horowitz — Sahni dynamic programming algorithm      43
Horowitz — Sahni dynamic programming algorithm, example using      43
Horowitz — Sahni dynamic programming algorithm, states of      43
Horowitz, E.      29 32 39 43 68 278
HP 9000/840 computer, BKP experiments run on      89—91
HP 9000/840 computer, BPP experiments run on      240—244
HP 9000/840 computer, CMP experiments run on      152 156
HP 9000/840 computer, GAP experiments run on      214—220
HP 9000/840 computer, KP experiments run on      71—73
HP 9000/840 computer, MKP experiments run on      185 186
HP 9000/840 computer, SSP experiments run on      130
HP 9000/840 computer, UKP experiments run on      103
HS algorithm      30—31
HS algorithm, decision-tree of      33
HS algorithm, example using      32
Hu, T.C.      5 95 96 142 144 145 278 281
Hudson, P.D.      22 278
Hung — Fisk branch-and-bound algorithms, branching strategy for      168
Hung — Fisk branch-and-bound algorithms, computational experiments using      183 184
Hung — Fisk branch-and-bound algorithms, MKP solved using      168
Hung, M.S.      163 168 179 184 185 237 277 278
Ibarra — Kim polynomial-time approximate algorithm      53 see
Ibarra, O.H.      14 53 54 56 95 125 278
IBM-7094 computer, BKP solved on      88
IKR algorithm      46
IKR algorithm, compared with Martello — Toth algorithm      48
IKR algorithm, example using      46—47
IKR algorithm, time complexity of      47
IKRM algorithm      176
IKRM algorithm, computational experiments using      183 184
IKRM algorithm, time complexity of      177
Ingargiola — Korsh algorithm, BKP solved using      89—90
Ingargiola — Korsh algorithm, computational experiments using      89—90
Ingargiola — Korsh reduction algorithms      45—46 176 see "IKRM
Ingargiola, G.P.      14 45 88 91 176 184 278
Integer linear programming problem      13
Investments, knapsack problem solution for      1
J(k) algorithm      120 122
J(k) algorithm, compared with procedure MTSS(K)      122—123
J(k) algorithm, computational experiments using      131—135
J(k) algorithm, example using      121
Jaikumar, R.      197 206 213 218 219 277
Jeroslow, R.      75 275
Joernsten, K.      201 203 206 218 278
Johnson algorithm      see "J(k) algorithm"
Johnson, D.S.      6 8 10 14 120 131 177 178 222 223 233 276 277 278
Johnson, E.L.      13 75 276 278
Johnson, S.C.      145 278
Kannan, R.      92 279
Kaplan, S.      279
Karp, R.M.      6 10 50 279
Kayal, N.      80 276
Kernighan, B.W.      145 278
Kim, C.E.      14 53 54 56 95 125 278
Kim, S.      201 278
Klastorin, T.D.      209 279
Klingman, D.      80 277
Knapsack polytope      74—77
Knapsack problems, literature reviews on      5
Knapsack problems, meaning of term      1—2
Knapsack problems, terminology used      2—5
Knuth, D.E.      107 279
Kolesar, P.J.      14 29 279
Korsh, J.F.      14 45 88 91 145 176 184 276 278
Kowalik, J.S.      5 32 281
Kuhn, N.W.      191 279
Kung, D.S.      80 275
L1 lower bound (for BPP)      225—228
L1 lower bound (for BPP), computational experiments using      241—244
L2 algorithm      231—232
L2 algorithm, example using      236
L2 algorithm, main variables in      231
L2 algorithm, worst-case performance ratio of      232—233
L3 algorithm      235—236
L3 algorithm, computational experiments using      241—244
L3 algorithm, example using      236 240
Lagarias, J.C.      126 279
Lageweg, B.J.      30 279
Lagrangian relaxations      11
Lagrangian relaxations, bounds from      23—24
Lagrangian relaxations, BPP      226—227
Lagrangian relaxations, GAP      193—194
Lagrangian relaxations, KP      23—24
Lagrangian relaxations, MKP      162—165
Large-size CMP, algorithm for      149—151
Large-size KP, algorithms for      57—67
Large-size SSP, algorithm for      116—117
Large-size UKP, algorithm for      98 100—102
Lauriere, M.      30 48 279
Lawler (polynomial-time approximation) scheme      125 126
Lawler (polynomial-time approximation) scheme, computational experiments using      131—134
Lawler, E.L.      56 95 125 126 131 191 279
LBFD algorithm, BPP lower bound using      233
LBFD algorithm, computational experiments using      241—244
LEGAP      190—191
Lenard, M.L.      95 144 278
Lenstra, J.K.      10 30 50 279
Levner, E.V.      56 125 126 131 277 279
Libura, M.      57 281

Linear Min-Sum Assignment Problem      191
Linear programming relaxation, KP      16—17
LISTS algorithm      110—111
LISTS algorithm, example using      111
Lower bounds      9
Lower bounds, BCMP      154
Lower bounds, BPP      224—233
Lower bounds, CMP      138—140
Lower bounds, ZOLP      171
LOWER procedure      173
Lueker, G.S.      56 92 137 279
Maculan, N.      20 279
Magazine, M.J.      56 95 142 143 279
Mamedov, K.Sh.      30 282
Marchetti-Spaccamela, A.      57 59 277 279
Martello — Toth algorithms, GAP solved using      204—206 212
Martello — Toth algorithms, GAP solved using, computational experiments for      214—218
Martello — Toth bound      195 197
Martello — Toth branch-and-bound algorithm      32—36
Martello — Toth branch-and-bound algorithm, branching strategy for      169
Martello — Toth branch-and-bound algorithm, compared with Horowitz — Sahni algorithm      32—34
Martello — Toth branch-and-bound algorithm, computational experiments using      183 184
Martello — Toth branch-and-bound algorithm, Fortran implementation of      248
Martello — Toth branch-and-bound algorithm, MKP solved using      168—170
Martello — Toth exact algorithm      61—67
Martello — Toth polynomial-time algorithm, Fortran implementation of      263—265
Martello — Toth polynomial-time algorithm, MKP solved using      179—182
Martello — Toth reduction algorithm      48
Martello — Toth reduction algorithm, compared with Ingargiola — Korsh algorithm      48
Martello, S.      5 14 20 22 24 32 36 48 60 61 68 85 88 91 93 96 98 100 101 102 107 109 116 118 119 121 122 131 135 139 145 146 149 154 159 162 168 169 170 172 175 176 179 180 182 184 185 191 195 204 206 209 212 213 218 228 233 237 248 261 263 276 277 279 280
Mazzola, J.B.      209 280
McDiarmid, C.J.H.      10 50 279
Meanti, M.      57 280
MINGAP      190
Mingozzi, A.      168 276
Minimal covers, meaning of term      75
MNT algorithm      144—145
MNT algorithm, example using      145
MT1 algorithm      34—36
MT1 algorithm, computational experiments using      69 70
MT1 algorithm, decision-tree of      37
MT1 algorithm, example using      36
MT1 algorithm, Fortran implementation of      247 248—249
MT1' algorithm      64
MT1R algorithm      247 249—251
MT2 algorithm      66—67
MT2 algorithm, computational experiments using      70 71
MT2 algorithm, Fortran implementation of      247 251—252
MT2 algorithm, heuristic version of      72
MTB2 algorithm, computational experiments using      89—91
MTB2 algorithm, Fortran implementation of      247 252—254
MTC1 algorithm      147—148
MTC1 algorithm, computational experiments using      151—153
MTC1 algorithm, decision-tree for      149
MTC1 algorithm, example using      149
MTC2 algorithm      150
MTC2 algorithm, computational experiments using      152
MTC2 algorithm, Fortran implementation of      247 258—259
MTCB algorithm      155
MTCB algorithm, computational experiments using      156
MTCB algorithm, Fortran implementation of      247 259—261
MTG algorithm, computational experiments using      214—217
MTG algorithm, development of      205—206
MTG algorithm, Fortran implementation of      247 265—268
MTGS algorithm      118 121
MTGSM algorithm      123—124
MTGSM algorithm, example using      124
MTHG algorithm      206—207
MTHG algorithm, computational experiments using      219—220
MTHG algorithm, example using      208
MTHG algorithm, Fortran implementation of      247 268—270
MTHM algorithm      180—181
MTHM algorithm, computational experiments using      185—187
MTHM algorithm, example using      182
MTHM algorithm, Fortran implementation of      247 263—265
MTM algorithm      173—174
MTM algorithm, computational experiments using      183—186
MTM algorithm, decision-tree for      175
MTM algorithm, example using      175
MTM algorithm, Fortran implementation of      247 261—263
MTM algorithm, modified version of      176
MTP algorithm      237—238
MTP algorithm, computational experiments using      244—245
MTP algorithm, decision-tree produced by      239
MTP algorithm, example using      238—240
MTP algorithm, Fortran implementation of      247 270—272
MTR algorithm      48—49
MTR algorithm, computational experiments using      69
MTR algorithm, example using      49
MTR' algorithm      64—65
MTRG1 algorithm      209—210
MTRG1 algorithm, decision-tree when used      212
MTRG1 algorithm, example using      211—213
MTRP algorithm      234
MTRP algorithm, example using      236 240
MTRP algorithm, time complexity of      237
MTS algorithm      113—114
MTS algorithm, decision-tree for      115
MTS algorithm, example using      115
MTSL algorithm      116—117
MTSL algorithm, computational experiments using      129—130
MTSL algorithm, Fortran implementation of      129—130
MTSS(k) algorithm      121—122
MTSS(k) algorithm, compared with procedure J(k)      122—123
MTSS(k) algorithm, computational experiments using      131—136
MTSS(k) algorithm, example using      123
MTSS(k) algorithm, worst-case performance ratio of      122
MTU1 algorithm      96—97
MTU1 algorithm, computational experiments using      103
MTU1 algorithm, decision-tree for      99
MTU1 algorithm, example using      98
MTU2 algorithm      100
MTU2 algorithm, computational experiments using      103
MTU2 algorithm, decision-tree for      102
MTU2 algorithm, example using      101
MTU2 algorithm, Fortran implementation of      247 254—255
Mueller-Merbach bound      23
Mueller-Merbach, H.      23 280
Multiple knapsack problems      see also "Bin-Packing Problem (BPP)" "Generalized "0-1
Multiple-Choice Knapsack Problem (MCKP)      3 77—80
Multiplier adjustment method, GAP upper bound determined by      197—201
Murphy, R.A.      47 280
Naesberg, M.      201 203 206 218 278
Nauss exact algorithm, computational experiment using      69
Nauss, R.      47 275
Nauss, R.M.      32 68 80 280
Neebe, A.      168 280
Nemhauser, G.L.      5 74 76 88 96 277 280 281
Nemhauser, J.L.      95 142 143 279
Ness, D.N.      282
Next-Fit (NF) algorithm      222 224
Next-Fit Decreasing (NFD) algorithm      223—224
NP-hard problems      6—9
Odlyzko, A.M.      126 279
Oehlandt, K.      88 275
Oguz, O.      56 279
One-point theorem      144
Padberg, M.W.      13 76 276 281
Papadimitriou, C.H.      5 281
Parker, R.G.      88 275
Partial enumeration, KP bounds from      24
Peled, U.N.      75 278
Performance of algorithms      9
Plateau, G.      22 30 36 47 48 60 68 116 276 277 281
Polynomial-time approximation schemes      10 14
Polynomial-time approximation schemes, KP solved using      50—53
Polynomial-time approximation schemes, KP solved using, computational experiments      71—74
Polynomial-time approximation schemes, MKP solved using      179—182
Polynomial-time approximation schemes, SSP solved using      120—125
Polynomial-time approximation schemes, SSP solved using, computational experiments      131—136

1 2 3

О проекте