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

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

blank
blank
blank
Красота
blank
Grotschel M., Lovasz L., Schrijver A. — Geometric Algorithms and Combinatorial Optimization
Grotschel M., Lovasz L., Schrijver A. — Geometric Algorithms and Combinatorial Optimization



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



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


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

Авторы: Grotschel M., Lovasz L., Schrijver A.

Аннотация:

This book develops geometric techniques for proving the polynomial time solvability of problems in convexity theory, geometry, and - in particular - combinatorial optimization. It offers a unifying approach based on two fundamental geometric algorithms: - the ellipsoid method for finding a point in a convex set and - the basis reduction method for point lattices. The ellipsoid method was used by Khachiyan to show the polynomial time solvability of linear programming. The basis reduction method yields a polynomial time procedure for certain diophantine approximation problems. A combination of these techniques makes it possible to show the polynomial time solvability of many questions concerning poyhedra - for instance, of linear programming problems having possibly exponentially many inequalities. Utilizing results from polyhedral combinatorics, it provides short proofs of the poynomial time solvability of many combinatiorial optimization problems. For a number of these problems, the geometric algorithms discussed in this book are the only techniques known to derive polynomial time solvability. This book is a continuation and extension of previous research of the authors for which they received the Fulkerson Prize, awarded by the Mathematical Programming Society and the American Mathematical Society.


Язык: en

Рубрика: Математика/Алгебра/Комбинаторика/

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

