@misc{GodsilGroetschelWelsh1992, author = {Godsil, C. D. and Gr{\"o}tschel, Martin and Welsh, D. J. A.}, title = {Combinatorics in Statistical Physics}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-694}, number = {SC-91-19}, year = {1992}, language = {en} } @misc{Groetschel1992, author = {Gr{\"o}tschel, Martin}, title = {Discrete Mathematics in Manufacturing.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-738}, number = {SC-92-03}, year = {1992}, abstract = {Manufacturing is a topic that provides rich opportunities for important mathematical contributions to real-world problems. The purpose of this paper is to show, by means of several examples, where and how mathematical problems of a discrete nature arise in manufacturing and to demonstrate the savings and improvements that can be achieved by employing the techniques of combinatorial optimization. The topics covered range from the design phase of a product (e. g.,routing, placement and via minimization in VLSI design), the control of CNC machines (e. g., drilling and plotting), to the management of assembly lines, storage systems and whole factories. We also point out difficulties in the modelling of complex situations and outline the algorithmic methods that are used for the solution of the mathematical problems arising in manufacturing. {\bf Key words:} discrete mathematics , combinatorial optimization, applications to manufacturing.}, language = {en} } @misc{GroetschelMonmaStoer1992, author = {Gr{\"o}tschel, Martin and Monma, Clyde and Stoer, Mechthild}, title = {A Polyhedral Approach to Network Connectivity Problems (Extended Abstract).}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-924}, number = {SC-92-22}, year = {1992}, abstract = {We present a polyhedral approach for the general problem of designing a minimum-cost network with specified connectivity requir}, language = {en} } @misc{GroetschelMonmaStoer1993, author = {Gr{\"o}tschel, Martin and Monma, Clyde and Stoer, Mechthild}, title = {Polyhedral and Computational Investigations for Designing Communication Networks with High Survivability Requirements.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-944}, number = {SC-92-24}, year = {1993}, abstract = {We consider the important practical and theoretical problem of designing a low-cost communications network which can survive failures of certain network components. Our initial interest in this area was motivated by the need to design certain ``two-connected" survivable topologies for fiber optic communication networks of interest to the regional telephone companies. In this paper, we describe some polyhedral results for network design problems with higher connectivity requirements. We also report on some preliminary computational results for a cutting plane algorithm for various real-world and random problems with high connectivity requirements which shows promise for providing good solutions to these difficult problems. \def\NP{\$\cal NP\$}}, language = {en} } @misc{AscheuerGroetschelKrumkeetal.1998, author = {Ascheuer, Norbert and Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg}, title = {Combinatorial Online Optimization}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3674}, number = {SC-98-24}, year = {1998}, abstract = {In ``classical'' optimization, all data of a problem instance are considered given. The standard theory and the usual algorithmic techniques apply to such cases only. Online optimization is different. Many decisions have to be made before all data are available. In addition, decisions once made cannot be changed. How should one act ``best'' in such an environment? In this paper we survey online problems coming up in combinatorial optimization. We first outline theoretical concepts, such as competitiveness against various adversaries, to analyze online problems and algorithms. The focus, however, lies on real-world applications. We report, in particular, on theoretical investigations and our practical experience with problems arising in transportation and the automatic handling of material.}, language = {en} } @misc{GroetschelDalitzWinczewski1998, author = {Gr{\"o}tschel, Martin and Dalitz, Wolfgang and Winczewski, Vincent}, title = {Math-Net: Ein Informationssystem der Mathematik}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3680}, number = {SC-98-25}, year = {1998}, abstract = {In diesem Artikel geben wir einen {\"U}berblick {\"u}ber das Math-Net-Projekt. Wir berichten {\"u}ber die organisatorischen und technischen Vorgehensweisen beim Aufbau eines verteilten Informationssystems f{\"u}r die Mathematik in Deutschland.}, language = {de} } @misc{GroetschelLuegger1998, author = {Gr{\"o}tschel, Martin and L{\"u}gger, Joachim}, title = {Scientific Information Systems and Metadata}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3698}, number = {SC-98-26}, year = {1998}, abstract = {This article begins with a short survey on the history of the classification of knowledge. It briefly discusses the traditional means of keeping track of scientific progress, i.e., collecting, classifying, abstracting, and reviewing all publications in a field. The focus of the article, however, is on modern electronic information and communication systems that try to provide high-quality information by automatic document retrieval or by using metadata, a new tool to guide search engines. We report, in particular, on efforts of this type made jointly by a number of German scientific societies. A full version of this paper including all hypertext references, links to online papers and references to the literature can be found under the URL: {\tt http://elib.zib.de/math.org.softinf.pub} .}, language = {en} } @misc{AbdelHamidAscheuerGroetschel1998, author = {Abdel-Hamid, Atef Abdel-Aziz and Ascheuer, Norbert and Gr{\"o}tschel, Martin}, title = {Order Picking in an Automatic Warehouse: Solving Online Asymmetric TSPs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3519}, number = {SC-98-08}, year = {1998}, abstract = {We report on a joint project with industry that had the aim to sequence transportation requests within an automatic storage system in such a way that the overall travel time is minimized. The manufacturing environment is such that scheduling decisions have to be made before all jobs are known. We have modeled this task as an \emph{online} Asymmetric Traveling Salesman Problem (ATSP). Several heuristics for the online ATSP are compared computationally within a simulation environment to judge which should be used in practice. Compared to the priority rule used so far, the optimization package reduced the unloaded travel time by about 40~\\%. Because of these significant savings our procedure was implemented as part of the control software for the stacker cranes of the storage systems.}, language = {en} } @misc{BorndoerferGroetschelLoebel1998, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and L{\"o}bel, Andreas}, title = {Optimization of Transportation Systems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3529}, number = {SC-98-09}, year = {1998}, abstract = {The world has experienced two hundred years of unprecedented advances in vehicle technology, transport system development, and traffic network extension. Technical progress continues but seems to have reached some limits. Congestion, pollution, and increasing costs have created, in some parts of the world, a climate of hostility against transportation technology. Mobility, however, is still increasing. What can be done? There is no panacea. Interdisciplinary cooperation is necessary, and we are going to argue in this paper that {\em Mathematics\/} can contribute significantly to the solution of some of the problems. We propose to employ methods developed in the {\em Theory of Optimization\/} to make better use of resources and existing technology. One way of optimization is better planning. We will point out that {\em Discrete Mathematics\/} provides a suitable framework for planning decisions within transportation systems. The mathematical approach leads to a better understanding of problems. Precise and quantitative models, and advanced mathematical tools allow for provable and reproducible conclusions. Modern computing equipment is suited to put such methods into practice. At present, mathematical methods contribute, in particular, to the solution of various problems of {\em operational planning}. We report about encouraging {\em results\/} achieved so far.}, language = {en} } @misc{BleyGroetschelWessaely1998, author = {Bley, Andreas and Gr{\"o}tschel, Martin and Wess{\"a}ly, Roland}, title = {Design of Broadband Virtual Private Networks: Model and Heuristics for the B-WiN}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3565}, number = {SC-98-13}, year = {1998}, abstract = {We investigate the problem of designing survivable broadband virtual private networks that employ the Open Shortest Path First (OSPF) routing protocol to route the packages. The capacities available for the links of the network are a minimal capacity plus multiples of a unit capacity. Given the directed communication demands between all pairs of nodes, we wish to select the capacities in a such way, that even in case of a single node or a single link failure a specified percentage of each demand can be satisfied and the costs for these capacities are minimal. We present a mixed--integer linear programming formulation of this problem and several heuristics for its solution. Furthermore, we report on computational results with real-world data.}, language = {en} } @incollection{Groetschel2005, author = {Gr{\"o}tschel, Martin}, title = {Der junge Albring und Schwelm}, booktitle = {Der Forscher und der Zweifler - Werner Albring zum 90. Geburtstag}, editor = {der Wissenschaften, Berlin-Brandenburgische}, publisher = {Berlin-Brandenburgische Akademie der Wissenschaften}, pages = {11 -- 35}, year = {2005}, language = {en} } @incollection{GroetschelHillerTuchscherer2009, author = {Gr{\"o}tschel, Martin and Hiller, Benjamin and Tuchscherer, Andreas}, title = {Structuring a Dynamic Environment}, booktitle = {Emergence, Analysis and Evolution of Structures. Concepts and Strategies Across Disciplines}, editor = {Lucas, Klaus and Roosen, Peter}, publisher = {Springer}, doi = {10.1007/978-3-642-00870-2}, pages = {199 -- 214}, year = {2009}, language = {en} } @incollection{GroetschelKochHoang2010, author = {Gr{\"o}tschel, Martin and Koch, Thorsten and Hoang, Nam-Dung}, title = {Lagenwechsel minimieren - oder das Bohren von L{\"o}chern in Leiterplatten}, booktitle = {Besser als Mathe}, editor = {Biermann, Katja and Gr{\"o}tschel, Martin and Lutz-Westphal, Brigitte}, publisher = {Vieweg+Teubner}, doi = {10.1007/978-3-658-01004-1_19}, pages = {161 -- 174}, year = {2010}, language = {en} } @incollection{Groetschel2008, author = {Gr{\"o}tschel, Martin}, title = {Tiefensuche}, volume = {58}, booktitle = {Kosmos und Zahl - Beitr{\"a}ge zur Mathematik- und Astronomiegeschichte, zu Alexander von Humboldt und Leibniz}, editor = {Hecht, Hartmut and Mikosch, Regina and Schwarz, Ingo and Siebert, Harald and Werther, Romy}, publisher = {Franz Steiner Verlag}, pages = {331 -- 346}, year = {2008}, language = {en} } @incollection{GroetschelLuegger2007, author = {Gr{\"o}tschel, Martin and L{\"u}gger, Joachim}, title = {Die Wissenschaftsgalaxis}, booktitle = {eUniversity - Update Bologna}, editor = {Keil, Reinhard and Kerres, Michael and Schulmeister, Rolf}, publisher = {Waxmann Verlag}, pages = {335 -- 354}, year = {2007}, language = {en} } @incollection{Groetschel2008, author = {Gr{\"o}tschel, Martin}, title = {Geistiges Eigentum - Eine Zusammenfassung der vorgetragenen Standpunkte}, volume = {Heft 7}, booktitle = {Geistiges Eigentum - Streitgespr{\"a}che in den Wissenschaftlichen Sitzungen der Versammlung der Berlin-Brandenburgischen Akademie der Wissenschaften}, editor = {der Wissenschaften, Berlin-Brandenburgische}, publisher = {Berlin-Brandenburgische Akademie der Wissenschaften}, pages = {89 -- 95}, year = {2008}, language = {en} } @incollection{Groetschel2008, author = {Gr{\"o}tschel, Martin}, title = {Geistiges Eigentum - Einf{\"u}hrung in das Thema}, volume = {Heft 7}, booktitle = {Geistiges Eigentum - Streitgespr{\"a}che in den Wissenschaftlichen Sitzungen der Versammlung der Berlin-Brandenburgischen Akademie der Wissenschaften}, editor = {der Wissenschaften, Berlin-Brandenburgische}, publisher = {Berlin-Brandenburgische Akademie der Wissenschaften}, pages = {9 -- 14}, year = {2008}, language = {en} } @incollection{Groetschel2007, author = {Gr{\"o}tschel, Martin}, title = {Schnelle Rundreisen}, booktitle = {Kombinatorische Optimierung erleben - In Studium und Unterricht}, editor = {Hußmann, Stephan and Lutz-Westphal, Brigitte}, publisher = {Vieweg}, address = {Wiesbaden}, pages = {95 -- 128}, year = {2007}, language = {en} } @misc{Groetschel2007, author = {Gr{\"o}tschel, Martin}, title = {Das Problem mit der Komplexit{\"a}t}, journal = {Kombinatorische Optimierung erleben - In Studium und Unterricht}, editor = {Hußmann, Stephan and Lutz-Westphal, Brigitte}, publisher = {Vieweg}, address = {Wiesbaden}, doi = {10.1007/978-3-8348-9120-4_9}, pages = {265 -- 274}, year = {2007}, language = {en} } @incollection{Groetschel2004, author = {Gr{\"o}tschel, Martin}, title = {Cardinality Homogeneous Set Systems, Cycles in Matroids, and Associated Polytopes}, booktitle = {The Sharpest Cut}, editor = {Gr{\"o}tschel, Martin}, publisher = {MPS-SIAM}, pages = {99 -- 120}, year = {2004}, language = {en} } @incollection{Groetschel2005, author = {Gr{\"o}tschel, Martin}, title = {In der Mathematik sind sich alle einig und die Gesellschaft hat von ihr nichts zu bef{\"u}rchten}, volume = {2}, booktitle = {Wissenschaft Kontrovers}, publisher = {Chronos, Edition Collegium Helveticum}, address = {Z{\"u}rich}, year = {2005}, language = {en} } @incollection{Groetschel2008, author = {Gr{\"o}tschel, Martin}, title = {Ohne x is nix}, volume = {14}, booktitle = {Berichte und Abhandlungen}, editor = {der Wissenschaften, Berlin-Brandenburgische}, publisher = {Akademie-Verlag}, address = {Berlin}, pages = {195 -- 219}, year = {2008}, language = {en} }