| 书目名称 | Geometric Algorithms and Combinatorial Optimization | | 编辑 | Martin Grötschel,László Lovász,Alexander Schrijver | | 视频video | | | 丛书名称 | Algorithms and Combinatorics | | 图书封面 |  | | 描述 | Historically, there is a close connection between geometry and optImization. This is illustrated by methods like the gradient method and the simplex method, which are associated with clear geometric pictures. In combinatorial optimization, however, many of the strongest and most frequently used algorithms are based on the discrete structure of the problems: the greedy algorithm, shortest path and alternating path methods, branch-and-bound, etc. In the last several years geometric methods, in particular polyhedral combinatorics, have played a more and more profound role in combinatorial optimization as well. Our book discusses two recent geometric algorithms that have turned out to have particularly interesting consequences in combinatorial optimization, at least from a theoretical point of view. These algorithms are able to utilize the rich body of results in polyhedral combinatorics. The first of these algorithms is the ellipsoid method, developed for nonlinear programming by N. Z. Shor, D. B. Yudin, and A. S. NemirovskiI. It was a great surprise when L. G. Khachiyan showed that this method can be adapted to solve linear programs in polynomial time, thus solving an important open | | 出版日期 | Book 19881st edition | | 关键词 | Basis Reduction in Lattices; Basisreduktion bei Gittern; Combinatorics; Convexity; Ellipsoid Method; Elli | | 版次 | 1 | | doi | https://doi.org/10.1007/978-3-642-97881-4 | | isbn_ebook | 978-3-642-97881-4Series ISSN 0937-5511 Series E-ISSN 2197-6783 | | issn_series | 0937-5511 | | copyright | Springer-Verlag Berlin Heidelberg 1988 |
The information of publication is updating
|
|
发表于 2025-3-21 17:37:51
