Geometric Algorithms and Combinatorial Optimization

摘要: This book develops geometric techniques for proving the polynomial time solvability of problems in convexity theory, geometry, and - particular combinatorial optimization. It offers a unifying approach based on two fundamental algorithms: ellipsoid method finding point convex set basis reduction lattices. The was used by Khachiyan to show linear programming. yields procedure certain diophantine approximation problems. A combination these makes it possible many questions concerning poyhedra instance, programming having possibly exponentially inequalities. Utilizing results from polyhedral combinatorics, provides short proofs poynomial combinatiorial optimization For number problems, algorithms discussed this are only known derive solvability. is continuation extension previous research authors which they received Fulkerson Prize, awarded Mathematical Programming Society American Society.