@book{GroetschelLovaszSchrijver1988, author = {Gr{\"o}tschel, Martin and Lov{\´a}sz, L{\´a}szlo and Schrijver, Alexander}, title = {Geometric Algorithms and Combinatorial Optimization}, volume = {2}, journal = {Algorithms and Combinatorics}, publisher = {Springer}, isbn = {3-540-13624-X, 0-387-13624-X (U.S.)}, year = {1988}, language = {en} } @article{GroetschelJuengerReinelt1989, author = {Gr{\"o}tschel, Martin and J{\"u}nger, Michael and Reinelt, Gerhard}, title = {Via Minimization with Pin Preassignments and Layer Preference}, volume = {69}, journal = {ZAMM - Zeitschrift f{\"u}r Angewandte Mathematik und Mechanik}, number = {11}, pages = {393 -- 399}, year = {1989}, language = {en} } @article{GroetschelTruemper1989, author = {Gr{\"o}tschel, Martin and Truemper, Klaus}, title = {Decomposition and Optimization over Cycles in Binary Matroids}, volume = {46}, journal = {Journal of Combinatorial Theory, Series B}, number = {3}, pages = {306 -- 337}, year = {1989}, language = {en} } @article{GroetschelTruemper1989, author = {Gr{\"o}tschel, Martin and Truemper, Klaus}, title = {Master Polytopes for Cycles of Binary Matroids}, volume = {114/115}, journal = {Linear Algebra and its Applications}, pages = {523 -- 540}, year = {1989}, language = {en} } @article{GroetschelWakabayashi1989, author = {Gr{\"o}tschel, Martin and Wakabayashi, Yoshiko}, title = {A cutting plane algorithm for a clustering problem}, volume = {45}, journal = {Mathematical Programming, Series B}, publisher = {Mathematical Programming, Series B}, pages = {59 -- 96}, year = {1989}, language = {en} } @inproceedings{AscheuerEscuderoGroetscheletal.1990, author = {Ascheuer, Norbert and Escudero, Laureano and Gr{\"o}tschel, Martin and Stoer, Mechthild}, title = {On Identifying in Polynomial Time Violated Subtour Elimination and Precedence Forcing Constraints for the Sequential Ordering Problem}, booktitle = {Integer Programming and Combinatorial Optimization, Proceeedings of a Conference held at the University of Waterloo, May 28-30, 1990}, editor = {Kannan, Ravi and Pulleyblank, William}, publisher = {University of Waterloo Press}, pages = {19 -- 28}, year = {1990}, language = {en} } @article{GroetschelMonma1990, author = {Gr{\"o}tschel, Martin and Monma, Clyde}, title = {Integer Polyhedra Arising from Certain Network Design Problems with Connectivity Constraints}, volume = {3}, journal = {SIAM Journal on Discrete Mathematics}, number = {4}, pages = {502 -- 523}, year = {1990}, language = {en} } @article{GroetschelWakabayashi1990, author = {Gr{\"o}tschel, Martin and Wakabayashi, Yoshiko}, title = {Facets of the clique partitioning polytope}, volume = {47}, journal = {Mathematical Programming, Series A}, number = {3}, pages = {367 -- 387}, year = {1990}, language = {en} } @article{GroetschelJuengerReinelt1984, author = {Gr{\"o}tschel, Martin and J{\"u}nger, Michael and Reinelt, Gerhard}, title = {Optimal triangulation of large real world input-output matrices}, volume = {25}, journal = {Statistische Hefte}, pages = {261 -- 295}, year = {1984}, language = {en} } @inproceedings{GroetschelLovaszSchrijver1984, author = {Gr{\"o}tschel, Martin and Lov{\´a}sz, L{\´a}szlo and Schrijver, Alexander}, title = {Geometric Methods in Combinatorial Optimization}, booktitle = {Progress in Combinatorial Optimization, (Conference Waterloo/Ontario 1982)}, editor = {Pulleyblank, William}, publisher = {Academic Press}, pages = {167 -- 183}, year = {1984}, language = {en} } @incollection{GroetschelLovaszSchrijver1984, author = {Gr{\"o}tschel, Martin and Lov{\´a}sz, L{\´a}szlo and Schrijver, Alexander}, title = {Polynomial algorithms for perfect graphs}, volume = {21}, booktitle = {Topics on perfect graphs}, editor = {Berge, Claude and Chv{\´a}tal, Vašek}, publisher = {North-Holland}, pages = {325 -- 356}, year = {1984}, language = {en} } @article{GroetschelLovaszSchrijver1984, author = {Gr{\"o}tschel, Martin and Lov{\´a}sz, L{\´a}szlo and Schrijver, Alexander}, title = {Corrigendum to our paper "The ellipsoid method and its consequences in combinatorial optimization"}, volume = {4}, journal = {Combinatorica}, number = {4}, pages = {291 -- 295}, year = {1984}, language = {en} } @article{GroetschelNemhauser1984, author = {Gr{\"o}tschel, Martin and Nemhauser, George}, title = {A polynomial algorithm for the max-cut problem on graphs without long odd cycles}, volume = {29}, journal = {Mathematical Programming}, number = {1}, publisher = {North-Holland}, pages = {28 -- 40}, year = {1984}, language = {en} } @inproceedings{GroetschelWakabayashi1984, author = {Gr{\"o}tschel, Martin and Wakabayashi, Yoshiko}, title = {Constructions of hypotraceable digraphs}, booktitle = {Mathematical Programming. Proceedings of the International Congress on Mathematical Programming, Rio de Janeiro, Brazil, 6-8 April 1981}, editor = {Cottle, Richard and Kelmanson, Milton and Korte, Bernhard}, publisher = {North-Holland}, pages = {147 -- 175}, year = {1984}, language = {en} } @article{BarahonaGroetschelMahjoub1985, author = {Barahona, Francisco and Gr{\"o}tschel, Martin and Mahjoub, Ali}, title = {Facets of the Bipartite Subgraph Polytope}, volume = {10}, journal = {Mathematics of Operations Research}, pages = {340 -- 358}, year = {1985}, language = {en} } @article{GroetschelHolland1985, author = {Gr{\"o}tschel, Martin and Holland, Olaf}, title = {Solving matching problems with linear programming}, volume = {33}, journal = {Mathematical Programming}, number = {3}, pages = {243 -- 259}, year = {1985}, language = {en} } @inproceedings{GroetschelJuengerReinelt1985, author = {Gr{\"o}tschel, Martin and J{\"u}nger, Michael and Reinelt, Gerhard}, title = {Acyclic subdigraphs and linear orderings}, booktitle = {Graphs and Order. The Role of Graphs in the Theory of Ordered Sets and its Applications, Proceedings of NATO ASI, Ser. C 147, Banff/Canada 1984}, editor = {Rival, Ivan}, publisher = {D. Reidel Publishing Company}, pages = {217 -- 264}, year = {1985}, language = {en} } @article{GroetschelJuengerReinelt1985, author = {Gr{\"o}tschel, Martin and J{\"u}nger, Michael and Reinelt, Gerhard}, title = {On the acyclic subgraph polytope}, volume = {33}, journal = {Mathematical Programming}, number = {1}, publisher = {North-Holland}, pages = {28 -- 42}, year = {1985}, language = {en} } @article{GroetschelJuengerReinelt1985, author = {Gr{\"o}tschel, Martin and J{\"u}nger, Michael and Reinelt, Gerhard}, title = {Facets of the linear ordering polytope}, volume = {33}, journal = {Mathematical Programming}, number = {1}, publisher = {North-Holland}, pages = {43 -- 60}, year = {1985}, language = {en} } @incollection{GroetschelPadberg1985, author = {Gr{\"o}tschel, Martin and Padberg, Manfred}, title = {Polyhedral theory}, booktitle = {The Traveling Salesman Problem. A Guided Tour of Combinatorial Optimization}, editor = {Lawler, Eugene and Lenstra, Jan and Kan, Alexander and Shmoys, David}, publisher = {Wiley}, pages = {251 -- 306}, year = {1985}, language = {en} } @incollection{PadbergGroetschel1985, author = {Padberg, Manfred and Gr{\"o}tschel, Martin}, title = {Polyhedral computations}, booktitle = {The Traveling Salesman Problem. A Guided Tour of Combinatorial Optimization}, editor = {Lawler, Eugene and Lenstra, Jan and Kan, Alexander and Shmoys, David}, publisher = {Wiley}, pages = {307 -- 360}, year = {1985}, language = {en} } @techreport{BarahonaGroetschel1985, author = {Barahona, Francisco and Gr{\"o}tschel, Martin}, title = {The Travelling Salesman Problem for Graphs not Contractible to K_5 - e}, number = {77}, publisher = {Mathematisches Institut, Universit{\"a}t Augsburg}, year = {1985}, language = {en} } @article{BarahonaGroetschel1986, author = {Barahona, Francisco and Gr{\"o}tschel, Martin}, title = {On the Cycle Polytope of a Binary Matroid}, volume = {40}, journal = {Journal of Combinatorial Theory, Series B}, pages = {40 -- 62}, year = {1986}, language = {en} } @inproceedings{Groetschel1986, author = {Gr{\"o}tschel, Martin}, title = {Polyedrische Kombinatorik und Schnittebenenverfahren, Tagungsbericht 2. Sommerschule Diskrete Strukturen, Bayreuth 1985}, volume = {21}, booktitle = {Diskrete Strukturen, algebraische Methoden und Anwendungen}, editor = {Kerber, Adalbert}, publisher = {Institut f{\"u}r Mathematik, Universit{\"a}t Bayreuth}, pages = {69 -- 100}, year = {1986}, language = {en} } @incollection{Groetschel1986, author = {Gr{\"o}tschel, Martin}, title = {Fortschritte in der polyedrischen Kombinatorik}, booktitle = {{\"O}konomische Prognose-, Entscheidungs- und Gleichgewichtsmodelle, Abschlußberichte des SFB 21}, editor = {Krelle, Wilhelm}, publisher = {Verlag Chemie}, address = {Weinheim}, pages = {341 -- 367}, year = {1986}, language = {en} } @article{GroetschelLovaszSchrijver1986, author = {Gr{\"o}tschel, Martin and Lov{\´a}sz, L{\´a}szlo and Schrijver, Alexander}, title = {Relaxations of Vertex Packing}, volume = {40}, journal = {Journal of Combinatorial Theory, Series B}, pages = {330 -- 343}, year = {1986}, language = {en} } @article{GroetschelPulleyblank1986, author = {Gr{\"o}tschel, Martin and Pulleyblank, William}, title = {Clique tree inequalities and the symmetric travelling salesman problem}, volume = {11}, journal = {Mathematics of Operations Research}, number = {4}, pages = {537 -- 569}, year = {1986}, language = {en} } @article{GroetschelHolland1987, author = {Gr{\"o}tschel, Martin and Holland, Olaf}, title = {A Cutting Plane Algorithm for Minimum Perfect 2-Matchings}, volume = {39}, journal = {Computing}, pages = {327 -- 344}, year = {1987}, language = {en} } @article{GroetschelThomassenWakabayashi1980, author = {Gr{\"o}tschel, Martin and Thomassen, Carsten and Wakabayashi, Yoshiko}, title = {Hypotraceable digraphs}, volume = {4}, journal = {Journal of Graph Theory}, pages = {377 -- 381}, year = {1980}, language = {en} } @article{GroetschelWakabayashi1980, author = {Gr{\"o}tschel, Martin and Wakabayashi, Yoshiko}, title = {Hypohamiltonian digraphs}, volume = {36}, journal = {Methods of Operations Research}, pages = {99 -- 119}, year = {1980}, language = {en} } @book{BachemButzGroetscheletal.1981, author = {Bachem, Achim and Butz, Lothar and Gr{\"o}tschel, Martin and (Bearb.), Rainer and Leitung), Bernhard}, title = {Input-Output-Analyse bei unternehmensgr{\"o}ßenspezifischen Fragestellungen}, publisher = {Institut f{\"u}r Mittelstandsforschung}, address = {Bonn}, year = {1981}, language = {en} } @article{BachemGroetschel1981, author = {Bachem, Achim and Gr{\"o}tschel, Martin}, title = {Homogenization of polyhedra}, volume = {40}, journal = {Methods of Operations Research}, pages = {215 -- 219}, year = {1981}, language = {en} } @inproceedings{BachemGroetschel1981, author = {Bachem, Achim and Gr{\"o}tschel, Martin}, title = {Characterizations of adjacency of faces of polyhedra}, volume = {14}, booktitle = {Mathematical Programming at Oberwolfach}, editor = {K{\"o}nig, Heinz and Korte, Bernhard and Ritter, Klaus}, publisher = {North-Holland}, pages = {1 -- 22}, year = {1981}, language = {en} } @article{GroetschelLovaszSchrijver1981, author = {Gr{\"o}tschel, Martin and Lov{\´a}sz, L{\´a}szlo and Schrijver, Alexander}, title = {The ellipsoid method and its consequences in combinatorial optimization}, volume = {1}, journal = {Combinatorica}, number = {2}, pages = {169 -- 197}, year = {1981}, language = {en} } @article{GroetschelLovaszSchrijver1981, author = {Gr{\"o}tschel, Martin and Lov{\´a}sz, L{\´a}szlo and Schrijver, Alexander}, title = {The ellipsoid method and its consequences in combinatorial optimization}, journal = {IIASA Collab. Proceedings Ser. CP-81-S1}, pages = {511 -- 546}, year = {1981}, language = {en} } @article{GroetschelPulleyblank1981, author = {Gr{\"o}tschel, Martin and Pulleyblank, William}, title = {Weakly bipartite graphs and the max-cut problem}, volume = {1}, journal = {Operations Research Letters}, number = {1}, pages = {23 -- 27}, year = {1981}, language = {en} } @article{GroetschelWakabayashi1981, author = {Gr{\"o}tschel, Martin and Wakabayashi, Yoshiko}, title = {On the structure of the monotone asymmetric travelling salesman polytope I}, volume = {34}, journal = {Discrete Mathematics}, pages = {43 -- 59}, year = {1981}, language = {en} } @article{GroetschelWakabayashi1981, author = {Gr{\"o}tschel, Martin and Wakabayashi, Yoshiko}, title = {On the structure of the monotone asymmetric travelling salesman polytope II}, volume = {14}, journal = {Mathematical Programming Study}, pages = {77 -- 97}, year = {1981}, language = {en} } @inproceedings{BachemGroetschel1982, author = {Bachem, Achim and Gr{\"o}tschel, Martin}, title = {New aspects of polyhedral theory}, booktitle = {Modern Applied Mathematics}, editor = {Korte, Bernhard}, publisher = {North-Holland}, pages = {51 -- 106}, year = {1982}, language = {en} } @inproceedings{Groetschel1982, author = {Gr{\"o}tschel, Martin}, title = {Approaches to Hard Combinatorial Optimization Problems}, booktitle = {Modern Applied Mathematics, Optimization and Operations Research, Lect. Summer Sch., Bonn 1979}, editor = {Korte, Bernhard}, publisher = {North-Holland}, pages = {437 -- 515}, year = {1982}, language = {en} } @inproceedings{Groetschel1982, author = {Gr{\"o}tschel, Martin}, title = {Kombinatorische Optimierung}, booktitle = {Forschungsbericht 1978-1980 der Rheinischen Friedrich-Wilhelms-Universit{\"a}t}, editor = {der Universit{\"a}t Bonn, Der}, publisher = {Bouvier}, address = {Bonn}, pages = {45 -- 54}, year = {1982}, language = {en} } @inproceedings{Groetschel1984, author = {Gr{\"o}tschel, Martin}, title = {On Intersections of Longest Cycles}, booktitle = {Graph Theory and Combinatorics}, editor = {Bollob{\´a}s, B{\´e}la}, publisher = {Academic Press}, pages = {171 -- 189}, year = {1984}, language = {en} } @incollection{Groetschel1984, author = {Gr{\"o}tschel, Martin}, title = {Developments in combinatorial optimization}, booktitle = {Perspectives in Mathematics (Anniversary of Oberwolfach 1984)}, editor = {J{\"a}ger, Willi and Moser, J. and Remmert, R.}, publisher = {Birkh{\"a}user}, address = {Basel}, pages = {249 -- 294}, year = {1984}, language = {en} } @inproceedings{Groetschel1984, author = {Gr{\"o}tschel, Martin}, title = {Polyhedral Combinatorics}, booktitle = {COMBINATORIAL OPTIMIZATION}, editor = {O'Heigeartaigh, Michael and Lenstra, Jan and Kan, Alexander}, publisher = {Wiley}, pages = {1 -- 10}, year = {1984}, language = {en} } @techreport{Groetschel1984, author = {Gr{\"o}tschel, Martin}, title = {Polyedrische Kombinatorik und Schnittebenenverfahren}, number = {231}, publisher = {Forschungszentrum Graz, {\"O}sterreich}, year = {1984}, language = {en} } @article{GroetschelJuengerReinelt1984, author = {Gr{\"o}tschel, Martin and J{\"u}nger, Michael and Reinelt, Gerhard}, title = {A Cutting Plane Algorithm for the Linear Ordering Problem}, volume = {32}, journal = {Operations Research}, number = {6}, pages = {1195 -- 1220}, year = {1984}, language = {en} } @article{BorndoerferGroetschelPfetsch2007, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and Pfetsch, Marc}, title = {A Column-Generation Approach to Line Planning in Public Transport}, volume = {41}, journal = {Transportation Science (INFORMS)}, number = {1}, doi = {10.1287/trsc.1060.0161}, pages = {123 -- 132}, year = {2007}, language = {en} } @misc{GroetschelLoebelVoelker1996, author = {Gr{\"o}tschel, Martin and L{\"o}bel, Andreas and V{\"o}lker, Manfred}, title = {Optimierung des Fahrzeugumlaufs im {\"O}ffentlichen Nahverkehr}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2195}, number = {SC-96-08}, year = {1996}, abstract = {This paper addresses the problem of scheduling vehicles in a public mass transportation system. We show how this problem can be modelled as a special multicommodity flow problem and outline the solution methodology we have developed. Based on polyhedral investigations, we have designed and implemented a branch\&cut algorithm and various heuristics with which real vehicle scheduling problems of truely large scale can be solved to optimality. We describe some implementation issues and report computational results.}, language = {de} } @misc{AscheuerFischettiGroetschel1997, author = {Ascheuer, Norbert and Fischetti, Matteo and Gr{\"o}tschel, Martin}, title = {A polyhedral study of the asymmetric travelling salesman problem with time windows}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2807}, number = {SC-97-11}, year = {1997}, abstract = {The asymmetric travelling salesman problem with time windows (ATSP-TW) is a basic model for scheduling and routing applications. In this paper we present a formulation of the problem involving only 0/1-variables associated with the arcs of the underlying digraph. This has the advantage of avoiding additional variables as well as the associated (typically very ineffective) linking constraints. In the formulation, time window restrictions are modelled by means of ``infeasible path elimination'' constraints. We present the basic form of these constraints along with some possible strengthenings. Several other classes of valid inequalities derived from related asymmetric travelling salesman problems are also described, along with a lifting theorem. We also study the ATSP-TW polytope, \$P_{TW}\$, defined as the convex hull of the integer solutions of our model. We show that determining the dimension of \$P_{TW}\$ is strongly {\em NP}--complete problem, even if only one time window is present. In this latter case, we provide a minimal equation system for \$P_{TW}\$. Computational experiments on the new formulation are reported in a companion paper [1997] where we show that it outperforms alternative formulations on some classes of problem instances.}, language = {en} } @misc{AlevrasGroetschelWessaely1997, author = {Alevras, Dimitris and Gr{\"o}tschel, Martin and Wess{\"a}ly, Roland}, title = {Cost-Efficient Network Synthesis from Leased Lines}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2912}, number = {SC-97-22}, year = {1997}, abstract = {Given a communication demand between each pair of nodes of a network we consider the problem of deciding what capacity to install on each edge of the network in order to minimize the building cost of the network and to satisfy the demand between each pair of nodes. The feasible capacities that can be leased from a network provider are of a particular kind in our case. There are a few so-called basic capacities having the property that every basic capacity is an integral multiple of every smaller basic capacity. An edge can be equipped with a capacity only if it is an integer combination of the basic capacities. We treat, in addition, several restrictions on the routings of the demands (length restriction, diversification) and failures of single nodes or single edges. We formulate the problem as a mixed integer linear programming problem and develop a cutting plane algorithm as well as several heuristics to solve it. We report on computational results for real world data.}, language = {en} } @misc{AlevrasGroetschelWessaely1997, author = {Alevras, Dimitris and Gr{\"o}tschel, Martin and Wess{\"a}ly, Roland}, title = {Capacity and Survivability Models for Telecommunication Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2931}, number = {SC-97-24}, year = {1997}, abstract = {Designing low-cost networks that survive certain failure situations is one of the prime tasks in the telecommunication industry. In this paper we survey the development of models for network survivability used in practice in the last ten years. We show how algorithms integrating polyhedral combinatorics, linear programming, and various heuristic ideas can help solve real-world network dimensioning instances to optimality or within reasonable quality guarantees in acceptable running times. The most general problem type we address is the following. Let a communication demand between each pair of nodes of a telecommunication network be given. We consider the problem of choosing, among a discrete set of possible capacities, which capacity to install on each of the possible edges of the network in order to (i) satisfy all demands, (ii) minimize the building cost of the network. \noindent In addition to determining the network topology and the edge capacities we have to provide, for each demand, a routing such that (iii) no path can carry more than a given percentage of the demand, (iv) no path in the routing exceeds a given length. \noindent We also have to make sure that (v) for every single node or edge failure, a certain percentage of the demand is reroutable. \noindent Moreover, for all failure situations feasible routings must be computed. The model described above has been developed in cooperation with a German mobile phone provider. We present a mixed-integer programming formulation of this model and computational results with data from practice.}, language = {en} } @misc{DalitzGroetschelLuegger1997, author = {Dalitz, Wolfgang and Gr{\"o}tschel, Martin and L{\"u}gger, Joachim}, title = {Information Services for Mathematics in the Internet (Math-Net)}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2949}, number = {SC-97-25}, year = {1997}, abstract = {The present paper gives a brief description of the Math-Net project which is carried out by nine mathematical institutions in Germany, supported by Deutsches Forschungsnetz (DFN) and Deutsche Telekom. The project aims at setting up the technical and organizational infrastructure for efficient, inexpensive and user-driven information services for mathematics. With the aid of active (structured retrieval mechanisms) and passive (profile services) components, electronic mathematical information in Germany will be made available to the scientist at his workplace. The emphasis is put on information about publications, software and data collections, teaching and research activities, but also on organizational and bibliographical information. Decentral organization structures, distributed search systems as well as the use of meta-information (metadata) in accordance with the Dublin Core (hopefully) guarantee a longterm, high-quality repository of data. The well-known mathematical software and data collection netlib\/ will be used as an example to illustrate how such a collection can be adapted to Math-Net. An integration of netlib into HyperWave offers additional perspectives and functionalities.}, language = {en} } @misc{BorndoerferGroetschelHerzogetal.1996, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and Herzog, Werner and Klostermeier, Fridolin and Konsek, Wilhelm and K{\"u}ttner, Christian}, title = {K{\"u}rzen muß nicht Kahlschlag heißen - das Beispiel Telebus-Behindertenfahrdienst Berlin}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2510}, number = {SC-96-41}, year = {1996}, abstract = {M{\"u}ssen Etatk{\"u}rzungen bei staatlichen Dienstleistungseinrichtungen notwendig zu Leistungseinschr{\"a}nkungen oder Geb{\"u}hrenerh{\"o}hungen f{\"u}hren? Wir zeigen am Beispiel des Berliner Behindertenfahrdienstes {\em Telebus}, da\ss{} Sparzwang auch als Chance zur Verbesserung der eigenen Verwaltungs- und Arbeitsabl{\"a}ufe genutzt werden kann. Durch st{\"a}rkere Dienstleistungsorientierung, Vereinfachung der Arbeitsabl{\"a}ufe und durch den Einsatz von moderner EDV und von mathematischen Optimierungsmethoden zur Fahrzeugeinsatzplanung werden bei Telebus heute staatliche Leistungen trotz geringeren Etats besser erbracht als vorher.}, language = {de} } @misc{AlevrasGroetschelJonasetal.1996, author = {Alevras, Dimitris and Gr{\"o}tschel, Martin and Jonas, Peter and Paul, Ulrich and Wess{\"a}ly, Roland}, title = {Survivable Mobile Phone Architectures: Models and Solution Methods}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2582}, number = {SC-96-48}, year = {1996}, abstract = {In the highly competitive area of telecommunications, cost, quality, and network management are among the most important aspects to be considered when designing a network. We study the problem of dimensioning a telecommunication network that is still operating in case of a failure of a network component. Given a demand between each pair of nodes of a telecommunication network and a finite set of possible capacities for each edge of the network, we consider the problem of deciding what capacity to install on each edge of the network in order to minimize the building cost of the network and to satisfy the demand between each pair of nodes, even if a network component fails. The routing of the demands must satisfy the following additional restrictions: (a) there is a maximum number of nodes allowed in each path between any pair of nodes (path length restriction), and (b) there is a maximum percentage of the demand between each pair of nodes that can be routed through any network component (diversification restriction). Moreover, the chosen capacities must be such that, for every single node or single edge failure, a certain percentage of the demand between any pair of nodes is reroutable (i.e. it ``survives'' the particular failure). We formulate the problem as a mixed integer linear programming problem and present a cutting plane algorithm as well as several heuristics for its solution. Furthermore, we discuss several ways to implement survivability into a telecommunication network.}, language = {en} } @misc{AlevrasGroetschelWessaely1996, author = {Alevras, Dimitris and Gr{\"o}tschel, Martin and Wess{\"a}ly, Roland}, title = {A Network Dimensioning Tool}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2591}, number = {SC-96-49}, year = {1996}, abstract = {Designing low cost networks that survive certain failure situations belongs to one of the prime tasks in the telecommunications industry. In this paper we describe a mathematical model combining several aspects of survivability that are elsewhere treated in a hierarchical fashion. We present mathematical investigations of this integrated model, a cutting plane algorithm, as well as several heuristics for its solution. Moreover, we report computational results with real world data. The problem we address is the following. Suppose, between each pair of nodes in a region, a communication demand is given. We want to determine the topology of a telecommunication network connecting the given nodes and to dimension all potential physical links. For each link, the possible capacities are restricted to a given finite set. The capacities must be chosen such that the communication demands are satisfied, even if certain network components fail, and such that the network building costs are as small as possible. Moreover, for each pair of nodes and each failure situation, we want to determine the paths on which the demand between the nodes is routed.}, language = {en} } @misc{BorndoerferGroetschelKlostermeieretal.1996, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and Klostermeier, Fridolin and K{\"u}ttner, Christian}, title = {Telebus Berlin - Mobilit{\"a}t f{\"u}r Behinderte}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2500}, number = {SC-96-40}, year = {1996}, abstract = {Steigendes Mobilit{\"a}tsbed{\"u}rfnis der Behinderten bei angespannter Haushaltslage --- diese Situation ergab vor drei Jahren beim Berliner Behindertenfahrdienst {\em Telebus\/} Handlungsbedarf. Gleichzeitig stie\ss{} die verwendete manuelle (Fahrzeug-)Tourenplanung mit damals etwa 1.000 Fahrtw{\"u}nschen pro Tag an ihre Grenzen. Zur L{\"o}sung dieser Probleme war der effiziente Einsatz von Computern und von {\em mathematischen Optimierungsverfahren\/} erforderlich. Ergebnis des daraufhin gestarteten {\em Telebus-Projektes\/} ist die Entwicklung eines neuen, alle Arbeitsabl{\"a}ufe unterst{\"u}tzenden Computersystems, das seit {\"u}ber einem Jahr im Einsatz ist. Herzst{\"u}ck dieses Systems ist ein auf mathematischen Methoden der ganzzahligen Optimierung basierendes Verfahren zur Tourenplanung. Ziel dieses Artikels ist die Beschreibung dieses Verfahrens und seiner Verwendung bei der Behindertenbef{\"o}rderung. Das Beispiel Telebus zeigt, da\ss{} der Einsatz mathematischer Optimierungstechniken neue M{\"o}glichkeiten f{\"u}r Kosteneinsparungen bei gleichzeitiger Serviceverbesserung auch in anderen Bereichen des {\"O}PNV er{\"o}ffnet.}, language = {de} } @misc{AbdelHamidAscheuerGroetscheletal.1995, author = {Abdel-Hamid, Atef Abdel-Aziz and Ascheuer, Norbert and Gr{\"o}tschel, Martin and Schorer, Herbert}, title = {Simulation und Optimierung einer PC-Fertigung unter Echtzeitbedingungen}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1700}, number = {SC-95-04}, year = {1995}, abstract = {Die Business Unit PC in Augsburg ist die zentrale Produktionsst{\"a}tte der Siemens--Nixdorf Informationssysteme (SNI) AG f{\"u}r Personal Computer sowie f{\"u}r einige Periph{\"a}rger{\"a}te. Das Werk, entworfen nach modernen CIM/CAI--Konzepten (Computer Integrated Manufacturing/ Computer Aided Industry), wurde 1987 errichtet. Bald zeigte sich jedoch, daß es f{\"u}r ein zu geringes Produktionsvolumen ausgelegt war und einige Komponenten des Systems Engp{\"a}sse im Produktionsbetrieb darstellen. Das Management suchte nach M{\"o}glichkeiten, den Produktionsfluß zu verbessern, ohne teure technische {\"A}nderungen am System vornehmen zu m{\"u}ssen. Eine Forschungsgruppe des Konrad--Zuse--Zentrums f{\"u}r Informationstechnik (die ehemals an der Universit{\"a}t Augsburg ans{\"a}ssig war) analysierte, unterst{\"u}tzt von einigen Studenten und Ingenieuren der SNI, den Produktionsfluß und lokalisierte Schwachstellen. Basierend auf diesen Erkenntnissen wurden mathematische Fragestellungen erarbeitet und auf mathematischen Optimierungsverfahren basierende Softwarepakete entwickelt, die jetzt teilweise bei SNI im Einsatz sind. Im folgenden werden einige dieser Fragestellungen, deren Modellierung und mathematische Behandlung beschrieben. Einige der Ans{\"a}tze, die hier dargestellt werden sollen, sind teilweise schon in Gr{\"o}tschel [Gr{\"o}92] angesprochen worden.}, language = {de} } @misc{GroetschelPadberg1994, author = {Gr{\"o}tschel, Martin and Padberg, Manfred}, title = {Ulysses 2000: In Search of Optimal Solutions to Hard Combinatorial Problems.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1296}, number = {SC-93-34}, year = {1994}, abstract = {Combinatorial optimization problems pervade many areas of human problem solving especially in the fields of business, economics and engineering. Intensive mathematical research and vast increases in raw computing power have advanced the state of the art in exact and heuristic problem solving at a pace that is unprecedented in human history. We survey here in layman's terms some of the fundamental concepts and principles that have led this progress. (This article will appear -- possibly in modified form -- in a popular science magazine.)}, language = {en} } @misc{GroetschelMonmaStoer1993, author = {Gr{\"o}tschel, Martin and Monma, Clyde and Stoer, Mechthild}, title = {Design of Survivable Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1054}, number = {SC-93-09}, year = {1993}, language = {en} } @misc{GroetschelLovasz1993, author = {Gr{\"o}tschel, Martin and Lov{\´a}sz, L{\´a}szlo}, title = {Combinatorial Optimization.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1098}, number = {SC-93-13}, year = {1993}, abstract = {This paper will appear as Chapter 28 of the forthcoming "Handbook on Combinatorics" (editors: R. Graham, M. Gr{\"o}tschel, L. Lovasz) to be published in 1994, by North-Holland.}, language = {en} } @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} } @misc{Groetschel2008, author = {Gr{\"o}tschel, Martin}, title = {Tiefensuche: Bemerkungen zur Algorithmengeschichte}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9628}, number = {08-23}, year = {2008}, abstract = {Dieser kurze Aufsatz zur Algorithmengeschichte ist Eberhard Knobloch, meinem Lieblings-Mathematikhistoriker, zum 65. Geburtstag gewidmet. Eberhard Knobloch hat immer, wenn ich ihm eine historische Frage zur Mathematik stellte, eine Antwort gewusst - fast immer auch sofort. Erst als ich mich selbst ein wenig und dazu amateurhaft mit Mathematikgeschichte besch{\"a}ftigte, wurde mir bewusst, wie schwierig dieses „Gesch{\"a}ft" ist. Man muss nicht nur mehrere (alte) Sprachen beherrschen, sondern auch die wissenschaftliche Bedeutung von Begriffen und Symbolen in fr{\"u}heren Zeiten kennen. Man muss zus{\"a}tzlich herausfinden, was zur Zeit der Entstehung der Texte „allgemeines Wissen" war, insbesondere, was seinerzeit g{\"u}ltige Beweisideen und -schritte waren, und daher damals keiner pr{\"a}zisen Definition oder Einf{\"u}hrung bedurfte. Es gibt aber noch eine Steigerung des historischen Schwierigkeitsgrades: Algorithmengeschichte. Dies m{\"o}chte ich in diesem Artikel kurz darlegen in der Hoffnung, dass sich Wissenschaftshistoriker dieses Themas noch intensiver annehmen, als sie das bisher tun. Der Grund ist, dass heute Algorithmen viele Bereiche unserer Alltagswelt steuern und unser t{\"a}gliches Leben oft von funktionierenden Algorithmen abh{\"a}ngt. Daher w{\"a}re eine bessere Kenntnis der Algorithmengeschichte von großem Interesse.}, language = {de} } @misc{GroetschelLutzWestphal2008, author = {Gr{\"o}tschel, Martin and Lutz-Westphal, Brigitte}, title = {Diskrete Mathematik und ihre Anwendungen: Auf dem Weg zu authentischem Mathematikunterricht}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10758}, number = {08-21}, year = {2008}, abstract = {Das heutige Leben ist durchdrungen von komplexen Technologien. Ohne Kommunikationsnetze, Internet, Mobilfunk, Logistik, Verkehrstechnik, medizinische Apparate, etc. k{\"o}nnte die moderne Gesellschaft nicht funktionieren. Fast alle dieser Technologien haben einen hohen Mathematikanteil. Der "normale B{\"u}rger"' weiss davon nichts, der Schulunterricht k{\"o}nnte dem ein wenig abhelfen. Einige mathematische Aspekte dieser Technologien sind einfach und sogar spielerisch intuitiv zug{\"a}nglich. Solche Anwendungen, die zus{\"a}tzlich noch der Lebensumwelt der Sch{\"u}ler zugeh{\"o}ren, k{\"o}nnen dazu genutzt werden, die mathematische Modellierung, also die mathematische Herangehensweise an die L{\"o}sung praktischer Fragen, anschaulich zu erl{\"a}utern. Gerade in der diskreten Mathematik k{\"o}nnen hier, quasi "nebenbei" mathematische Theorien erarbeitet und Teilaspekte (Definitionen, Fragestellungen, einfache Sachverhalte) durch eigenst{\"a}ndiges Entdecken der Sch{\"u}ler entwickelt werden. Wir beginnen mit einigen Beispielen.}, language = {de} } @incollection{GroetschelKrumkeRambauetal.2001, author = {Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg and Winter, Thomas and Zimmermann, Uwe}, title = {Combinatorial Online Optimization in Real Time}, booktitle = {Online Optimization of Large Scale Systems}, editor = {Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg}, publisher = {Springer}, pages = {679 -- 704}, year = {2001}, language = {en} } @incollection{GroetschelKrumkeRambau2001, author = {Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg}, title = {Online Optimization of Complex Transportation Systems}, booktitle = {Online Optimization of Large Scale Systems}, editor = {Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg}, publisher = {Springer}, pages = {705 -- 729}, year = {2001}, language = {en} } @misc{GroetschelRaackWerner2013, author = {Gr{\"o}tschel, Martin and Raack, Christian and Werner, Axel}, title = {Towards optimizing the deployment of optical access networks}, issn = {1438-0064}, doi = {10.1007/s13675-013-0016-x}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-18627}, year = {2013}, abstract = {In this paper we study the cost-optimal deployment of optical access networks considering variants of the problem such as fiber to the home (FTTH), fiber to the building (FTTB), fiber to the curb (FTTC), or fiber to the neighborhood (FTTN). We identify the combinatorial structures of the most important sub-problems arising in this area and model these, e.g., as capacitated facility location, concentrator location, or Steiner tree problems. We discuss modeling alternatives as well. We finally construct a "unified" integer programming model that combines all sub-models and provides a global view of all these FTTx problems. We also summarize computational studies of various special cases.}, language = {en} } @misc{Groetschel2012, author = {Gr{\"o}tschel, Martin}, title = {Einblicke in die Diskrete Mathematik}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14399}, number = {12-01}, year = {2012}, abstract = {„Diskrete Mathematik, was ist das?", ist eine typische Frage von Lehrern mit traditioneller Mathematikausbildung, denn dort kam und kommt diskrete Mathematik kaum vor. Die etwas Aufgeschlosseneren fragen: „Wenn (schon wieder) etwas Neues unterrichtet werden soll, was soll denn dann im Lehrplan gestrichen werden?" Auf die zweite Frage wird hier nicht eingegangen. Das Ziel dieses Aufsatzes ist es, in diskrete Mathematik einzuf{\"u}hren, Interesse an diesem Fachgebiet zu wecken und dazu anzuregen, dieses auch im Schulunterricht (ein wenig) zu ber{\"u}cksichtigen. Die Sch{\"u}ler und Sch{\"u}lerinnen werden daf{\"u}r dankbar sein - eine Erfahrung, die in vielen Unterrichtsreihen gemacht wurde.}, language = {de} } @misc{GroetschelHillerTuchscherer2007, author = {Gr{\"o}tschel, Martin and Hiller, Benjamin and Tuchscherer, Andreas}, title = {Combinatorial Online Optimization: Elevators \& Yellow Angels}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10360}, number = {07-36}, year = {2007}, abstract = {In \emph{classical optimization} it is assumed that full information about the problem to be solved is given. This, in particular, includes that all data are at hand. The real world may not be so nice'' to optimizers. Some problem constraints may not be known, the data may be corrupted, or some data may not be available at the moments when decisions have to be made. The last issue is the subject of \emph{online optimization} which will be addressed here. We explain some theory that has been developed to cope with such situations and provide examples from practice where unavailable information is not the result of bad data handling but an inevitable phenomenon.}, language = {en} } @misc{GroetschelNeumann2012, author = {Gr{\"o}tschel, Martin and Neumann, Gerald}, title = {10 Jahre TELOTA}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14799}, number = {12-13}, year = {2012}, abstract = {Das TELOTA-Projekt - zun{\"a}chst nur f{\"u}r zwei Jahre gestartet - feierte am 15. Juni 2011 sein 10-j{\"a}hriges Bestehen im Rahmen eines Workshops mit einem abschließenden Festvortrag von Richard Stallmann zum Thema „Copyright versus community in the age of computer networks". Diese Veranstaltung zeigte, wie aktuell die TELOTA-Themen weiterhin sind und dass diese eine große Resonanz in der allgemeinen {\"O}ffentlichkeit finden. Die TELOTA-Aktivit{\"a}ten haben sich als wichtiger Bestandteil der IT-Infrastruktur der BBAW erwiesen, gehen aber weit {\"u}ber reinen Service hinaus. Sie beeinflussen die Forschung selbst und f{\"u}hren zu neuen interessanten wissenschaftlichen Fragestellungen. Der R{\"u}ckblick auf die ersten zehn Jahre der TELOTA-Initiative in diesem Artikel soll einen kleinen Eindruck von dem geben, was bisher geleistet wurde.}, language = {de} } @misc{GroetschelNemhauser2007, author = {Gr{\"o}tschel, Martin and Nemhauser, George}, title = {George Dantzig's contributions to integer programming}, issn = {1438-0064}, doi = {10.1016/j.disopt.2007.08.003}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10393}, number = {07-39}, year = {2007}, abstract = {This paper reviews George Dantzig's contribution to integer programming, especially his seminal work with Fulkerson and Johnson on the traveling salesman problem}, language = {en} } @incollection{GroetschelFonsecaDavis2001, author = {Gr{\"o}tschel, Martin and Fonseca, Irene and Davis, Mark}, title = {The Impact of Mathematical Research on Industry and Vice Versa}, booktitle = {Mathematical Glimpses into the 21st Century}, editor = {Casacuberta, Carles and Mir{\´o}-Roig, Rosa and Ortega, Joaqu{\´i}n and Xamb{\´o}-Descamps, Sebasti{\`a}}, edition = {First}, publisher = {Societat Catalana de Matem{\`a}tiques and Centro Internacional de M{\´e}todos Num{\´e}ricos en Ingenier{\´i}a}, address = {Barcelona, Spain}, pages = {35 -- 53}, year = {2001}, language = {en} } @incollection{GroetschelLoebelVoelker1997, author = {Gr{\"o}tschel, Martin and L{\"o}bel, Andreas and V{\"o}lker, Manfred}, title = {Optimierung des Fahrzeugumlaufs im {\"O}ffentlichen Nahverkehr}, booktitle = {Mathematik}, editor = {Hoffmann, Karl-Heinz and J{\"a}ger, Willi and Lohmann, Thomas and Schunck (Hrsg.), Hermann}, publisher = {Springer}, pages = {609 -- 624}, year = {1997}, language = {en} } @inproceedings{Groetschel2000, author = {Gr{\"o}tschel, Martin}, title = {Frequency Assignment in Mobile Phone Systems}, volume = {1974}, booktitle = {FST TCS 2000}, editor = {Kapoor, Sanjiv and Prasad, Sanjiva}, publisher = {Springer}, pages = {81 -- 86}, year = {2000}, language = {en} } @misc{GroetschelKrumkeRambauetal.2002, author = {Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg and Torres, Luis Miguel}, title = {Making the Yellow Angels Fly: Online Dispatching Of Service Vehicles in Real Time}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6858}, number = {02-18}, year = {2002}, abstract = {Combinatorial online optimization is an area with lots of applications and potential for significant progress, both in theory and practice. In this short note we sketch the ADACproblem, a typical large-scale online optimization problem, discuss some theoretical and pratical issues coming up, and explain, very briefly, how we approach this problem mathematically. Online problems are a battlefield of heuristics with many strong claims about their solution quality. We indicate that a stronger problem orientation and the use of a little more mathematics may yield.}, language = {en} } @misc{Groetschel2002, author = {Gr{\"o}tschel, Martin}, title = {Cardinality Homogeneous Set Systems, Cycles in Matroids, and Associated Polytopes}, doi = {10.1137/1.9780898718805.ch8}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6868}, number = {02-19}, year = {2002}, abstract = {A subset \${\cal C}\$ of the power set of a finite set \$E\$ is called cardinality homogeneous if, whenever \${\cal C}\$ contains some set \$F\$, \${\cal C}\$ contains all subsets of \$E\$ of cardinality \$|F|\$. Examples of such set systems \${\cal C}\$ are the sets of circuits and the sets of cycles of uniform matroids and the sets of all even or of all odd cardinality subsets of \$E\$. With each cardinality homogeneous set system \${\cal C}\$, we associate the polytope \$P({\cal C})\$, the convex hull of the incidence vectors of all sets in \${\cal C}\$, and provide a complete and nonredundant linear description of \$P({\cal C})\$. We show that a greedy algorithm optimizes any linear function over \$P({\cal C})\$, give an explicit optimum solution of the dual linear program, and provide a polynomial time separation algorithm for the class of polytopes of type \$P({\cal C})\$.}, language = {en} } @misc{Groetschel2002, author = {Gr{\"o}tschel, Martin}, title = {P=NP?}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6939}, number = {02-26}, year = {2002}, abstract = {Hinter der f{\"u}r den Uneingeweihten etwas kryptischen Frage "P = NP?" verbirgt sich das derzeit wichtigste Problem der Komplexit{\"a}tstheorie. Dieser Artikel erl{\"a}utert einige Aspekte der Theorie und erkl{\"a}rt informell, was "P = NP?" bedeutet. Es geht nicht nur um komplizierte algorithmische Mathematik und Informatik, sondern um grunds{\"a}tzliche Fragen unserer Lebensumwelt. Kann man vielleicht beweisen, dass es f{\"u}r viele Probleme unseres Alltags keine effizienten L{\"o}sungsmethoden gibt?}, language = {de} } @misc{GroetschelLueggerSperber1996, author = {Gr{\"o}tschel, Martin and L{\"u}gger, Joachim and Sperber, Wolfram}, title = {DMV-Vorhaben. "Verbesserung des benutzerorientierten Zugriffs auf fachspezifische Online-Datenbanken und CD-ROM f{\"u}r Mathematische Institute der Bundesrepublik Deutschland"}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5318}, number = {TR-96-02}, year = {1996}, abstract = {Der Report analysiert die Ergebnisse des Projektes ,,Verbesserung des benutzerorientierten Zugriffs auf fachspezifische Online und CD-ROM Datenbanken f{\"u}r Mathematische Institute der Bundesrepublik Deutschland'' der Deutschen Mathematiker-Vereinigung. An dem Projekt, das vom ZIB geleitet und koordiniert worden ist, haben mehr als 50 mathematische Fachbereiche und Forschungsinstitute teilgenommen. Dieses vom damaligen BMFT (einem Teil des jetzigen Bundesministeriums f{\"u}r Bildung, Wissenschaft, Forschung und Technologie) gef{\"o}rderte Projekt hat wesentlich dazu beigetragen, dass fachspezifische Datenbanken heute in den mathematischen Fachbereichen in Deutschland zu den selbstverst{\"a}ndlichen Arbeitsmitteln geh{\"o}ren. Dar{\"u}ber hinaus hat das Projekt die Grundlagen f{\"u}r eine moderne elektronische Informations- und Kommunikationsstruktur in den mathematischen Fachbereichen gelegt.}, language = {de} } @misc{GroetschelLuegger1996, author = {Gr{\"o}tschel, Martin and L{\"u}gger, Joachim}, title = {Neue Produkte f{\"u}r die digitale Bibliothek: die Rolle der Wissenschaften}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5343}, number = {TR-96-05}, year = {1996}, abstract = {Der Artikel ist die ausgearbeitete und erweiterte Fassung eines eingeladenen Vortrags der Tagung ,,Die unendliche Bibliothek - Digitale Information in Wissenschaft, Verlag und Bibliothek''. Dieses Treffen, eine Veranstaltung des B{\"o}rsenvereins des Deutschen Buchhandels e.V., der Deutschen Bibliothek und der Bundesvereinigung Deutscher Bibliothkesverb{\"a}nde, fand im Dezember 1995 in Bonn als Beitrag zur der heute aktuellen Debatte unter Wissenschaftlern, Verlegern, Buchh{\"a}ndlern, Bibliothekaren und Politikern statt, wie unser Wissen und unsere Informationen digital transferiert werden k{\"o}nnen. Der Vortrag stellte das zentrale Problem des heutigen wissenschaftlichen Informationswesens dar, die gleichzeitige Existenz von Informationsflut und Informationsmangel. Nach einer knappen Bestimmung der Ver{\"a}nderung der Kommunikationsstrukturen in den Wissenschaften fragte er nach den essentiellen Ver{\"a}nderungen der Informationsarten, d.h. nach der Natur der kommenden Globalen Digitalen Bibliothek, die als ein {\"u}ber die ganze Welt und auf viele Institutionen verteilter globaler Speicher gesehen wird. Der Vortrag diskutierte zum Schluss die Bed{\"u}rfnisse und Interessen der Wissenschaften und ihre spezifische Verantwortung beim {\"U}bergang in die elektronische Welt. Der Tagungsband ist erschienen beim Harrassowitz Verlag, Wiesbaden, 1996.}, language = {de} } @misc{GroetschelLuegger1996, author = {Gr{\"o}tschel, Martin and L{\"u}gger, Joachim}, title = {Wissenschaftliche Information und Kommunikation im Umbruch}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5365}, number = {TR-96-07}, year = {1996}, abstract = {Steht uns das Ende des traditionellen wissenschaftlichen Publizierens bevor? Neue Technologien er{\"o}ffnen neue Chancen zur Bew{\"a}ltigung der Informationsflut und des gleichzeitigen Informationsmangels. Doch der Einsatz von Technik allein reicht nicht aus.}, language = {de} }