Murota K. — Discrete convex analysis :: Электронная библиотека попечительского совета мехмата МГУ

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

Авторизация

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

Murota K. — Discrete convex analysis

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

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

Название: Discrete convex analysis

Автор: Murota K.

Аннотация:

Discrete Convex Analysis is a novel paradigm for discrete optimization that combines the ideas in continuous optimization (convex analysis) and combinatorial optimization (matroid/submodular function theory) to establish a unified theoretical framework for nonlinear discrete optimization. The study of this theory is expanding with the development of efficient algorithms and applications to a number of diverse disciplines like matrix theory, operations research, and economics. This self-contained book is designed to provide a novel insight into optimization on discrete structures and should reveal unexpected links among different disciplines. It is the first and only English-language monograph on the theory and applications of discrete convex analysis.

Язык:

Рубрика: Математика/

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

ed2k: ed2k stats

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

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

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

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

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

Optimality criterion, valuated matroid intersection      225
Optimality criterion, weighted matroid intersection      225
Optimality, global      2 9
Optimality, local      2 10
Optimization, combinatorial      3
Optimization, continuous      1
Optimization, discrete      3
Optimum, global      9
Optimum, local      10
Out of kilter      314
Pairing      79
parallel      62
Partial order, acyclic graph      107
Partial order, extreme base      108
Perfect matching      89
Perfect matching, minimum weight      89 266
Poisson equation      41 43 47
Polar cone      82
Polyhedral, ${L}^{\natural}$ -convex function      192
Polyhedral, ${M}^{\natural}$ -convex function      161
Polyhedral, convex function      25 80
Polyhedral, L-concave function      190
Polyhedral, L-convex function      190
Polyhedral, M-concave function      160
Polyhedral, M-convex function      160
Polyhedral, method      8
Polyhedron, ${L}^{\natural}$ -convex      129 131
Polyhedron, ${M}^{\natural}$ -convex      117 118
Polyhedron, base      105
Polyhedron, convex      78
Polyhedron, integral      90
Polyhedron, integral L-convex      131
Polyhedron, integral M-convex      118
Polyhedron, L-convex      123 131
Polyhedron, M-convex      108 118
Polyhedron, rational      90
Polyhedron, submodular      112
Polynomial matrix      71 354
Polynomial matrix, mixed      355
Polytope      90
Positive definite      39
Positive semidefinite      39
Positive support      18
Positively homogeneous, function      7 82
Positively homogeneous, L-convex function      193
Positively homogeneous, M-convex function      164
Potential      41 53 89 248
Potential, criterion      249 260 262
Potential, optimal      251
Primal integrality      252 261
Primal integrality, intersection theorem      20 114
Primal integrality, linear programming      89
Primal problem      87
Primal-dual algorithm      315
Principal minor      40
Principal submatrix      40
Principal submatrix, leading      40
producer      323
Production      323
Profit      324
Profit, function      324
Projection, ${M}_{2}$ -convex function      226
Projection, ${M}_{2}$ -convex set      117
Projection, base polyhedron      117
Projection, function to subset      143 162
Projection, M-convex function      134
Projection, M-convex polyhedron      118
Projection, M-convex set      102
Projection, polyhedral M-convex function      161
Proper convex function      77
Proximity theorem      156
Proximity theorem, ${L}_{2}$ -convex function      232
Proximity theorem, ${M}_{2}$ -convex function      228
Proximity theorem, L-convex function      186
Proximity theorem, M-convex function      156
Proximity theorem, quasi L-convex function      201
Proximity theorem, quasi M-convex function      174
Quadratic, ${L}^{\natural}$ -convex function      48 52 182
Quadratic, ${M}^{\natural}$ -convex function      48 52 139
Quadratic, form      39
Quadratic, function      39
Quadratic, L-convex function      182
Quadratic, M-convex function      139
Quasi convex      168
Quasi convex, semistrictly      168
Quasi L-convex function      199
Quasi L-optimality criterion      201
Quasi L-proximity theorem      201
Quasi linear      324
Quasi M-convex function      169
Quasi M-minimizer cut      174
Quasi M-minimizer cut, with scaling      175
Quasi M-optimality criterion      173
Quasi M-proximity theorem      174
Quasi submodular      198
Quasi submodular, semistrictly      198
Quasi-separable, concave function      334
Quasi-separable, convex function      140
Rank function, matrix      69
Rank function, matroid      70
Rational polyhedron      90
Reduced cost      249 251
Relative interior      78
Reservation value function      325
Resistance      41
Resolvent      45
Resource allocation problem      4 176
Restriction, ${L}_{2}$ -convex function      229
Restriction, ${L}_{2}$ -convex set      129
Restriction, function to interval      92
Restriction, function to subset      143 162
Restriction, L-convex function      178
Restriction, L-convex polyhedron      131
Restriction, L-convex set      121
Restriction, polyhedral L-convex function      192
Rigidity      361
Ring family      104 107 292

