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

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

Feasible, $\delta -$       296
Feasible, dual problem      236
Feasible, flow      247 258
Feasible, minimum cost flow problem      247
Feasible, potential      122
Feasible, primal problem      235
Feasible, set      1
Feasible, submodular flow problem      258
Fenchel duality      12 85
Fenchel transformation      81
Fenchel-type duality, generic form      13
Fenchel-type duality, L-convex function      32 222
Fenchel-type duality, M-convex function      32 222
Fenchel-type duality, submodular function      225
Fixed constant      347
Flow      53
Flow, $\delta$ -feasible      296
Flow, feasible      247 258
Frank's discrete separation theorem      17 111
Frank's discrete separation theorem, (as special case of L-separation)      33 224
Frank's weight-splitting theorem      34 225
Fully combinatorial algorithm      290
Fundamental circuit      149
g-polymatroid      117
Generalized polymatroid      117
Generator      45
Global minimizer      79
Global optimality      2
Global optimum      9
Goods, divisible      327
Goods, indivisible      323
Gradient      80
Graph, acyclic      107
Graph, bipartite      89
Graph, directed      52 88
Grassmann — Plucker relation      69
Greedy algorithm      3 108
Gross substitutes property      153 331
Gross substitutes property, stepwise      155 331
Ground set      70
Gyrator      361
Hamiltonian path problem      257
Hole free      90
Ideal      107
IFF fixing algorithm      300
IFF scaling algorithm      298 299
In kilter      314
Inaccurate number      347
Incidence, chain      88
Incidence, graph      88
Incidence, topological      347
Income      324
Independent set, matrix      68
Independent set, matroid      70
Indicator function      79 90
Indivisible commodity      323
Indivisible goods      323
Infimal convolution      80
Infimal convolution, by network transformation      272
Infimal convolution, integer      143
Initial endowment      324
Initial endowment, total      326
Initial vertex      53
Inner product      79
Integer biconjugate      212
Integer infimal convolution      143
Integer interval      92
Integer subdifferential      166
Integral base polyhedron      18
Integral L-convex polyhedron      131
Integral M-convex polyhedron      118
Integral neighborhood      93
Integral polyhedral, ${L}^{\natural}$ -convex function      192
Integral polyhedral, ${M}^{\natural}$ -convex function      162
Integral polyhedral, convex function      161
Integral polyhedral, L-convex function      191
Integral polyhedral, M-convex function      161
Integral polyhedron      90
Integrality, dual      161 252 261
Integrality, linear programming      89
Integrality, minimum cost flow problem      252
Integrality, polyhedral convex function      161
Integrality, polyhedral L-convex function      191
Integrality, polyhedral M-convex function      161
Integrality, polyhedron      90
Integrality, primal      252 261
Integrality, submodular flow problem      261
Integrally concave function      94
Integrally convex function      7 94
Integrally convex function, submodular      189
Integrally convex set      96
Intersection theorem, Edmonds's      3 20 112
Intersection theorem, Edmonds's (as special case of Fencheltype duality)      34 224
Intersection theorem, M-convex      219
Intersection theorem, valuated matroid      225
Intersection theorem, weighted matroid      225
Intersection, convexity in      92
Intersection, M-convex      219
Intersection, matroid      3
Intersection, submodular polyhedron      20
Intersection, valuated matroid      225
Interval, closed      77
Interval, integer      92
Interval, open      77
Jump system      120
Kilter, diagram      53 251
Kilter, in      314
Kilter, out of      314
Kirchhoff's law      349
Kirchhoff's law, current      353
Kirchhoff's law, voltage      353
Koenig — Egervary theorem for mixed matrix      358
L-concave function      22
L-concave function, polyhedral      190
L-convex cone      131
L-convex function      8 22 177
L-convex function, dual-integral polyhedral      191
L-convex function, integral polyhedral      191
L-convex function, polyhedral      190
L-convex function, positively homogeneous      193
L-convex function, quadratic      52 182
L-convex function, quasi      199
L-convex function, semistrictly quasi      199
L-convex polyhedron      123 131
L-convex polyhedron, integral      131
L-convex set      22 121
L-optimality criterion      185 193
L-optimality criterion, quasi      201
L-proximity theorem      186
L-proximity theorem, quasi      201
L-separation theorem      33 218
Lagrange duality      234
Lagrangian function      236
Lagrangian function, dual      242
Laminar convex function      141
Laminar convex function, by network transformation      273
Laminar family      141
Laplace transform      351
Lattice      292
Lattice, distributive      292
Lattice, sub-      104
Leading principal minor      40
Leading principal submatrix      40
Leaving arc      52
Legendre transformation      81
Legendre — Fenchel transform, concave      11 81
Legendre — Fenchel transform, convex      10 81
Legendre — Fenchel transform, discrete      13 212
Legendre — Fenchel transformation, concave      11 81
Legendre — Fenchel transformation, convex      10 81

