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

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

$GL(\epsilon)$ algorithm      125—126
$GL(\epsilon)$ algorithm, computational experiments using      131—134
$GL(\epsilon)$ algorithm, example using      126 127
$IK(\epsilon)$ algorithm      53—54
$IK(\epsilon)$ algorithm, example using      55
$IK(\epsilon)$ algorithm, KP solved using      54—55
$IK(\epsilon)$ algorithm, SSP solved using      125
(1,k)-configuration      76
0-1 Knapsack Problem (KP)      2 13—80 see "Multiple "Multiple-Choice "Unbounded
0-1 Knapsack Problem (KP) with Generalized Upper Bound (GUB) Constraints      77
0-1 Knapsack Problem (KP), approximate algorithms used      50—57
0-1 Knapsack Problem (KP), BKP as generalization of      81
0-1 Knapsack Problem (KP), BKP transformed into      82—84
0-1 Knapsack Problem (KP), bounds from additional constraints      20—23
0-1 Knapsack Problem (KP), bounds from partial enumeration      24—27
0-1 Knapsack Problem (KP), branch-and-bound algorithms used      29
0-1 Knapsack Problem (KP), continuous relaxation of      16—17
0-1 Knapsack Problem (KP), definition of      13
0-1 Knapsack Problem (KP), dynamic programming used      36—45
0-1 Knapsack Problem (KP), exact algorithms used      57—67
0-1 Knapsack Problem (KP), Fortran-coded algorithms used      247 248—252
0-1 Knapsack Problem (KP), fractions handled for      14
0-1 Knapsack Problem (KP), greedy algorithms used      27—29
0-1 Knapsack Problem (KP), improved bounds of      20—27
0-1 Knapsack Problem (KP), Lagrangian relaxation of      19—20
0-1 Knapsack Problem (KP), Lagrangian relaxation of, bounds from      23—24
0-1 Knapsack Problem (KP), linear programming relaxation of      16—17
0-1 Knapsack Problem (KP), minimization version of      15
0-1 Knapsack Problem (KP), minimization version of, solution of      29
0-1 Knapsack Problem (KP), nonpositive values handled for      14
0-1 Knapsack Problem (KP), NP-hardness of      6
0-1 Knapsack Problem (KP), probabilistic result for      56—57
0-1 Knapsack Problem (KP), reasons for study of      13
0-1 Knapsack Problem (KP), recursive formulae for      7
0-1 Knapsack Problem (KP), reduction algorithms used      45—50
0-1 Knapsack Problem (KP), relaxations of      16—20
0-1 Knapsack Problem (KP), SSP as special case of      105
0-1 Knapsack Problem (KP), upper bounds of      16—20
0-1 Linear Programming Problem (ZOLP), algorithm for solution of      171
0-1 Linear Programming Problem (ZOLP), definition of      170
0-1 Linear Programming Problem (ZOLP), lower bound on      171
0-1 Multiple Knapsack Problem (MKP)      157—187
0-1 Multiple Knapsack Problem (MKP), approximate algorithms used      177—182
0-1 Multiple Knapsack Problem (MKP), branch-and-bound algorithms used      168—170
0-1 Multiple Knapsack Problem (MKP), computational experiments for solution of      182—187
0-1 Multiple Knapsack Problem (MKP), continuous relaxation of      160—162
0-1 Multiple Knapsack Problem (MKP), definition of      157
0-1 Multiple Knapsack Problem (MKP), exact algorithms used      167—176
0-1 Multiple Knapsack Problem (MKP), Fortran-coded algorithms used      247 261—265
0-1 Multiple Knapsack Problem (MKP), greedy algorithms used      166—167
0-1 Multiple Knapsack Problem (MKP), Lagrangian relaxation of      162—165
0-1 Multiple Knapsack Problem (MKP), LEGAP as generalization of      191
0-1 Multiple Knapsack Problem (MKP), NP-hardness of      8
0-1 Multiple Knapsack Problem (MKP), polynomial-time approximation, algorithms used      179—182
0-1 Multiple Knapsack Problem (MKP), reduction algorithms used      176—177
0-1 Multiple Knapsack Problem (MKP), relaxations of      158—165
0-1 Multiple Knapsack Problem (MKP), surrogate relaxation of      158—162
0-1 Multiple Knapsack Problem (MKP), upper bounds of, techniques to obtain      158—165
0-1 Multiple Knapsack Problem (MKP), upper bounds of, worst-case performance of      165—166
Additional constraints, bounds from      20—23
ADJUST procedure      198—200
ADJUST procedure, example using      200
Aho, A.V.      15 18 223 275
Ahrens — Finke (dynamic programming) algorithm      107
Ahrens — Finke (dynamic programming) algorithm, computational experiments using      129
Ahrens, J.H.      29 39 43 107 129 130 275
Aittoniemi, L.      88 275
Approximate algorithms, BKP solved using      86—87
Approximate algorithms, BPP solved using      222—224
Approximate algorithms, GAP solved using      206—209
Approximate algorithms, KP solved using      50—57
Approximate algorithms, KP solved using, computational experiments involving      71—74
Approximate algorithms, MKP solved using      177—182
Approximate algorithms, SSP solved using      117—128
Approximate algorithms, SSP solved using, computational experiments for      130—136
Approximate algorithms, UKP solved using      93—95
Armstrong, R.D.      80 275
Assignment problems      see "Generalized Assignment Problem" "LEGAP" "MINGAP" "XYGAP"
Asymptotic worst-case performance ratio      223
AVIS problem      129
Avis, D.      128 275
Babat, L.G.      56 275
Bachem, A.      74 275
Baker, B.S.      223 275
Balas — Zemel algorithm      58—60
Balas — Zemel algorithm, computational experiments using      70
Balas, E.      14 17 47 57 58 59 60 62 68 75 76 163 275
Barr, R.S.      30 275
Bellman, R.      37 275
Best-Fit (BF) algorithm      223 224
Best-Fit Decreasing (BFD) algorithm      223—224 238
Bibliography      275
Bin-Packing Problem (BPP)      5 221—245
Bin-Packing Problem (BPP), approximate algorithms used      222—224
Bin-Packing Problem (BPP), approximate algorithms used, worst-case performance ratio of      222 223
Bin-Packing Problem (BPP), continuous relaxation of      224
Bin-Packing Problem (BPP), definition of      221
Bin-Packing Problem (BPP), Fortran-coded algorithm used      247 270—272
Bin-Packing Problem (BPP), Lagrangian relaxation of      226—227
Bin-Packing Problem (BPP), lower bounds for      224—233
Bin-Packing Problem (BPP), lower bounds for, worst-case performance ratio for      224 228 232
Bin-Packing Problem (BPP), NP-hardness of      9
Bin-Packing Problem (BPP), reduction algorithms used      233—237
Bin-Packing Problem (BPP), relaxations of      224—227
Bin-Packing Problem (BPP), relaxations-based lower bounds for      224—228
Bin-Packing Problem (BPP), relaxations-based lower bounds for, computational experiments using      241—244
Bin-Packing Problem (BPP), stronger lower bound for      228—233
Bin-Packing Problem (BPP), surrogate relaxation of      225—226
Binary knapsack problem      see "0-1 Knapsack Problem (KP)"
Binary tree, upper bound of KP      26
Bornstein, C.T.      22 282
Bound-and-bound algorithm      171
Bound-and-bound algorithm, MKP solved using      172—176
Bound-and-bound method      170—172
Bounded Change-Making Problem (BCMP)      153—156
Bounded Change-Making Problem (BCMP), branch-and-bound algorithm used      155
Bounded Change-Making Problem (BCMP), computational experiments for solution of      156
Bounded Change-Making Problem (BCMP), continuous relaxation of      153—154
Bounded Change-Making Problem (BCMP), definition of      153
Bounded Change-Making Problem (BCMP), Fortran-coded algorithm used      247 259—261
Bounded Change-Making Problem (BCMP), greedy algorithm used      155
Bounded Change-Making Problem (BCMP), lower bound for      154
Bounded Knapsack Problem (BKP)      3 81—91
Bounded Knapsack Problem (BKP), approximate algorithms used      86—87
Bounded Knapsack Problem (BKP), branch-and-bound algorithms used      88—89
Bounded Knapsack Problem (BKP), computational experiments for solution of      89—91
Bounded Knapsack Problem (BKP), definition of      81
Bounded Knapsack Problem (BKP), dynamic programming used      88
Bounded Knapsack Problem (BKP), exact algorithms used      87—89
Bounded Knapsack Problem (BKP), Fortran-coded algorithm used      247 252—254
Bounded Knapsack Problem (BKP), NP-hardness of      6
Bounded Knapsack Problem (BKP), recursive formulae for      7
Bounded Knapsack Problem (BKP), special case of      91—103
Bounded Knapsack Problem (BKP), transformation into KP      82—84
Bounded Knapsack Problem (BKP), upper bounds of      84—86
Branch-and-bound algorithms, BCMP solved using      155
Branch-and-bound algorithms, BKP solved using      88—89
Branch-and-bound algorithms, CMP solved using      146—149
Branch-and-bound algorithms, compared with dynamic programming algorithms      70
Branch-and-bound algorithms, GAP solved using      204—206
Branch-and-bound algorithms, Greenberg — Hegerich approach      29 30
Branch-and-bound algorithms, Kolesar algorithm      29
Branch-and-bound algorithms, KP solved using      14 26—27 29—36
Branch-and-bound algorithms, MKP solved using      168—170
Branch-and-bound tree, upper bound of KP      27
Brown, J.R.      237 278
Bulfin, R.L.      88 275
BZ algorithm      60
BZC algorithm      58—59
Cabot, A.V.      96 276