Saddle-point theorem      238
Scaling      145
Scaling algorithm, L-convex function      308
Scaling algorithm, M-convex function      283 287
Scaling algorithm, M-convex submodular flow      320
Scaling, conjugate      319
Scaling, cost      318
Scaling, domain      145
Scaling, nonlinear      170 199
Semigroup      45
Semistrictly quasi convex      168
Semistrictly quasi L-convex      199
Semistrictly quasi M-convex      169
Semistrictly quasi submodular      198
Separable concave function      333
Separable concave function, quasi      334
Separable convex function      10 95 140 182
Separable convex function, quasi      140
Separable convex function, with chain condition      182
Separation theorem, convex function      2 11 84
Separation theorem, convex set      35 83
Separation theorem, generic discrete      13 216
Separation theorem, L-convex function      218
Separation theorem, L-convex set      36 126
Separation theorem, M-convex function      217
Separation theorem, M-convex set      36 114
Separation theorem, submodular function      17 111
Series      62
Seudopolynomial algorithm      288
Simple cycle      62
Single improvement property      332
Spanning tree      149
Stable marriage problem      345
Stable matching problem      345
Steepest descent algorithm, L-convex function      305 306
Steepest descent algorithm, M-convex function      281
Steepest descent scaling algorithm, L-convex function      308
Steepest descent scaling algorithm, M-convex function      283
Stepwise gross substitutes property      155 331
Stoichiometric coefficient      350
Strictly convex function      77
Strong duality      87
Strong no complementarities property      332
Strongly polynomial algorithm      288
Structural equation      54 349
Subdeterminant      40 359
Subdifferential      80
Subdifferential, concave function      217
Subdifferential, discrete function      166
Subdifferential, integer      166
Subgradient      80
Subgradient, discrete function      166
Sublattice      104
Submatrix leading principal      40
Submodular      62 206
Submodular flow problem      255
Submodular flow problem, economic equilibrium      341
Submodular flow problem, feasibility theorem      258
Submodular flow problem, M-convex      256
Submodular flow problem, maximum      259
Submodular function minimization, IFF fixing algorithm      300
Submodular function minimization, IFF scaling algorithm      298 299
Submodular function minimization, Schrijver's algorithm      293
Submodular, function      16 44 70 104
Submodular, function on distributive lattice      292
Submodular, integrally convex-function      7 189
Submodular, polyhedron      20 112
Submodular, utility function      330
Submodularity      44 177 190
Submodularity, inequality      16 44 177
Submodularity, local      180
Substitutes      62
Successive shortest path algorithm      312
Sum, of functions      80
Sum, of M-convex functions      226
Supermodular      16 62 105 145 206
Supermodular, function      105
Supply, correspondence      324
Supply, set      324
Support, function      82
Support, negative      18
Support, positive      18
System parameter      347
Tension      53
Tension, another convention      253
Terminal vertex      52 53
Tight set      108
Transformation by network      269
Transformation by network, of flow type      269
Transformation by network, of potential type      269
Transitive      107 119
Translation submodularity      23 44 178
Triangle inequality      24 122
Two-stage algorithm      310
Unimodular totally      88
Unique-min condition      266
Unit contraction      45
Unit demand preference      334
Univariate function      10
Univariate function, discrete convex      95
Univariate function, polyhedral convex      80
Utility function      324
Valuated matroid      7 72 225
Valuated matroid, intersection problem      225
Valuation      72
Variational formulation      43 55
Vertex      52
Vertex, initial      53
Vertex, terminal      53
Voltage      41 53
Voltage potential      55
Weak duality      87
Weak exchange axiom      137
Weakly polynomial algorithm      288
Weight splitting, matroid intersection      34 225
Weight splitting, valuated matroid intersection      225
z-transform      355

1 2 3

О проекте