Legendre — Fenchel transformation, discrete      13 212
Level set      172
Linear extension, partial order      108
Linear extension, set function      16 104
Linear order      108
Linear program      87
Linear program, dual problem      87
Linear program, primal problem      87
Linear programming      86
Linear programming, duality      87
Linearity in direction      1 177 190
Local convex extension      93
Local optimality      2
Local optimum      10
Lovasz extension      16 104 111
lp      87
LP, duality      87
M-concave function      8 26
M-concave function, polyhedral      160
M-convex cone      119
M-convex function      8 26 133
M-convex function, dual-integral polyhedral      161
M-convex function, integral polyhedral      161
M-convex function, polyhedral      160
M-convex function, positively homogeneous      164
M-convex function, quadratic      52 139
M-convex function, quasi      169
M-convex function, semistrictly quasi      169
M-convex intersection, problem      219 264
M-convex intersection, theorem      219
M-convex polyhedron      108 118
M-convex polyhedron, integral      118
M-convex program      235
M-convex set      27 101
M-convex submodular flow problem      256
M-convex submodular flow problem, economic equilibrium      341
M-matrix      42
M-minimizer cut      149
M-minimizer cut, with scaling      158
M-optimality criterion      148 163
M-optimality criterion, quasi      173
M-proximity theorem      156
M-proximity theorem, quasi      174
M-separation theorem      33 217
Markovian      45
Matching      89
Matching, bipartite      89
Matching, perfect      89
Matching, weighted      89 266
Mathematical programming      1
Matrix, compartmental      43
Matrix, incidence (chain)      88
Matrix, incidence (graph)      88
Matrix, M-      42
Matrix, mixed      354
Matrix, mixed polynomial      355
Matrix, mixed skew-symmetric      361
Matrix, node admittance      42
Matrix, polynomial      71 354
Matrix, positive-definite      39
Matrix, positive-semidefinite      39
Matrix, principal sub-      40
Matrix, totally unimodular      88
Matroid      70
Matroid, induction through a graph      270
Matroid, intersection problem      34 225
Matroid, valuated      72
Max-fiow min-cut theorem for submodular flow      259
Maximum submodular flow problem      259
Maximum weight circulation problem      61
Mechanical system      350
Midpoint convexity      9
Midpoint convexity, discrete function      23 180
Midpoint convexity, discrete set      129
Miller's discrete convex function      98
Min-max relation      2
Minimizer      79
Minimizer cut, M-convex function      149
Minimizer cut, M-convex function with scaling      158
Minimizer cut, quasi M-convex function      174
Minimizer cut, quasi M-convex function with scaling      175
Minimizer, ${L}_{2}$ -convex function      232
Minimizer, ${M}_{2}$ -convex function      227 228
Minimizer, global      9 79
Minimizer, integrally convex function      94
Minimizer, L-convex function      185 305
Minimizer, local      10
Minimizer, M-convex function      148 281
Minimizer, maximal      290 291 304 307
Minimizer, minimal      290 291 305 307
Minimizer, submodular set function      288
Minimum cost flow problem      53 245
Minimum cost flow problem, integer flow      246
Minimum cut      316
Minimum spanning tree problem      149
Minkowski sum      80 90
Minkowski sum, convexity in      92
Minkowski sum, discrete      90
Minkowski sum, integral      90
Minor      40 359
Minor, leading principal      40
Minor, principal      40
Mixed matrix      354
Mixed polynomial matrix      355
Mixed skew-symmetric matrix      361
money      323
Monotonicity      54
Multimodular function      183
Multiple exchange axiom      333
Multiterminal electrical network      53
Negative cycle      122 252 263
Negative cycle, criterion      252 263 264
Negative support      18
Neighborhood, integral      93
Network      53
Network flow, duality      268
Network flow, electrical network      41 43
Network flow, L-convexity      24 31 56 58 270
Network flow, M-convexity      28 31 56 58 270
Network flow, maximum weight circulation      61
Network flow, minimum cost flow      245
Network flow, multiterminal      53
Network flow, submodular flow      255
Network, auxiliary      252 263
Network, electrical      53
Network, transformation by      270
No complementarities property      332
No complementarities property, strong      332
Node      52
Node admittance matrix      42
Normal contraction      45
Objective function      1
Off-diagonal nonpositivity      41
Open interval      77
Optimal potential      89 251
Optimal value function      236
Optimality criterion, ${L}_{2}$ -convex function      232
Optimality criterion, ${M}_{2}$ -convex function      219 227 228
Optimality criterion, by negative cycle      252 263 264
Optimality criterion, by potential      249 260 262
Optimality criterion, integrally convex function      94 95
Optimality criterion, L-convex function      185 193
Optimality criterion, M-convex function      148 163
Optimality criterion, M-convex submodular flow      262—264
Optimality criterion, minimum cost flow      249 252
Optimality criterion, quasi L-convex function      201
Optimality criterion, quasi M-convex function      173
Optimality criterion, submodular flow      260
Optimality criterion, submodular set function      185
Optimality criterion, sum of M-convex functions      219

1 2 3

О проекте