Geometric Algorithms and Combinatorial Optimization (Springer Series in Computational Mathematics) by Martin Gr鰐schel
Publisher:Springer (January 1988) | ISBN: 038713624X | Pages: 362 | DJVU | 4.48 MB
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 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. The ellipsoid method was used by Khachiyan to show the polynomial time solvability of linear programming. The basis reduction method yields a polynomial time procedure for certain diophantine approximation problems.
发表于 2011-2-19 08:31:38