Geometric Algorithms and Combinatorial Optimization

Martin Grötschel, Làszlo Lovàsz, Alexander Schrijver

362 pages, parution le 01/12/1994

Ajouter à une liste

Indisponible

Résumé

This book develops geometric techniques for proving the polynomial time solvability of problems in convexity theory, geometry, and, in particular, combinatorial optimization. It offers a unifying approach which is based on two fundamental geometric algorithms:

the ellipsoid method for finding a point in a convex set and
the basis reduction method for point lattices.

This book is a continuation and extension of previous research of the authors for which they received the Fulkerson prize, awarded by the Mathematical Programming Society and the American Mathematical Society. The first edition of this book was received enthusiastically by the community of discrete mathematicians, combinatorial optimizers, operations researchers, and computer scientists.

Contents

Mathematical Preliminaries

Complexity, Oracles, and Numerical Computation
Algorithmic Aspects of Convex Sets : Formulation of the Problems
The Ellipsoid Method
Algorithms for Convex Bodies
Diophantine Approximation and Basics Reduction
Rational Polyhedra
Combinatorial Optimization : Some Basic Examples
Combinatorial Optimization : A Tour d'Horizon
Stable Sets in Graphs
Submodular Functions

References
Index

L'auteur - Alexander Schrijver

CWI, Amsterdam, The Netherlands

Caractéristiques techniques

	PAPIER
Éditeur(s)	Springer
Auteur(s)	Martin Grötschel, Làszlo Lovàsz, Alexander Schrijver
Parution	01/12/1994
Nb. de pages	362
Format	17 x 25
Couverture	Relié
Poids	721g
Intérieur	Noir et Blanc
EAN13	9783540567400