Michael Jünger - Böcker

AlegendsaysthatJackEdmondsshouted"Eureka-youshrink!"whenhefound a good characterization for matching (and the matching algorithm) in 1963, the daybeforehistalkatasummerworkshopatRANDCorporationwithcelebrities like George Dantzig, Ralph Gomory, and Alan Ho?man in the audience. During Aussois 2001, Jack con?rmed: "'Eureka - you shrink!' is really true, except that instead of 'Eureka' it maybe was some less digni?ed word." Aussois 2001 was the ?fth in an annual series of workshops on combinatorial optimization that are alternately organized by Thomas Liebling, Denis Naddef, andLaurenceWolsey-theinitiatorsofthisseries-inevenyearsandtheeditors of this book in odd years (except 1997). We decided to dedicate Aussois 2001 to Jack Edmonds in appreciation of his groundbreaking work that laid the foundations of much of what combinatorial optimizers have done in the last 35 years. Luckily, Jack is a regular participant of the Aussois workshops and, as ever, he cares a lot for young combinatorial optimizers who traditionally play a major r ole in the Aussois series. Fig.1.Handout for the Aussois 2001 participants VI Preface Highlights of Aussois 2001 included a special session entitled "Eureka - you shrink!" in honor of Jack and a special lecture by Jack on "Submodular Fu- tions, Matroids, and Certain Polyhedra" that closed the workshop. In this book, we give an account of the "Eureka - you shrink!" session as well as reprints of three hardly accessible papers that Jack gave as a handout to the Aussois 2001 participants and that were originally published in theProceedings oftheCalgaryInternationalConferenceonCombinatorialStructuresandTheir Applications 1969, Gordon and Breach (1970) - newly typeset by the editors and reprinted by permission.

Automatic Graph Drawing is concerned with the layout of relational structures as they occur in Computer Science (Data Base Design, Data Mining, Web Mining), Bioinformatics (Metabolic Networks), Businessinformatics (Organization Diagrams, Event Driven Process Chains), or the Social Sciences (Social Networks).In mathematical terms, such relational structures are modeled as graphs or more general objects such as hypergraphs, clustered graphs, or compound graphs. A variety of layout algorithms that are based on graph theoretical foundations have been developed in the last two decades and implemented in software systems.After an introduction to the subject area and a concise treatment of the technical foundations for the subsequent chapters, this book features 14 chapters on state-of-the-art graph drawing software systems, ranging from general "tool boxes'' to customized software for various applications. These chapters are written by leading experts, they follow a uniform scheme and can be read independently from each other.

Since its start in 1990, the IPCO conference series (held under the auspices of theMathematicalProgrammingSociety)hasbecomeanimportantforumforthe presentation of recent results in Integer Programming and Combinatorial Op- mization. This volume compiles the papers presented at IPCO XI, the eleventh conference in this series, held June 8–10, 2005, at the Technische Universit¨ at Berlin. The high interest in this conference series is evident in the large number of submissions. For IPCO XI, 119 extended abstracts of up to 10 pages were submitted. During its meeting on January 29–30, 2005, the Program Committee carefully selected 34 contributions for presentation in non-parallel sessions at the conference. The ?nal choices were not easy at all, since, due to the limited number of time slots, many very good papers could not be accepted. During the selection process the contributions were refereed according to the standards of refereed conferences. As a result of this procedure, you have in your hands a volume that contains papers describing high-quality research e?orts. The page limit for contributions to this proceedings volume was set to 15. You may ?nd full versions of the papers in scienti?c journals in the near future. We thank all the authors who submitted papers. Furthermore, the Program Committee is indebted to the many reviewers who, with their speci?c expertise, helped a lot in making the decisions.

This tutorial contains written versions of seven lectures on Computational Combinatorial Optimization given by leading members of the optimization community. The lectures introduce modern combinatorial optimization techniques, with an emphasis on branch and cut algorithms and Lagrangian relaxation approaches. Polyhedral combinatorics as the mathematical backbone of successful algorithms are covered from many perspectives, in particular, polyhedral projection and lifting techniques and the importance of modeling are extensively discussed. Applications to prominent combinatorial optimization problems, e.g. , in production and transport planning, are treated in many places; in particular, the book contains a state-of-the-art account of the most successful techniques for solving the traveling salesman problem to optimality.

