Greedoids: Vol 4 (Algorithms and Combinatorics) - Tapa dura

Korte, Bernhard; Lovasz, Laszlo; Schrader, Rainer

 
9783540181903: Greedoids: Vol 4 (Algorithms and Combinatorics)
Tapa dura
ISBN 10: 3540181903 ISBN 13: 9783540181903
Editorial: Springer, 1991

Sinopsis

I. Introduction.- 1. Set Systems and Languages.- 2. Graphs, Partially Ordered Sets and Lattices.- II. Abstract Linear Dependence - Matroids.- 1. Matroid Axiomatizations.- 2. Matroids and Optimization.- 3. Operations on Matroids.- 4. Submodular Functions and Polymatroids.- III. Abstract Convexity - Antimatroids.- 1. Convex Geometries and Shelling Processes.- 2. Examples of Antimatroids.- 3. Circuits and Paths.- 4. Helly’s Theorem and Relatives.- 5. Ramsey-type Results.- 6. Representations of Antimatroids.- IV. General Exchange Structures - Greedoids.- 1. Basic Facts.- 2. Examples of Greedoids.- V. Structural Properties.- 1. Rank Function.- 2. Closure Operators.- 3. Rank and Closure Feasibility.- 4. Minors and Extensions.- 5. Interval Greedoids.- VI. Further Structural Properties.- 1. Lattices Associated with Greedoids.- 2. Connectivity in Greedoids.- VII. Local Poset Greedoids.- 1. Polymatroid Greedoids.- 2. Local Properties of Local Poset Greedoids.- 3. Excluded Minors for Local Posets.- 4. Paths in Local Poset Greedoids.- 5. Excluded Minors for Undirected Branchings Greedoids.- VIII. Greedoids on Partially Ordered Sets.- 1. Supermatroids.- 2. Ordered Geometries.- 3. Characterization of Ordered Geometries.- 4. Minimal and Maximal Ordered Geometries.- IX. Intersection, Slimming and Trimming.- 1. Intersections of Greedoids and Antimatroids.- 2. The Meet of a Matroid and an Antimatroid.- 3. Balanced Interval Greedoids.- 4. Exchange Systems and Gauss Greedoids.- X. Transposition Greedoids.- 1. The Transposition Property.- 2. Applications of the Transposition Property.- 3. Simplicial Elimination.- XI. Optimization in Greedoids.- 1. General Objective Functions.- 2. Linear Functions.- 3. Polyhedral Descriptions.- 4. Transversals and Partial Transversals.- 5. Intersection of Supermatroids.- XII. Topological Results for Greedoids.- 1. A Brief Review of Topological Prerequisites.- 2. Shellability of Greedoids and the Partial Tutte Polynomial.- 3. Homotopy Properties of Greedoids.- References.- Notation Index.- Author Index.- Inclusion Chart (inside the back cover).

"Sinopsis" puede pertenecer a otra edición de este libro.

Reseña del editor

With the advent of computers, algorithmic principles play an ever increasing role in mathematics. Algorithms have to exploit the structure of the underlying mathematical object, and properties exploited by algorithms are often closely tied to classical structural analysis in mathematics. This connection between algorithms and structure is in particular apparent in discrete mathematics, where proofs are often constructive, and can be turned into algorithms more directly. The principle of greediness plays a fundamental role both in the design of continuous algorithms (where it is called the steepest descent or gradient method) and of discrete algorithms. The discrete structure most closely related to greediness is a matroid; in fact, matroids may be characterized axiomatically as those independence systems for which the greedy solution is optimal for certain optimization problems (e.g. linear objective functions, bottleneck functions). This book is an attempt to unify different approaches and to lead the reader from fundamental results in matroid theory to the current borderline of open research problems. The monograph begins by reviewing classical concepts from matroid theory and extending them to greedoids. It then proceeds to the discussion of subclasses like interval greedoids, antimatroids or convex geometries, greedoids on partially ordered sets and greedoid intersections. Emphasis is placed on optimization problems in greedois. An algorithmic characterization of greedoids in terms of the greedy algorithm is derived, the behaviour with respect to linear functions is investigated, the shortest path problem for graphs is extended to a class of greedoids, linear descriptions of antimatroid polyhedra and complexity results are given and the Rado-Hall theorem on transversals is generalized. The self-contained volume which assumes only a basic familarity with combinatorial optimization ends with a chapter on topological results in connection with greedoids.

"Sobre este título" puede pertenecer a otra edición de este libro.

Editorial
Springer
Año de publicación
1991
Idioma
Inglés
ISBN 10 
3540181903
ISBN 13 
9783540181903
Encuadernación
Tapa dura
Número de páginas
228
Contacto del fabricante
no disponible
Persona responsable
CMN Printpool Inh. Mathis Neumann
https://www.also.com/ec/cms5/en_6000/6000/index.jsp

Friedrich-Karl-Str. 9
Hamburg
Alemania

Otras ediciones populares con el mismo título

9783642634994: Greedoids: 4 (Algorithms and Combinatorics)

Edición Destacada

ISBN 10:  3642634990 ISBN 13:  9783642634994
Editorial: Springer, 2012
Tapa blanda