Lee J., Davis S.H. (Ed), Ablowitz M.J. (Ed) — First Course in Combinatorial Optimization :: Электронная библиотека попечительского совета мехмата МГУ

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

Авторизация

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

Lee J., Davis S.H. (Ed), Ablowitz M.J. (Ed) — First Course in Combinatorial Optimization

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

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

Название: First Course in Combinatorial Optimization

Авторы: Lee J., Davis S.H. (Ed), Ablowitz M.J. (Ed)

Аннотация:

For advanced undergraduate or graduate level students with some elementary notions from graph theory, this text is intended as a rigorous, enticing introduction to be used in a one-semester course. Without attempting comprehensiveness and touching only lightly on applications, Lee (IBM T.J. Watson Research Center) discusses linear and integer programming, polytopes, matroids and matroid optimization, shortest paths, and network flows. He emphasizes the unifying roles of matroids, submodularity, and polyhedral combinatorics, and does not dwell on data structures and implementation details. Problems and exercises are included throughout.

Язык:

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

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

ed2k: ed2k stats

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

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

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

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

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

(Weighted) Greedy Algorithm      57
(Weighted) Matroid-Intersection Algorithm      102
2-factor inequalities and Chvatal — Gomory cutting planes      174
Algorithmic proof of Koenig's Theorem      117
Augmenting paths      140
Augmenting-Path Procedure      141
Backtracking Procedure      142
Base polytope      73
Base polytope with a coloop      73
Bellman — Ford algorithm      76
Bellman-Ford algorithm      76
Berge's theorem      107
Big right-hand side      187
Bipartite matching      85
Branch-&-Bound      182
Branch-&-Bound using group relaxation      185
Branch-&-Bound using linear-programming relaxation      180
Cardinality Greedy Algorithm      56
Cardinality Matroid-Intersection Algorithm      96
Christofides's Heuristic      131 132
Christofides's Theorem      131
Chvatal — Gomory cutting planes      153 154
Circuit elimination      52
Clique separation      169
Closure      62
Cocircuits and coloops      65
Comb      174
Comparing relaxations      6
Convexity of f' and integer-valued minima      195
Correctness for odd submodular minimization      199
Correctness of Edmonds's Cardinality Matching Algorithm      117
Correctness of labels for Dijkstra's Algorithm      79
Correctness of the Cardinality Matroid-Intersection Algorithm      96
Cover separation      168
Cuts      61
Dijkstra's algorithm      79
Dijkstra's Theorem      81
Dimension Theorem      29
Direct sum      50
Directed Hamiltonian tours      89
Disjoint odd-set cover      113
Dual graphic matroids and planar graphs      66
Dual of a linear matroid      64
Dual rank function      64
Dual solution      69
Edmonds — Johnson Minimum-Weight T-Join Algorithm      129
Edmonds — Karp labeling      144
Edmonds — Karp Theorem      143
Edmonds's Maximum-Cardinality Matching Algorithm      115
Epsilon-Perturbed Dual Simplex Method      40
Euler's theorem      129
Exponential example for Branch-&-Bound      184
Facets of a matching polytope      112
Facets of a matroid polytope      71
Fano representation      54
Farkas lemma      13 14
Feasible basic solutions and extreme points      27
Finding a feasible v-w flow      146
Finding a negative-weight dicycle      77
Finding violated cover inequalities      168
Finiteness and efficiency of Edmonds's Cardinality Matching Algorithm      116
Finiteness of Gomory's Cutting-Plane Method      165
Flow across a cut      139
Floyd — Warshall Algorithm      78
Forest components      50
Forest of repeated edges      130
Generic Cutting-Plane Method      152
Generic rigidity in the plane      86 93 96 97 99
Gomory cuts are Chvatal — Gomory cuts      159
Gomory cutting planes      157 158 159
Gomory's Cutting-Plane Method      159
Graphic $\Rightarrow$ linear over GF(2)      51
Graphic circuit elimination      53
Graphic matroid      50
Graphic unique circuit      53
Greedy characterization of matroids      60
Greedy optimality for matroids      57
Greedy optimality for polymatroids      70
Hall's theorem      45
Incapacitated facility location and submodular maximization      201
Integrality implies unimodularity      42
Intersection of three matroid poly topes      106
Knapsack program      82 183
Knapsack program using group relaxation      187
Koenig's Theorem      146
Konig's theorem      146 44
Kuhn's Assignment Algorithm      107 123
Lagrangian relaxation      38
Lagrangian Relaxation Theorem      36
Linear circuit elimination      52
Linear matroid      50
Linear over GF(2) $\nRightarrow$ graphic      54
Linear unique circuit      53
Linear-programming proof of the Max-Flow/Min-Cut Theorem      146