With 133 registered participants from 27 countries, including 19 participants fromindustry,theInternationalSymposiumonGraphDrawing2001(GD2001) that took place in Vienna, September 23-26, 2001, clearly demonstrated that the graph drawing community is still growing. The 31 contributed talks that hadbeenselectedoutof66papersubmissionsbytheprogramcommitteere?ect themanyfacetsofgraphdrawingandthehighactivityinourscienti?cdiscipline. In addition, we had the pleasure of enjoying invited presentations by Alexander Schrijver and Eduard Gr. oller that mark extreme points of the wide spectrum of graph drawing, the mathematical foundations and the computer graphics, respectively.Wehavecompiledthewrittenversionsofthesecontributionsinthe same order as they were presented during the conference. WehaveaddedacorrectversionofJoanP.Hutchinson'scontributiontoGD 2000 that had been misprinted in the GD 2000 proceedings. GD 2001 hosted a software exhibition that gave participants and guests the opportunity for hands-on experience with state-of-the-art graph drawing tools. Outofthe26submittedsoftwaretools,24werepresentedattheconferenceand received considerable attention by the participants.Each of them is represented here by a two-page-summary. Inaspecialsessionongraphexchangeformats,organizedbyGiuseppeLiotta, theGXLandtheGraphMLprojectswerepresentedbyAndreasWinterandUlrik Brandes,respectively,andthenalivelydiscussionfollowed.Thewrittenversions of the two reports are also included here. The ?nal contribution in this volume is a report on a traditional component of all graph drawing conferences that is a serious and a fun event at the same time: the Graph Drawing Contest 2001 organized by Franz Brandenburg. We would like to thank all contributors for the pleasant cooperation.

In 1958, Ralph E. Gomory transformed the field of integer programming when he published a paper that described a cutting-plane algorithm for pure integer programs and announced that the method could be refined to give a finite algorithm for integer programming. In 2008, to commemorate the anniversary of this seminal paper, a special workshop celebrating fifty years of integer programming was held in Aussois, France, as part of the 12th Combinatorial Optimization Workshop.It contains reprints of key historical articles and written versions of survey lectures on six of the hottest topics in the field by distinguished members of the integer programming community. Useful for anyone in mathematics, computer science and operations research, this book exposes mathematical optimization, specifically integer programming and combinatorial optimization, to a broad audience.

Martin Grötschel is one of the most influential mathematicians of our time. He has received numerous honors and holds a number of key positions in the international mathematical community. He celebrated his 65th birthday on September 10, 2013. Martin Grötschel’s doctoral descendant tree 1983–2012, i.e., the first 30 years, features 39 children, 74 grandchildren, 24 great-grandchildren and 2 great-great-grandchildren, a total of 139 doctoral descendants.This book starts with a personal tribute to Martin Grötschel by the editors (Part I), a contribution by his very special “predecessor” Manfred Padberg on “Facets and Rank of Integer Polyhedra” (Part II), and the doctoral descendant tree 1983–2012 (Part III). The core of this book (Part IV) contains 16 contributions, each of which is coauthored by at least one doctoral descendant.The sequence of the articles starts with contributions to the theory of mathematical optimization, including polyhedral combinatorics, extended formulations, mixed-integer convex optimization, super classes of perfect graphs, efficient algorithms for subtree-telecenters, junctions in acyclic graphs and preemptive restricted strip covering, as well as efficient approximation of non-preemptive restricted strip covering.Combinations of new theoretical insights with algorithms and experiments deal with network design problems, combinatorial optimization problems with submodular objective functions and more general mixed-integer nonlinear optimization problems. Applications include VLSI layout design, systems biology, wireless network design, mean-risk optimization and gas network optimization.Computational studies include a semidefinite branch and cut approach for the max k-cut problem, mixed-integer nonlinear optimal control, and mixed-integer linear optimization for scheduling and routing of fly-in safari planes.The two closing articles are devoted to computational advances in generalmixed integer linear optimization, the first by scientists working in industry, the second by scientists working in academia.These articles reflect the “scientific facets” of Martin Grötschel who has set standards in theory, computation and applications.