ed2k: ed2k stats

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

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

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

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID
blank
Предметный указатель
Eulerian trail      19
Even circuit      19
Even cycle      236
Even, S.      255 280 335
Expansion parameter      82
Extended polymatroid      306 306—324 316
Extremal ray      184
Face      9
Facet      9
Facet-complexity      163 163—165
Faddeev, D.K.      1 335
Faddeeva, V.N.      1
Family, crossing      315 315—324
Family, intersecting      315 315—324
Family, lattice      313 313—319 325—329
Family, ring      313 313—319 325—329
Farkas lemma      12
Farkas, Gy.      15
Feasible solution      15
Feedback arc set      253 253—254
Feinstein, A.      199 335
Fenchel, W.      49 332
Feofiloff, P.      252 335
FLOOR      2
Flow      197 197—201 233—242
Flow value      197
Flow, minimum-cost      238—242
Flow, multicommodity      266—271
Flow, multiterminal      249
Flow-equivalent      249
Floyd, R.W.      235 335
Fonlupt, J.      250 274 281 332 335
Ford, L.R., Jr.      197 198 199 202 231 234 237 239 279 280 335
Forest      20
Forest polytope      216 216—217
Frank, A.      vii 168 189 190 216 247 252 280 324 335
Fridman, A.A.      336
Frobenius norm      8
Frobenius' marriage theorem      204
Frobenius, E G.      203 204 230 335
Frumkin, M.A.      45 155 336
Fueredi, Z.      127 331
Fulkerson's optimum arborescence theorem      243
Fulkerson, D.R.      197 198 199 202 225 231 234 237 238 239 241 243 246 277 279 280 284 335 336
Full column rank      3
Full row rank      3
Full-dimensional      3
Fully polynomial approximation algorithm (scheme)      35
Function minimization, odd submodular      325—329
Function minimization, submodular      310 310—311 315 316 325—329
Function, convex      49 55—56 188
Function, submodular      304 304—308
Function, support      49
Gabow, H.N.      243 247 336
Gain, maximum      241
Galil, Z.      231 236 243 247 336
Gallai graph      281
Gallai, T.      230 231 255 280 281 336
Gamma-function      68
Gantmacher, F.R.      1
Garey, M.R.      21 28 219 272 336
Gass, S.I.      1 337
Gathen, J. yon zur      45 155 337
Gaussian elimination      36—40
Gavril, F.      280 337
General Euclidean norm      5
Geometry of numbers      138—156
Gerards, A.M.H.      274 275 337
Gershovich, V.I.      94 345
Gewirtz, A.      332
Ghellinck, G. de      66 337
Ghouila-Houri, A.      280 337
Giles, R.      16 244 302 316 319 320 321 322 334 337 344
Gill, P.E.      66 337
Gilmore, P.C.      280 337
Glover, F.      236 337
Goffin, J.-L.      65 122 337
Goldberg, A.V.      237 337
Goldfarb, D.      65 71 72 82 94 107 248 332
Golumbic, M.      283 337
Gomory, R.E.      13 233 248 249 257 331 337
Gomory-Hu tree      249
Graham, R.L.      221 248 337
Gram — Schmidt orthogonalization      40
Graph      16—18 17
Greedy algorithm      212 212—213 246 306—308
Greenberg, H.      332
Greene, C.      250 337
Gritzmann, P.      66 332
Groetschel, M.      65 107 159 193 218 223 249 250 254 263 265 283 285 326 331 337 338 341 343
Gross, O.A.      280 336
Gruenbaum, B.      1 69 333 338
Guy, R.      334 344
H-perfect graph      299
Hadamard inequality      8
Hadlock, F.      250 338
Hajnal, A.      280 335 338
Half-integer multicommodity flow problem      267
Halfspace      9
Hall, M., Jr.      231 337 338
Hamiitonian graph      19
Hamiltonian circuit      19
Hamiltonian circuit problem      21
Hamiltonian digraph      19
Hamiltonian tour      19
Hanani, H.      334 344
Handle      264
Hartvigsen, D.B.      265 338
Hassin, R.      324 338
Hayward, R.B.      282 338
head      18
Hell, P.      248 337
Heller, I.      282 338
Hellman, M.E.      221 331
Hensel, K.      338
Hermite normal form      43 43—45 155 155—156
Hermite, C.      i 43 140 338
Hoang, C.T.      281 333
Hoffman, A.J.      199 238 239 241 280 282 337 339
Holland, O.      223 338
Holyer, I.      208 209 339
Homogenization, 1-      185
Hopcroft, J.E.      21 231 274 339
Hsu, W.-L.      282 302 339
Hu, T.C.      248 249 257 268 337 339
Hull, affine      3 182—184
Hull, conic      3
Hull, convex      3
Hull, linear      3
Hypergraph      225
Hyperplane      9
Ibarra, O.H.      35 339
Ideal in a partially ordered set      314
Identity matrix      2
Ikura, Y.      302 339
Imai, H.      66 339
Incidence vector      1
incident      17
Incident from      18
Incident to      18
Indegree      18
Independence testing, linear      40
Independent set of a matroid      211
Induced graph      17
Inequalities problem, linear diophantine      11—14 192 192—196
Inequalities, linear      9—13 41—43 49 75 189—191
Inequality system      9—11 75
Ingleton, A.W.      304 339
Initial endnode      18
Inner product      2
Inner radius      53
Input of a problem      22
Input size      23 30
Instance of a problem      21 22
Integer linear programming      15—16 192—196
Integer linear programming problem      16
Integer multicommodity flow problem      267
Integral optimization over extended polymatroids      309
Integral polyhedron      200
Interior $\epsilon$-ball of K      6
Internal node      19
Intersecting family      315 315—324
Intersection of convex sets      129—131 188
Intersection of two matroids      214 214—218 306 310
Interval graph      279
Inverse matrix      40
Iri, M.      66 211 339
Isolated node      17
Isthmus      19
Jensen, P.M.      309 339
John, F.      69 124 339
Johnson, D.S.      21 28 219 267 272 336 339
Johnson, E.L.      257 258 260 261 262 334
Join, T-      259 259—262
Jordan, W.      124
Juenger, M.      vii 250 254 331 338
K-connected graph      19
Kannan, R.      45 151 334 339
Kariv, O.      255 335
Karmarkar's method      65—66
Karmarkar, N.      65 66 339
Karp, R.M.      vii 28 65 189 231 238 239 249 265 334 339 340
Karzanov, A.V.      252
Khachiyan, L.G.      v 25 64 65 71 157 158 180 181 198 232 235 242 265 340
Khintchine, A.      132 136 340
Kim, C.E.      35 339
Klee, V.      42 64 69 333 340
Klingman, D.      236 337
Knuth, D.E.      250 340
Koenig's edge coloring theorem      209
Koenig's edge covering theorem      230
Koenig's matching theorem      230
Koenig, D.      25 209 210 230 231 232 238 240 277 279 280 305 332 340
Konnerth, T.      vii
Koopmans, T.C.      232 333
Korte, B.      309 337 339 341 344
Kozlov, M.K.      181 340
Kronecker, L.      334
Kruskal, J.B.      199 247 282 339 340
Kuhn, H.W.      233 279 280 339 340
Kupferschmid, M.      64 334
Kuratowski, C.      25
Kwan, M.-K.      262 340
Lagarias, J.C.      138 218 220 221 340 341
Laminar      317
Lancaster, P.      1 341
Las Vergnas, M.      282 332
Lattice      139 139—156
Lattice family      313 313—319 325—329
Lattice vector problem, nearest      141
Lattice vector problem, shortest      140 143
Lawlet, E.L.      16 65 216 324 338 341 343
Leading principal submatrix      2
Lehman, A.      225 226 227 228 246 252 284 341
Lekkerkerker, C.G.      139 280 341
Lempel, A.      280 335
Length      19 23
Lenstra, A.K.      133 141 149 341
Lenstra, H.W., Jr.      v vi 124 133 134 141 149 162 193 195 196 341
Lenstra, J.K.      338 343
Levin, A.Yu.      65 341
Levin, L.A.      65 104 346
Line graph      18 279 302
Line perfect graph      281
Lineality space      10 183
linear combination      3
Linear diophantine equations      11—12 45 155—156
Linear diophantine inequalities problem      11—14 192 192—196
Linear equations      11—12 36—40
Linear form problem, small      139 147
Linear hull      3
Linear independence testing      40
Linear inequalities      9 43 41—43 49 75 189—191
Linear program      14
Linear programming      14—16 41—43 49 180 188 192
Linear programming duality      15
Linear programming problem      14
Linear programming, integer      15—16 192—196
Linear subspace      3
Linearly (in)dependent      3
Liu, T H.      201 242 333
Loewner, K.      69
Loewner-John ellipsoid      69 69—73 122—127
Lomonossov, M.V.      268 341
Longest branching problem      245
Longest dipath problem      240
Lovasz, L.      65 107 133 140 141 149 159 160 181 193 195 218 230 246 259 261 262 275 277 283 285 309 311 326 334 337 338 341 342 344
Lower integer part      2
LP-relaxation      16
Lucchesi, C.L.      251 252 253 254 321 342
Lucchesi—Younger theorem      252
Lueker, G.S.      280 281 332 342 344
Mader, W.      225 247 342
Magnanti, T.L.      250 337
Mahadev, N.V.R.      281 333
Mahjoub, A.R.      249 250 254 331 335
Marcus, M.      1 342
Marsh, A.B., III.      256 257 258 333 342
Martel, C.U.      324 341
Matching      17 203—208 229 229—233 253—254 305
Matching number      229
Matching polytope      204—206 255 255—256
Matching polytope, b-      257
Matching problem      255
Matching, 1-      17
Matching, b-      46 257 257—259 265
Matrix      2
Matrix norm      7 7—8
Matroid      210—218 211 305—306 311—313
Matroid intersection      214 214—218 306 310
Matroid polytope      213 213—218
Maurras, J.F.      282 342
Max-flow min-cut property      226 226—229 252
Max-flow min-cut theorem      199 237
Max-potential min-work theorem      234
Maximum (r, s)-cut problem      239
Maximum (r, s)-dicut problem      239
Maximum (r, s)-flow problem      197 236
Maximum cut problem      249
Maximum degree      230
Maximum degree problem      209
Maximum flow problem      197 236
Maximum norm      5
Maximum potential problem      234
Maximum-gain flow problem      241
Megiddo, N.      189 342
Membership oracle      54
Membership problem, strong      48 48—50 170—174
Membership problem, weak      51 51—55 56—58 61—63 102—122 128—132 170—174
Menger's Theorem      238
Menger, K.      25 238 342
Merkle, R.C.      221 331
Mertens, F.      149 343
Meyniel graph      281
Meyniel, H.      281 282 283 342
Micali, S.      255 342
Miller, R.E.      340
Min-potential max-work theorem      240
Minc, H.      1 342
Minimal face      183
1 2 3 4
blank
Реклама
blank
blank
HR
@Mail.ru
       © Электронная библиотека попечительского совета мехмата МГУ, 2004-2024
Электронная библиотека мехмата МГУ | Valid HTML 4.01! | Valid CSS! О проекте