Algebraic and Combinatorial Methods in Operations ResearchR.E. Burkard, R.A. Cuninghame-Green, U. Zimmermann For the first time, this book unites different algebraic approaches for discrete optimization and operations research. The presentation of some fundamental directions of this new fast developing area shows the wide range of its applicability. Specifically, the book contains contributions in the following fields: semigroup and semiring theory applied to combinatorial and integer programming, network flow theory in ordered algebraic structures, extremal optimization problems, decomposition principles for discrete structures, Boolean methods in graph theory and applications. |
Contents
| 1 | |
| 23 | |
Chapter 3 A dual optimality criterion for algebraic linear programs | 35 |
Chapter 4 On properties of solution sets of extremal linear programs | 41 |
Chapter 5 Using fields for semiring computations | 55 |
Chapter 6 Scheduling by noncommutative algebra | 75 |
Chapter 7 Pseudoboolean functions and stability of graphs | 83 |
Chapter 8 Independence systems and perfect kmatroidintersections | 99 |
a survey of recent results | 147 |
Chapter 13 Algebraic flows and timecost tradeoff problems | 165 |
Chapter 14 Ranking the cuts and cutsets of a network | 183 |
Chapter 15 Shortest paths in signed graphs | 201 |
Chapter 16 A boolean algebraic analysis of fire protection | 215 |
Chapter 17 Iteration and summability in semirings | 229 |
Chapter 18 Substitution decomposition for discrete structures and connections with combinatorial optimization | 257 |
Chapter 19 On maxseparable optimization problems | 357 |
Chapter 9 Matroids on ordered sets and the greedy algorithm | 115 |
Chapter 10 An algorithm for the unbounded matroid intersection polyhedron | 129 |
Chapter 11 Algebraic Flows | 135 |
Chapter 20 Minimization of combined objective functions on integral submolar flows | 363 |
Other editions - View all
Common terms and phrases
algebraic flow algebraic structures Annals of Discrete applications arbitrary arcs assume augmenting path autonomous sets Boolean functions bounds called classes clique clutters combinatorial optimization comparability graph composition series composition tree computation congruence partition consider convex corresponding cut-set defined denote dioids Discrete Mathematics dual element example exists feasible solution finite given Gondran graph G greedy algorithm Hence homomorphisms idempotent implies independence system integral isomorphic iteration Lemma linear programs Math matrix matroids maximal method negative circuit network flow nodes objective function obtained Operations Research optimization problems partial orders partition lattices polymatroids polynomial project networks Proof properties quotient rank function relations s-t nets satisfying Section semigroup semiring set systems signed graphs solve split decomposition submodular flows subset substitution decomposition Theorem theory variables vector vertex vertices weight Zimmermann