Automatic Graph Drawing is concerned with the layout of relational structures as they occur in Computer Science (Data Base Design, Data Mining, Web Mining), Bioinformatics (Metabolic Networks), Businessinformatics (Organization Diagrams, Event Driven Process Chains), or the Social Sciences (Social Networks).In mathematical terms, such relational structures are modeled as graphs or more general objects such as hypergraphs, clustered graphs, or compound graphs. A variety of layout algorithms that are based on graph theoretical foundations have been developed in the last two decades and implemented in software systems.After an introduction to the subject area and a concise treatment of the technical foundations for the subsequent chapters, this book features 14 chapters on state-of-the-art graph drawing software systems, ranging from general "tool boxes'' to customized software for various applications. These chapters are written by leading experts, they follow a uniform scheme and can be read independently from each other.

Mathematiker haben in den letzten Jahren grundlegende Beiträge zu Fragestellungen in der Industrie, in Transport und Kommunikation, Versicherungen und Banken, in Medizin und Biologie geleistet. Dieses Buch ist ein Versuch, solche Beiträge in Form von Fallstudien einer größeren Öffentlichkeit zugänglich zu machen. Die von Experten in den jeweiligen Anwendungsgebieten geschriebenen Artikel belegen, wie vielfältig und wie aufregend Mathematik im Spannungsfeld zwischen Theorie und Anwendung sein kann. Die behandelte Problematik wird in der jeweiligen "Anwendersprache" eingeführt, mathematisch modelliert, dann werden Lösungsverfahren skizziert und schließlich praktische Ergebnisse diskutiert. Dieser Band zeugt von einer Öffnung der Mathematik und von einem "Trend zur größeren Praxisnähe".

In 1958, Ralph E. Gomory transformed the field of integer programming when he published a paper that described a cutting-plane algorithm for pure integer programs and announced that the method could be refined to give a finite algorithm for integer programming. In 2008, to commemorate the anniversary of this seminal paper, a special workshop celebrating fifty years of integer programming was held in Aussois, France, as part of the 12th Combinatorial Optimization Workshop.It contains reprints of key historical articles and written versions of survey lectures on six of the hottest topics in the field by distinguished members of the integer programming community. Useful for anyone in mathematics, computer science and operations research, this book exposes mathematical optimization, specifically integer programming and combinatorial optimization, to a broad audience.

This proceedings volume contains extended abstracts of talks presented at the 18th Symposium on Operations Research held at the University of Cologne, September 1-3, 1993. The Symposia on Operations Research are the annual meetings of the Gesellschaft fiir Mathematik, Okonometrie und Operations Research (GMOOR), a scientific society providing a link between research and applications in the areas of applied mathematics, economics and operations research. The broad range of interests and scientific activities covered by GMOOR and its members was demonstrated by about 250 talks presented at the 18th Symposium. As in l'ecent years, emphasis was placed on optimization and stochastics, this year with a special focus on combinatorial optimization and discrete mathematics. We appreciate that with sections on parallel and distributed computing and on scientific computing also new fields could be integrated into the scope of the GMOOR. This book contains extended abstracts of most of the papers presented at the con­ ference. Long versions and full papers of the talks are expected to appear elsewhere in refereed periodicals. The contributions were divided into sixteen sections: (1) Theory of Optimization, (2) Computational Methods of Optimization, (3) Combinatorial Optimization and Dis­ crete Mathematics, (4) Scientific Computing, (5) Decision Theory, (6) Mathematical Economics and Game Theory, (7) Banking, Finance and Insurance, (8) Econometrics, (9) Macroeconomics and Economic Theory, (10) Stochastics, (11) Production and Lo­ gistics, (12) System and Control Theory, (13) Routing and Scheduling, (14) Knowledge Based Systems, (15) Information Systems and (16) Parallel and Distributed Compu­ ting.