√лавна€    Ex Libris     ниги    ∆урналы    —татьи    —ерии     аталог    Wanted    «агрузка    ’удЋит    —правка    ѕоиск по индексам    ѕоиск    ‘орум   

ѕоиск по указател€м

Martello S., Toth P. Ч Knapsack problems: algorithms and computer implementations
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.

язык: en

–убрика: “ехнологи€/

—татус предметного указател€: √отов указатель с номерами страниц

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
       © Ёлектронна€ библиотека попечительского совета мехмата ћ√”, 2004-2019
Ёлектронна€ библиотека мехмата ћ√” | Valid HTML 4.01! | Valid CSS! ќ проекте