Matching      117
Matching and Chvatal — Gomory cutting planes      154
Matching Duality Theorem      113 121
Matching matroid      108
Matching-Polylope Theorem      109
Matroid duality      63
Matroid partitioning      100
Matroid polytope      67
Matroid-Intersection Duality Theorem      99
Matroid-Intersection Polytope      103
Max-Flow/Min-Cut Theorem      146
Maximum-cardinality matching and submodular maximization      200
Maximum-cardinality matching in a shrunken graph      116
Maximum-cardinality matroid intersection and submodular minimization      195
Maximum-cardinality p-matroid intersection and submodular maximization      200
Maximum-entropy sampling and Branch-&-Bound      192
Maximum-Flow Algorithm      142
Maximum-Row Algorithm      141
Maximum-weight spanning tree      58 60 65
Minimum-weight cuts and submodular minimization      195
Minimum-weight dipaths by linear programming      77
Minimum-weight dipaths in graphs with no dicycles      81
Minimum-weight even path      126
Minkowski's Theorem (for polytopes)      30
Minors of matroids      66
Mismatching matroid      109
Mixed-integer cuts      155
Monotonicity of labels in the Maximum-Flow Algorithm      144
Motion      86 87
Necessity of facets      32
Necessity of weight splitting      20
Nonrepresenlable matroids      56
Odd-cycle separation      175
Piecewise-linear functions      7
Planar dual      65
Planar generic rigidity      88
Postperson's tour      130
Primal Simplex Method      23
Rank characterization of matroids      62
Recovering the dipaths with Dijkstra's Algorithm      81
Recovering the dipaths with the Bellman — Ford Algorithm      77
Recovering the dipaths with the Floyd — Warshall Algorithm      78
Redundancy Theorem      30
Scheduling      59 65 99 108
Sensitivity Theorem      28
Separation Algorithm for Sublour-Elimination Inequalities      172
Separations      100
Shifting the objective for T-joins      128
Shortcut      95
Shortest implies augmenting      94
Shrinking      114
Strong Complementary-Slackness Theorem      18
Strong duality for flows and the stopping criterion of the Maximum-Flow Algorithm      142
Strong duality theorem      15
Strong Optimal-Basis Theorem      27
Structure of repeated edges      128
Subdifferential for the Lagrangian      39 40
Subgradient method      23
Submodular minimization over odd sets      198
Submodularity of matroid rank function      61
Sufficiency of weight splitting      19
Swapping Algorithm      60
Symmetric difference for T-joins      128
T-joins in the planar dual and cuts      148
The Dual Simplex Method      40
The intersection of two matroids need not be a matroid      84
Theorem of the Alternative for Linear Inequalities      12 17
Transformation to nonnegative weights for T-joins      128
Tutte's Perfect-Matching Theorem      114
Unbounded integer program      165
Uncapacitated facility location      6 155
Uniform matroid      50
Unimodularity and connections      43
Unimodularity and consecutive ones      46
Unimodularity and digraphs      44
Unimodularity and pivoting      43
Unimodularity implies integrality      41
Unique circuit      53
Unique Description Theorem      33
Validity of 2-factor inequalities      174
Vertex packing and Chvatal — Gomory      155
Vertex packing and submodular maximization      201
Vertex packing in bipartite graphs      146
Vertex packing on a star      51 53 57 61 69
Violated 2-factor inequality      174
w-tree relaxation      188
w-tree-based Branch-&-Bound      189
Weak Complementary-Slackness Theorem      18
Weak duality for flows      140
Weak duality theorem      14
Weak Optimal-Basis Theorem      22
Weighted matching      112
Weyl's Theorem (for polytopes)      11
Workforce planning      47
Worst case for Christofides's Heuristic      135

О проекте