Martin Grötschel – författare

The Sharpest Cut is written in honor of Manfred Padberg, who has made fundamental contributions to both the theoretical and computational sides of integer programming and combinatorial optimization. This outstanding collection presents recent results in these areas that are closely connected to Padberg's research. His deep commitment to the geometrical approach to combinatorial optimization can be felt throughout this volume; his search for increasingly better and computationally efficient cutting planes gave rise to its title.The peer-reviewed papers contained here are based on invited lectures given at a workshop held in October 2001 to celebrate Padberg's 60th birthday. Grouped by topic (packing, stable sets, and perfect graphs; polyhedral combinatorics; general polytopes; semidefinite programming; computation), many of the papers set out to solve challenges set forth in Padberg’s work. The book also shows how Padberg's ideas on cutting planes have influenced modern commercial optimization software. In addition, the volume contains a short curriculum vitae, a personal account of Padberg’s work by Laurence Wolsey, and an appendix with reflections from Egon Balas, Claude Berge, and Harold Kuhn.Manfred Padberg was Research Professor, Stern School of Business, New York University until 2002. Over the course of his career he received many honors for his work, including the Lanchester Prize, Dantzig Prize, and the John von Neuman Theory Prize. He has published six books and over 100 articles.

Whether costs are to be reduced, profits to be maximized, or scarce resources to be used wisely, optimization methods are available to guide decision making. In online optimization the main issue is incomplete data, and the scientific challenge: How well can an online algorithm perform? Can one guarantee solution quality, even without knowing all data in advance? In real-time optimization there is an additional requirement, decisions have to be computed very fast in relation to the time frame of the instance we consider. Online and real-time optimization problems occur in all branches of optimization. These areas have developed their own techniques but they are addressing the same issues: quality, stability, and robustness of the solutions. To fertilize this emerging topic of optimization theory and to foster cooperation between the different branches of optimization, the Deutsche Forschungsgemeinschaft (DFG) has supported a Priority Programme "Online Optimization of Large Systems".

Discrete mathematics and theoretical computer science are closely linked research areas with strong impacts on applications and various other scientific disciplines. Both fields deeply cross fertilize each other. One of the persons who particularly contributed to building bridges between these and many other areas is László Lovász, a scholar whose outstanding scientific work has defined and shaped many research directions in the last 40 years. A number of friends and colleagues, all top authorities in their fields of expertise and all invited plenary speakers at one of two conferences in August 2008 in Hungary, both celebrating Lovász’s 60th birthday, have contributed their latest research papers to this volume. This collection of articles offers an excellent view on the state of combinatorics and related topics and will be of interest for experienced specialists as well as young researchers.

Whether costs are to be reduced, profits to be maximized, or scarce resources to be used wisely, optimization methods are available to guide decision making. In online optimization the main issue is incomplete data, and the scientific challenge: How well can an online algorithm perform? Can one guarantee solution quality, even without knowing all data in advance? In real-time optimization there is an additional requirement, decisions have to be computed very fast in relation to the time frame of the instance we consider. Online and real-time optimization problems occur in all branches of optimization. These areas have developed their own techniques but they are addressing the same issues: quality, stability, and robustness of the solutions. To fertilize this emerging topic of optimization theory and to foster cooperation between the different branches of optimization, the Deutsche Forschungsgemeinschaft (DFG) has supported a Priority Programme "Online Optimization of Large Systems".

Discrete mathematics and theoretical computer science are closely linked research areas with strong impacts on applications and various other scientific disciplines. Both fields deeply cross fertilize each other. One of the persons who particularly contributed to building bridges between these and many other areas is László Lovász, a scholar whose outstanding scientific work has defined and shaped many research directions in the last 40 years. A number of friends and colleagues, all top authorities in their fields of expertise and all invited plenary speakers at one of two conferences in August 2008 in Hungary, both celebrating Lovász’s 60th birthday, have contributed their latest research papers to this volume. This collection of articles offers an excellent view on the state of combinatorics and related topics and will be of interest for experienced specialists as well as young researchers.

Mathematics as a production factor or driving force for innovation? Those, who want to know and understand why mathematics is deeply involved in the design of products, the layout of production processes and supply chains will find this book an indispensable and rich source.

Since the publication of the first edition of our book, geometric algorithms and combinatorial optimization have kept growing at the same fast pace as before. Nevertheless, we do not feel that the ongoing research has made this book outdated. Rather, it seems that many of the new results build on the models, algorithms, and theorems presented here. For instance, the celebrated Dyer-Frieze-Kannan algorithm for approximating the volume of a convex body is based on the oracle model of convex bodies and uses the ellipsoid method as a preprocessing technique. The polynomial time equivalence of optimization, separation, and membership has become a commonly employed tool in the study of the complexity of combinatorial optimization problems and in the newly developing field of computational convexity. Implementations of the basis reduction algorithm can be found in various computer algebra software systems. On the other hand, several of the open problems discussed in the first edition are still unsolved. For example, there are still no combinatorial polynomial time algorithms known for minimizing a submodular function or finding a maximum clique in a perfect graph. Moreover, despite the success of the interior point methods for the solution of explicitly given linear programs there is still no method known that solves implicitly given linear programs, such as those described in this book, and that is both practically and theoretically efficient. In particular, it is not known how to adapt interior point methods to such linear programs.