Canonical inequalities      75
Canonical vectors      142
Carpaneto, G.      191 276
CDC-Cyber 730 computer, CMP experiments run on      151
CDC-Cyber 730 computer, KP experiments run on      68—71
CDC-Cyber 730 computer, MKP experiments run on      183 184 185
CDC-Cyber 730 computer, SSP experiments run on      129 130 132—134
Chalmet, L.      191 276
Chang, L.      145 276
Chang, S.K.      142 143 145 151 276
Change-Making Problem (CMP)      4 137—156
Change-Making Problem (CMP), BCMP as generalization of      153
Change-Making Problem (CMP), branch-and-bound algorithms used      146—149
Change-Making Problem (CMP), computational experiments for solution of      151—153
Change-Making Problem (CMP), definition of      137
Change-Making Problem (CMP), dynamic programming used      145—146
Change-Making Problem (CMP), exact algorithms used      145—149
Change-Making Problem (CMP), Fortran-coded algorithms used      247 258—259
Change-Making Problem (CMP), greedy algorithms used      140—142
Change-Making Problem (CMP), large-size problems      149—151
Change-Making Problem (CMP), lower bounds for      138—140
Change-Making Problem (CMP), NP-hardness of      7
Change-Making Problem (CMP), recursive formulae for      8
Christofides, N.      168 237 276
Chvatal, V.      128 276
Coffman, E.G., Jr.      222 223 275 276
Combinatorial optimization      13
Computational experiments, BCMP-solving algorithm      156
Computational experiments, BKP-solution algorithms      89—91
Computational experiments, CMP-solution algorithms      151—153
Computational experiments, Fayard — Plateau algorithm used      70
Computational experiments, GAP-solving algorithms      213—220
Computational experiments, KP-solution algorithms      67—74
Computational experiments, MKP-solving algorithms      182—187
Computational experiments, SSP-solution algorithms      128—136
Computational experiments, UKP-solution algorithms      102—103
Continuous knapsack problem      16
Continuous Knapsack Problem, solutions of      17 19
Continuous relaxations      11
Continuous relaxations, BCMP      153—154
Continuous relaxations, BPP      224
Continuous relaxations, GAP      192
Continuous relaxations, KP      16—17
Continuous relaxations, MKP      160—162
Cord, J.      276
CORE algorithm      63—64 72
Core problem, KP      14 57
Core problem, SSP      116
Core problem, UKP      98
Critical item, finding in nominated time      17—19 25
Critical item, meaning of term      16
Critical ratio, definition of      17
CRITICAL_ITEM algorithm      18
CRITICAL_ITEM algorithm, BCMP solved using      155
Crowder, H.      13 276
d'Atri, G.      56 126 275
Dannenbring, D.      168 280
Dantzig bound      17 24 45 59 162 197
Dantzig, G.B.      14 16 37 162 276
de Kluyver, C.A.      5 281
Decision-trees, BPP lower bounds      239
Decision-trees, HS algorithm      33
Decision-trees, MT1 algorithm      37
Decision-trees, MTC1 algorithm      149
Decision-trees, MTM algorithm      175
Decision-trees, MTRG1 algorithm      212
Decision-trees, MTS algorithm      115
Decision-trees, MTU1 algorithm      99
Decision-trees, MTU2 algorithm      102
DeMaio, A.      191 276
Dembo, R.S.      47 276
Demers, A.      10 223 233 278
Deo, N.      5 32 281
Depth-first algorithm, meaning of term      29
Depth-first branch-and-bound algorithms      168
Depth-first branch-and-bound algorithms, GAP solved using      204—206
Dietrich, B.L.      13 106 276
Diophantine equation, SSP related to      105
Dominance criteria, MCKP      78—80
Dominated states, elimination of      39—12
Dominated states, meaning of term      39
DP1 algorithm      39
DP1 algorithm, compared with DP2      44
DP1 algorithm, example using      42
DP2 algorithm      41—42
DP2 algorithm, compared with DP1      44
DP2 algorithm, example using      42 44
DP2 algorithm, states of      42 44
DPS algorithm      109
Dreyfus, S.E.      275
Dudzinski — Walukiewicz bound      24
Dudzinski, K.      5 23 24 26 80 276
Dyer, M.E.      80 276
Dynamic programming, algorithms compared with branch-and-bound algorithms      70
Dynamic programming, BKP solved using      88
Dynamic programming, CMP solved using      145—149
Dynamic programming, combined with tree-search to solve SSP      109—116
Dynamic programming, knapsack problems first solved by      14
Dynamic programming, KP solved using      36—45
Dynamic programming, meaning of term      37—38
Dynamic programming, SSP solved using      106—109
Eilon, S.      237 276
Elkihel, M.      36 116 281
Escudero, L.F.      13 106 276
Exact algorithms, BKP solved using      87—89
Exact algorithms, CMP solved using      145—149
Exact algorithms, GAP solved using      204—206
Exact algorithms, KP solved using      57—67
Exact algorithms, KP solved using, computational experiments involving      68—71
Exact algorithms, large-size CMP solved using      149—151
Exact algorithms, large-size UKP solved using      98 100—102
Exact algorithms, MKP solved using      167—176
Exact algorithms, SSP solved using      106—117
Exact algorithms, SSP solved using, computational experiments involving      129—130
Exact algorithms, UKP solved using      95—98
Faaland, B.      107 276
Fayard — Plateau algorithm      60—61
Fayard — Plateau algorithm, computational experiments using      70
Fayard, D.      22 30 47 48 60 68 276 277
Feldman, I.      96 278
Finke, G.      29 39 43 107 129 130 275
First-Fit (FF) algorithm, BBP solved using      222—223 224
First-Fit Decreasing (FFD) algorithm      223—224 238 240
Fischetti, M.      102 122 124 176 277
Fisher — Jaikumar — Van Wassenhove algorithm, GAP solved using, computational experiments for      214—218
Fisher — Jaikumar — Van Wassenhove bound      197 200—201
Fisher, M.L.      9 20 197 206 213 218 219 277
Fisk, J.C.      179 185 277
FPDHR reduction algorithm      47
Frieze, A.M.      128 277
FS(k) algorithm      124
FS(k) algorithm, compared with MTSS(k) algorithm      125
Fully polynomial-time approximation schemes      10 14
Fully polynomial-time approximation schemes, computational inferiority of      72
Fully polynomial-time approximation schemes, KP solved using      53—57
Fully polynomial-time approximation schemes, not possible for MKP      178
Fully polynomial-time approximation schemes, SSP solved using      125—126
Garey, M.R.      6 8 10 177 178 222 223 233 276 277 278
Garfinkel, R.S.      5 96 277
Gelders, L.      191 276
Generalized Assignment Problem (GAP)      4 189—220
Generalized Assignment Problem (GAP), approximate algorithms used      206—209
Generalized Assignment Problem (GAP), branch-and-bound algorithms used      204—206
Generalized Assignment Problem (GAP), computational experiments for solution of      213—220
Generalized Assignment Problem (GAP), definition of      189
Generalized Assignment Problem (GAP), exact algorithms used      204—206
Generalized Assignment Problem (GAP), Fortran-coded algorithms used      247 265—270
Generalized Assignment Problem (GAP), Lagrangian relaxation of      193—194
Generalized Assignment Problem (GAP), minimization version of      190
Generalized Assignment Problem (GAP), NP-hardness of      8

1 2 3

О проекте