@misc{BosseGroetschelHenk2004, author = {Bosse, Hartwig and Gr{\"o}tschel, Martin and Henk, Martin}, title = {Polynomial Inequalities Representing Polyhedra}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8284}, number = {04-53}, year = {2004}, abstract = {Our main result is that every \$n\$-dimensional polytope can be described by at most \$2n-1\$ polynomial inequalities and, moreover, these polynomials can explicitly be constructed. For an \$n\$-dimensional pointed polyhedral cone we prove the bound \$2n-2\$ and for arbitrary polyhedra we get a constructible representation by \$2n\$ polynomial inequalities.}, language = {en} } @misc{GroetschelMartinWeismantel1995, author = {Gr{\"o}tschel, Martin and Martin, Alexander and Weismantel, Robert}, title = {Optimum Path Packing on Wheels: The Consecutive Case}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1976}, number = {SC-95-31}, year = {1995}, abstract = {We show that, given a wheel with nonnegative edge lengths and pairs of terminals located on the wheel's outer cycle such that the terminal pairs are in consecutive order, then a path packing, i.~e., a collection of edge disjoint paths connecting the given terminal pairs, of minimum length can be found in strongly polynomial time. Moreover, we exhibit for this case a system of linear inequalities that provides a complete and nonredundant description of the path packing polytope, which is the convex hull of all incidence vectors of path packings and their supersets.}, language = {en} } @misc{GroetschelMartinWeismantel1994, author = {Gr{\"o}tschel, Martin and Martin, Alexander and Weismantel, Robert}, title = {The Steiner Tree Packing Problem in VLSI-Design.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1328}, number = {SC-94-02}, year = {1994}, abstract = {In this paper we describe several versions of the routing problem arising in VLSI design and indicate how the Steiner tree packing problem can be used to model these problems mathematically. We focus on switchbox routing problems and provide integer programming formulations for routing in the knock-knee and in the Manhattan model. We give a brief sketch of cutting plane algorithms that we developed and implemented for these two models. We report on computational experiments using standard test instances. Our codes are able to determine optimum solutions in most cases, and in particular, we can show that some of the instances have no feasible solution if Manhattan routing is used instead of knock-knee routing.}, language = {en} } @misc{GroetschelMartinWeismantel1993, author = {Gr{\"o}tschel, Martin and Martin, Alexander and Weismantel, Robert}, title = {Optimum Path Packing on Wheels: The Noncrossing Case.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1225}, number = {SC-93-26}, year = {1993}, abstract = {We show that, given a wheel with nonnegative edge lengths and pairs of terminals located on the wheel's outer cycle such that no two terminal pairs cross, then a path packing, i.~e.,a collection of edge disjoint paths connecting the given terminal pairs, of minimum length can be found in strongly polynomial time. Moreover, we exhibit for this case a system of linear inequalities that provides a complete and nonredundant description of the path packing polytope, which is the convex hull of all incidence vectors of path packings and their supersets.}, language = {en} } @misc{GroetschelMartinWeismantel1992, author = {Gr{\"o}tschel, Martin and Martin, Alexander and Weismantel, Robert}, title = {Packing Steiner Trees: Polyhedral Investigations.}, doi = {10.1007/BF02592085}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-786}, number = {SC-92-08}, year = {1992}, abstract = {Let \$G=(V,E)\$ be a graph and \$T\subseteq V\$ be a node set. We call an edge set \$S\$ a Steiner tree with respect to \$T\$ if \$S\$ connects all pairs of nodes in \$T\$. In this paper we address the following problem, which we call the weighted Steiner tree packing problem. Given a graph \$G=(V,E)\$ with edge weights \$w_e\$, edge capacities \$c_e, e \in E,\$ and node sets \$T_1,\ldots,T_N\$, find edge sets \$S_1,\ldots,S_N\$ such that each \$S_k\$ is a Steiner tree with respect to \$T_k\$, at most \$c_e\$ of these edge sets use edge \$e\$ for each \$e\in E\$, and such that the sum of the weights of the edge sets is minimal. Our motivation for studying this problem arises from the routing problem in VLSI-design, where given sets of points have to be connected by wires. We consider the Steiner tree packing Problem from a polyhedral point of view and define an appropriate polyhedron, called the Steiner tree packing polyhedron. The goal of this paper is to (partially) describe this polyhedron by means of inequalities. It turns out that, under mild assumptions, each inequality that defines a facet for the (single) Steiner tree polyhedron can be lifted to a facet-defining inequality for the Steiner tree packing polyhedron. The main emphasis of this paper lies on the presentation of so-called joint inequalities that are valid and facet-defining for this polyhedron. Inequalities of this kind involve at least two Steiner trees. The classes of inequalities we have found form the basis of a branch \& cut algorithm. This algorithm is described in our companion paper SC 92-09.}, language = {en} } @misc{GroetschelMartinWeismantel1992, author = {Gr{\"o}tschel, Martin and Martin, Alexander and Weismantel, Robert}, title = {Packing Steiners Trees: A Cutting Plane Algorithm and Computational Results.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-792}, number = {SC-92-09}, year = {1992}, abstract = {In this paper we describe a cutting plane algorithm for the Steiner tree packing problem. We use our algorithm to solve some switchbox routing problems of VLSI-design and report on our computational experience. This includes a brief discussion of separation algorithms, a new LP-based primal heuristic and implementation details. The paper is based on the polyhedral theory for the Steiner tree packing polyhedron developed in our companion paper SC 92-8 and meant to turn this theory into an algorithmic tool for the solution of practical problems.}, language = {en} } @misc{FerreiraGroetschelKiefletal.1993, author = {Ferreira, Carlos E. and Gr{\"o}tschel, Martin and Kiefl, Stefan and Krispenz, Ludwig and Martin, Alexander and Weismantel, Robert}, title = {Some Integer Programs Arising in the Design of Main Frame Computers.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-957}, number = {SC-92-25}, year = {1993}, abstract = {In this paper we describe and discuss a problem that arises in the (global) design of a main frame computer. The task is to assign certain functional units to a given number of so called multi chip modules or printed circuit boards taking into account many technical constraints and minimizing a complex objective function. We describe the real world problem. A thorough mathematical modelling of all aspects of this problem results in a rather complicated integer program that seems to be hopelessly difficult -- at least for the present state of integer programming technology. We introduce several relaxations of the general model, which are also \$NP\$-hard, but seem to be more easily accessible. The mathematical relations between the relaxations and the exact formulation of the problem are discussed as well.}, language = {en} } @misc{GroetschelMartinWeismantel1992, author = {Gr{\"o}tschel, Martin and Martin, Alexander and Weismantel, Robert}, title = {Routing in Grid Graphs by Cutting Planes.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-967}, number = {SC-92-26}, year = {1992}, abstract = {{\def\N{{\cal N}} \def\R{\hbox{\rm I\kern-2pt R}} \def\MN{{\rm I\kern-2pt N}} In this paper we study the following problem, which we call the weighted routing problem. Let be given a graph \$G=(V,E)\$ with non-negative edge weights \$w_e\in\R_+\$ and integer edge capacities \$c_e\in\MN\$ and let \$\N=\{T_1,\ldots,T_N\}\$, \$N\ge 1\$, be a list of node sets. The weighted routing problem consists in finding edge sets \$S_1,\ldots,S_N\$ such that, for each \$k\in\{1,\ldots,N\}\$, the subgraph \$(V(S_k),S_k)\$ contains an \$[s,t]\$-path for all \$s,t\in T_k\$, at most \$c_e\$ of these edge sets use edge \$e\$ for each \$e\in E\$, and such that the sum of the weights of the edge sets is minimal. Our motivation for studying this problem arises from the routing problem in VLSI-design, where given sets of points have to be connected by wires. We consider the weighted routing problem from a polyhedral point of view. We define an appropriate polyhedron and try to (partially) describe this polyhedron by means of inequalities. We briefly sketch our separation algorithms for some of the presented classes of inequalities. Based on these separation routines we have implemented a branch and cut algorithm. Our algorithm is applicable to an important subclass of routing problems arising in VLSI-design, namely to problems where the underlying graph is a grid graph and the list of node sets is located on the outer face of the grid. We report on our computational experience with this class of problem instances.}}, language = {en} } @misc{GroetschelMartinWeismantel1992, author = {Gr{\"o}tschel, Martin and Martin, Alexander and Weismantel, Robert}, title = {Packing Steiner Trees: Further Facets.}, doi = {10.1006/eujc.1996.0004}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-975}, number = {SC-93-01}, year = {1992}, abstract = {In this paper we continue the investigations in [GMW92a] for the \def\sbppo{Steiner tree packing polyhedron} \sbppo. We present several new classes of valid inequalities and give sufficient (and necessary) conditions for these inequalities to be facet-defining. It is intended to incorporate these inequalities into an existing cutting plane algorithm that is applicable to practical problems arising in the design of electronic circuits.}, language = {en} } @misc{GroetschelMartinWeismantel1992, author = {Gr{\"o}tschel, Martin and Martin, Alexander and Weismantel, Robert}, title = {Packing Steiner Trees: Separation Algorithms.}, doi = {10.1137/S0895480193258716}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-984}, number = {SC-93-02}, year = {1992}, abstract = {In this paper we investigate separation problems for classes of inequalities valid for the polytope associated with the Steiner tree packing problem, a problem that arises, e.~g., in VLSI routing. The separation problem for Steiner partition inequalities is \${\cal N}\hskip-2pt{\cal P}\$-hard in general. We show that it can be solved in polynomial time for those instances that come up in switchbox routing. Our algorithm uses dynamic programming techniques. These techniques are also applied to the much more complicated separation problem for alternating cycle inequalities. In this case we can compute in polynomial time, given some point \$y\$, a lower bound for the gap \$\alpha-a^Ty\$ over all alternating cycle inequalities \$a^Tx\ge\alpha\$. This gives rise to a very effective separation heuristic. A by-product of our algorithm is the solution of a combinatorial optimization problem that is interesting in its own right: Find a shortest path in a graph where the ``length'' of a path is its usual length minus the length of its longest edge.}, language = {en} } @misc{BorndoerferEisenblaetterGroetscheletal.1997, author = {Bornd{\"o}rfer, Ralf and Eisenbl{\"a}tter, Andreas and Gr{\"o}tschel, Martin and Martin, Alexander}, title = {Frequency Assignment in Cellular Phone Networks}, doi = {10.1023/A:1018908907763}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3044}, number = {SC-97-35}, year = {1997}, abstract = {We present a graph-theoretic model for the \emph{frequency assignment problem} in Cellular Phone Networks: Obeying several technical and legal restrictions, frequencies have to be assigned to transceivers so that interference is as small as possible. This optimization problem is NP-hard. Good approximation cannot be guaranteed, unless P = NP. We describe several assignment heuristics. These heuristics are simple and not too hard to implement. We give an assessment of the heuristics' efficiency and practical usefulness. For this purpose, typical instances of frequency assignment problems with up to 4240 transceivers and 75 frequencies of a German cellular phone network operator are used. The results are satisfying from a practitioner's point of view. The best performing heuristics were integrated into a network planning system used in practice.}, language = {en} } @misc{GroetschelHenk2002, author = {Gr{\"o}tschel, Martin and Henk, Martin}, title = {On the Representation of Polyhedra by Polynomial Inequalities}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6826}, number = {02-15}, year = {2002}, abstract = {A beautiful result of Br{\"o}cker and Scheiderer on the stability index of basic closed semi-algebraic sets implies, as a very special case, that every \$d\$-dimensional polyhedron admits a representation as the set of solutions of at most \$d(d+1)/2\$ polynomial inequalities. Even in this polyhedral case, however, no constructive proof is known, even if the quadratic upper bound is replaced by any bound depending only on the dimension. Here we give, for simple polytopes, an explicit construction of polynomials describing such a polytope. The number of used polynomials is exponential in the dimension, but in the 2- and 3-dimensional case we get the expected number \$d(d+1)/2\$.}, language = {en} } @misc{BosseGroetschelHenk2003, author = {Bosse, Hartwig and Gr{\"o}tschel, Martin and Henk, Martin}, title = {Polynomial Inequalities Representing Polyhedra}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7473}, number = {03-25}, year = {2003}, abstract = {Our main result is that every n-dimensional polytope can be described by at most (2n-1) polynomial inequalities and, moreover, these polynomials can explicitly be constructed. For an n-dimensional pointed polyhedral cone we prove the bound 2n-2 and for arbitrary polyhedra we get a constructible representation by 2n polynomial inequalities.}, language = {en} } @misc{BorndoerferEisenblaetterGroetscheletal.1998, author = {Bornd{\"o}rfer, Ralf and Eisenbl{\"a}tter, Andreas and Gr{\"o}tschel, Martin and Martin, Alexander}, title = {The Orientation Model for Frequency Assignment Problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5627}, number = {TR-98-01}, year = {1998}, abstract = {Mobile telecommunication systems establish a large number of communication links with a limited number of available frequencies; reuse of the same or adjacent frequencies on neighboring links causes interference. The task to find an assignment of frequencies to channels with minimal interference is the frequency assignment problem. The frequency assignment problem is usually treated as a graph coloring problem where the number of colors is minimized, but this approach does not model interference minimization correctly. We give in this paper a new integer programming formulation of the frequency assignment problem, the orientation model, and develop a heuristic two-stage method to solve it. The algorithm iteratively solves an outer and an inner optimization problem. The outer problem decides for each pair of communication links which link gets the higher frequency and leads to an acyclic subdigraph problem with additional longest path restrictions. The inner problem to find an optimal assignment respecting an orientation leads to a min-cost flow problem.}, language = {en} } @article{GroetschelMartinWeismantel1996, author = {Gr{\"o}tschel, Martin and Martin, Alexander and Weismantel, Robert}, title = {Packing Steiner trees: Polyhedral Investigations}, volume = {72}, journal = {Mathematical Programming, Series A}, number = {2}, doi = {10.1007/BF02592085}, pages = {101 -- 123}, year = {1996}, language = {en} } @article{GroetschelMartinWeismantel1996, author = {Gr{\"o}tschel, Martin and Martin, Alexander and Weismantel, Robert}, title = {Optimum Path Packing on Wheels}, volume = {31}, journal = {Computers and Mathematics with Applications}, number = {11}, publisher = {Elsevier}, pages = {23 -- 35}, year = {1996}, language = {en} } @article{BosseGroetschelHenk2005, author = {Bosse, Hartwig and Gr{\"o}tschel, Martin and Henk, Martin}, title = {Polynomial inequalities representing polyhedra}, volume = {103}, journal = {Mathematical Programming}, number = {1}, doi = {10.1007/s10107-004-0563-2}, pages = {35 -- 44}, year = {2005}, language = {en} } @article{GroetschelHenk2003, author = {Gr{\"o}tschel, Martin and Henk, Martin}, title = {The Representation of Polyhedra by Polynomial Inequalities}, volume = {29}, journal = {Discrete \& Computational Geometry}, number = {4}, doi = {10.1007/s00454-003-0782-y}, pages = {485 -- 504}, year = {2003}, language = {en} } @article{BorndoerferEisenblaetterGroetscheletal.1998, author = {Bornd{\"o}rfer, Ralf and Eisenbl{\"a}tter, Andreas and Gr{\"o}tschel, Martin and Martin, Alexander}, title = {Frequency assignment in cellular phone networks}, volume = {76}, journal = {Annals of Operations Research}, publisher = {J. C. Baltzer AG, Science Publishers}, doi = {10.1023/A:1018908907763}, pages = {73 -- 93}, year = {1998}, language = {en} } @article{GroetschelMartinWeismantel1996, author = {Gr{\"o}tschel, Martin and Martin, Alexander and Weismantel, Robert}, title = {Packing Steiner trees: a cutting plane algorithm and computational results}, volume = {72}, journal = {Mathematical Programming, Series A}, number = {2}, doi = {10.1007/BF02592086}, pages = {125 -- 145}, year = {1996}, language = {en} } @article{GroetschelMartinWeismantel1997, author = {Gr{\"o}tschel, Martin and Martin, Alexander and Weismantel, Robert}, title = {The Steiner tree packing problem in VLSI design}, volume = {78}, journal = {Mathematical Programming}, number = {2}, pages = {265 -- 281}, year = {1997}, language = {en} } @inproceedings{GroetschelMartinWeismantel1993, author = {Gr{\"o}tschel, Martin and Martin, Alexander and Weismantel, Robert}, title = {Routing in grid graphs by cutting planes}, booktitle = {Integer Programming and Combinatorial Optimization. Proceedings of a Conference held at Centro Ettore Majorana, Erice, Italy, April 29 - May 1, 1993}, editor = {Rinaldi, Giovanni and Wolsey, Laurence}, publisher = {Librarian CORE}, address = {Louvain-la-Neuve}, pages = {447 -- 461}, year = {1993}, language = {en} } @article{FerreiraGroetschelMartinetal.1993, author = {Ferreira, Carlos and Gr{\"o}tschel, Martin and Martin, Alexander and Weismantel, Robert and Kiefl, Stefan and Krispenz, Ludwig}, title = {Some Integer Programs Arising in the Design of Main Frame Computers}, volume = {38}, journal = {ZOR - Methods and Models of Operations Research}, number = {1}, pages = {77 -- 100}, year = {1993}, language = {en} } @article{GroetschelMartinWeismantel1995, author = {Gr{\"o}tschel, Martin and Martin, Alexander and Weismantel, Robert}, title = {Routing in Grid Graphs by Cutting Planes}, volume = {41}, journal = {ZOR - Mathematical Methods of Operations Research}, number = {3}, pages = {255 -- 275}, year = {1995}, language = {en} } @article{GroetschelMartinWeismantel1996, author = {Gr{\"o}tschel, Martin and Martin, Alexander and Weismantel, Robert}, title = {Packing Steiner Trees: Separation Algorithms}, volume = {9}, journal = {SIAM Journal on Discrete Mathematics}, number = {2}, doi = {10.1137/S0895480193258716}, pages = {233 -- 257}, year = {1996}, language = {en} } @article{GroetschelMartinWeismantel1996, author = {Gr{\"o}tschel, Martin and Martin, Alexander and Weismantel, Robert}, title = {Packing Steiner Trees: Further Facets}, volume = {17}, journal = {European Journal of Combinatorics}, number = {1}, doi = {10.1006/eujc.1996.0004}, pages = {39 -- 52}, year = {1996}, language = {en} } @inproceedings{BorndoerferEisenblaetterGroetscheletal.1996, author = {Bornd{\"o}rfer, Ralf and Eisenbl{\"a}tter, Andreas and Gr{\"o}tschel, Martin and Martin, Alexander}, title = {Stable-Set and Other Techniques for Frequency Assignment Problems}, booktitle = {Anais da I Oficina Nacional em Problemas de Corte \& Empacotamento}, publisher = {Universidade de S{\~a}o Paulo, Instituto de Matem{\´a}tica e Estat{\´i}stica}, pages = {17 -- 21}, year = {1996}, language = {en} } @misc{GroetschelLuegger2009, author = {Gr{\"o}tschel, Martin and L{\"u}gger, Joachim}, title = {Ver{\"a}nderungen der Publikations- und Kommunikationswelt: Open Access, Google, etc.}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11223}, number = {09-10}, year = {2009}, abstract = {Vorbemerkung Beim Schreiben dieses Artikels, der auf Ver{\"a}nderungen der Kommunikations- und Publikationstechniken und ihre Bedeutung hinweist, ist uns mehr als je zuvor bewusst geworden, wie beschr{\"a}nkt das Medium Papier ist. Es gibt z. B. keine Hyperlinks, durch die man unmittelbar das Erw{\"a}hnte erleben oder {\"u}berpr{\"u}fen kann. Ein schneller Wechsel vom Wort zum Bild, zum Ton oder Video ist nicht m{\"o}glich. Wer will schon lange URLs abtippen und Medienbr{\"u}che erleiden? Wir haben uns daher entschlossen, eine textidentische Version dieses Artikels mit allen URLs - sie liegt Ihnen hier vor - elektronisch anzubieten und in der f{\"u}r die "Gegenworte" (BBAW) gek{\"u}rzten Fassung nur durch [URL] anzudeuten, dass der Leser an dieser Stelle einfach in der elektronischen Version einen Klick ins Internet machen sollte. Und damit sind wir bereits mitten im Thema.}, language = {de} } @misc{GroetschelLuegger2009, author = {Gr{\"o}tschel, Martin and L{\"u}gger, Joachim}, title = {E-Learning and the Working Mathematician}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11455}, number = {09-29}, year = {2009}, abstract = {Eigentlich war der erste Autor nur zu einem Grußwort zur Tagung „GML² 2009 - Grundfragen Multi¬medialen Lehrens und Lernens" eingeladen. Daraus wurde ein E-Learning-bezogener Vortrag, der - basierend auf Erfahrungen im Fach Mathematik - einen kritischen Blick auf die E-Learning-Szene in Deutschland wirft und diese mit entsprechenden Aktivit{\"a}ten weltweit vergleicht. Dies ist die in seinen mathematischen Teilen gek{\"u}rzte, in den E-Learning-Anteilen ein wenig erweiterte schriftliche Fassung des Vortrags. Der Artikel stammt nicht von E-Learning-Spezialisten sondern von Personen, die sich seit fast zwanzig Jahren mit elektronischer Information und Kommunikation (kurz: IuK) - insbesondere in der Mathematik - besch{\"a}ftigen. Nach einer Definition von Michael Kerres kennzeichnet der Begriff E-Learning (electronic learning - elektronisch unterst{\"u}tztes Lernen) alle Formen von Lernen, bei denen digitale Medien f{\"u}r die Pr{\"a}sentation und Distribution von Lernmaterialien und/oder zur Unterst{\"u}tzung zwischenmenschlicher Kommunikation zum Einsatz kommen, siehe z.B. http://de.wikipedia.org/wiki/E-Learning. IuK und E-Learning haben nach dieser Begriffsbildung viele Ber{\"u}hrungspunkte. Deswegen wagen wir es, unsere positiven und negativen Erfahrungen im Bereich IuK in diesem Er{\"o}ffnungsvortrag zu berichten, einige Entwicklungslinien zu vergleichen und eine eigene Kurzversion der Definition von E-Learning (besser E-Teaching and -Learning) voranzustellen: „Lehren und Lernen mit Unterst{\"u}tzung elektronischer Hilfsmittel".}, language = {de} } @misc{Groetschel2005, author = {Gr{\"o}tschel, Martin}, title = {Das Problem mit der Komplexit{\"a}t: P = NP?}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8916}, number = {05-58}, year = {2005}, abstract = {Was Komplexit{\"a}t ist, weiß niemand so richtig. In vielen Wissenschaftsgebieten wird der Begriff Komplexit{\"a}t verwendet, {\"u}berall mit etwas anderer Bedeutung. Mathematik und Informatik hab en eine eigene Theorie hierzu entwickelt: die Komplexit{\"a}tstheorie. Sie stellt zwar grundlegende Begriffe bereit, aber leider sind die meisten wichtigen Fragestellungen noch ungel{\"o}st. Diese kurze Einf{\"u}hrung konzentriert sich auf einen speziellen, aber bedeutenden Aspekt der Theorie: L{\"o}sbarkeit von Problemen in deterministischer und nichtdeterministischer polynomialer Zeit. Hinter der f{\"u}r Uneingeweihte etwas kryptischen Frage "P = NP?" verbirgt sich das derzeit wichtigste Problem der Komplexit{\"a}tstheorie. Anhand dieser Fragestellung werden einige Aspekte der Theorie erl{\"a}utert und formell erkl{\"a}rt, 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{BorndoerferGroetschelPfetsch2005, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and Pfetsch, Marc}, title = {A Column-Generation Approach to Line Planning in Public Transport}, doi = {/10.1287/trsc.1060.0161}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8522}, number = {05-18}, year = {2005}, abstract = {The line planning problem is one of the fundamental problems in strategic planning of public and rail transport. It consists in finding lines and corresponding frequencies in a transport network such that a given travel demand can be satisfied. There are (at least) two objectives. The transport company wishes to minimize operating costs, the passengers want to minimize travel times. We propose a n ew multi-commodity flow model for line planning. Its main features, in comparison to existing models, are that the passenger paths can be freely routed and that the lines are generated dynamically. We discuss properties of this model and investigate its complexity. Results with data for the city of Potsdam, Germany, are reported.}, language = {en} } @misc{BorndoerferGroetschelPfetsch2005, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and Pfetsch, Marc}, title = {Public Transport to the fORe!}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8562}, number = {05-22}, year = {2005}, abstract = {Can OR methods help the public transport industry to break even? The article gives evidence that there exist significant potentials in this direction, which can be harnessed by a combination of modern mathematical methods and local planning knowledge. Many of the planning steps in public transport are classical combinatorial problems, which can be solved in unprecedented size and quality due the rapid progress in large-scale optimization. Three examples on vehicle scheduling, duty scheduling, and integrated vehicle and duty scheduling illustrate the level that has been reached and the improvements that can be achieved today. Extensions of such methods to further questions of strategic, online, and market-oriented planning are currently investigated. In this way, OR can make a significant contribution to answer the basic but extremely difficult question ``What is a good public transport network?.}, language = {en} } @misc{GroetschelRoggenbuckSperber2005, author = {Gr{\"o}tschel, Martin and Roggenbuck, Robert and Sperber, Wolfram}, title = {Entwicklung und Aufbau des Internet-Dienstes "Math\&Industry"}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8573}, number = {05-23}, year = {2005}, abstract = {Die Anwendung mathematischer Methoden und Verfahren wird immer mehr zur Voraussetzung innovativer Produkte und Dienstleistungen. Um neue Produkte und Dienstleistungen zu entwickeln, m{\"u}ssen die Produktions- und technologischen Prozesse mathematisch modelliert, beschrieben und optimiert werden. Diesen Umstand Rechnung tragend, hat das Bundesministerium f{\"u}r Bildung und Forschung (BMBF) 1993 begonnen, den Einsatz mathematischer Verfahren und Methoden in der Mathematik {\"u}ber ein spezielles Mathematikprogramm zu f{\"o}rdern. Inzwischen hat die vierte F{\"o}rderperiode des Mathematikprogramms begonnen. \par Das Medium Internet und insbesondere das WWW sind f{\"u}r die Sichtbarkeit und Transparenz wissenschaftlicher Resultate in den letzten zehn Jahren immer wichtiger geworden. Wer nicht im Web "'sichtbar"' ist, l{\"a}uft Gefahr, nicht wahrgenommen zu werden. Intention und Ziel des durchgef{\"u}hrten Projekts war es, ein Konzept f{\"u}r eine qualitativ hochwertige und umfassende Darstellung des BMBF Mathematikprogramms, insbesondere der in den Projekten erzielten Ergebnisse, zu entwickeln und zu realisieren und damit den Stellenwert und die Akzeptanz mathematischer Forschung in der Gesellschaft zu festigen und den Wissenstransfer zwischen mathematischer Forschung sowie Forschung und Entwicklung in der Wirtschaft und dem Dienstleistungsbereich zu f{\"o}rdern.}, language = {de} } @misc{Groetschel2005, author = {Gr{\"o}tschel, Martin}, title = {Schnelle Rundreisen: Das Travelling Salesman-Problem}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8901}, number = {05-57}, year = {2005}, abstract = {Das Travelling-Salesman-Problem (TSP) ist das am intensivsten untersuchte kombinatorische Optimierungsproblem. In diesem Abschnitt wird eine Einf{\"u}hrung in das TSP gegeben. Es werden Problemstellungen erl{\"a}utert, Anwendungen skizziert und einige Schwierigkeiten bei der korrekten Modellierung der Zielfunktion dargelegt. Es ist gar nicht so klar, was in einem konkreten Problem die wirkliche Entfernung ist. Exakte und approximative L{\"o}sungsverfahren werden an Beispielen skizziert, und es wird angedeutet, dass man, obwohl TSPs zu den theoretisch schweren Problemen z{\"a}hlen, in der Praxis TSPs von atemberaubender Gr{\"o}ße l{\"o}sen kann.}, language = {de} } @misc{GroetschelHinrichsSchroeeretal.2006, author = {Gr{\"o}tschel, Martin and Hinrichs, Hinrich and Schr{\"o}er, Klaus and Tuchscherer, Andreas}, title = {Ein gemischt-ganzzahliges lineares Optimierungsmodell f{\"u}r ein Laserschweißproblem im Karosseriebau}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9141}, number = {06-21}, year = {2006}, abstract = {Wir besch{\"a}ftigen uns mit dem Problem der Betriebsplanung von Laserschweißrobotern im Karosseriebau. Gegeben ist eine Menge von Schweißn{\"a}hten, die innerhalb einer Fertigungszelle an einem Karosserieteil gefertigt werden m{\"u}ssen. Die Schweißn{\"a}hte werden durch mehrere parallel betriebene Roboter bearbeitet. Die Aufgabe besteht darin, f{\"u}r jeden Roboter eine Reihenfolge und eine zeitliche Koordinierung seiner Bewegungen zu finden, so dass alle Schweißn{\"a}hte innerhalb der Taktzeit der Fertigungszelle bearbeitet werden und so wenig Laserquellen wie m{\"o}glich eingesetzt werden. Dabei m{\"u}ssen einige Nebenbedingungen ber{\"u}cksichtigt werden. F{\"u}r dieses spezielle Schweißproblem haben wir eine Formulierung als gemischt-ganzzahliges lineares Programm entwickelt, welches sich f{\"u}r die untersuchten praktischen F{\"a}lle sehr schnell l{\"o}sen l{\"a}sst.}, language = {de} } @misc{AchterbergGroetschelKoch2006, author = {Achterberg, Tobias and Gr{\"o}tschel, Martin and Koch, Thorsten}, title = {Software for Teaching Modeling of Integer Programming Problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9176}, number = {06-23}, year = {2006}, abstract = {Modern applications of mathematical programming must take into account a multitude of technical details, business demands, and legal requirements. Teaching the mathematical modeling of such issues and their interrelations requires real-world examples that are well beyond the toy sizes that can be tackled with the student editions of most commercial software packages. We present a new tool, which is freely available for academic use including complete source code. It consists of an algebraic modeling language and a linear mixed integer programming solver. The performance and features of the tool are in the range of current state-of-the-art commercial tools, though not in all aspects as good as the best ones. Our tool does allow the execution and analysis of large real-world instances in the classroom and can therefore enhance the teaching of problem solving issues. Teaching experience has been gathered and practical usability was tested in classes at several universities and a two week intensive block course at TU Berlin. The feedback from students and teachers has been very positive.}, language = {en} } @misc{BorndoerferGroetschelLoebel2000, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and L{\"o}bel, Andreas}, title = {Der schnellste Weg zum Ziel}, journal = {Alles Mathematik}, editor = {Aigner, Martin and Behrends, Ehrhard}, publisher = {Vieweg Verlag}, address = {Braunschweig/Wiesbaden}, doi = {10.1007/978-3-322-96366-6_5}, pages = {45 -- 76}, year = {2000}, language = {en} } @incollection{BorndoerferGroetschelJaeger2008, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and Jaeger, Ulrich}, title = {Planungsprobleme im {\"o}ffentlichen Verkehr}, booktitle = {PRODUKTIONSFAKTOR MATHEMATIK - Wie Mathematik Technik und Wirtschaft bewegt}, editor = {Gr{\"o}tschel, Martin and Lucas, Klaus and Mehrmann, Volker}, publisher = {acatech - Deutsche Akademie der Technikwissenschaften und Springer}, pages = {127 -- 153}, year = {2008}, language = {en} } @inproceedings{BorndoerferGroetschelPfetsch2008, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and Pfetsch, Marc}, title = {Models for Line Planning in Public Transport}, volume = {600}, booktitle = {Computer-aided Systems in Public Transport (CASPT 2004)}, editor = {Hickman, Mark and Mirchandani, Pitu and Voß, Stefan}, publisher = {Springer-Verlag}, doi = {10.1007/978-3-540-73312-6_18}, pages = {363 -- 378}, year = {2008}, language = {en} } @misc{Groetschel1973, type = {Master Thesis}, author = {Gr{\"o}tschel, Martin}, title = {Der Satz von Frobenius f{\"u}r konvergente Potenzreihen}, year = {1973}, language = {en} } @article{GroetschelPadberg1975, author = {Gr{\"o}tschel, Martin and Padberg, Manfred}, title = {Partial linear characterizations of the asymmetric travelling salesman polytope}, volume = {8}, journal = {Mathematical Programming}, pages = {378 -- 381}, year = {1975}, language = {en} } @inproceedings{Groetschel1976, author = {Gr{\"o}tschel, Martin}, title = {{\"U}ber Graphen mit Kreisen, die gegebene Wege enthalten}, volume = {5}, booktitle = {Proceedings in Operations Research}, editor = {Kohlas, J{\"u}rg and Seifert, Olaf and Zimmermann, H.}, publisher = {Physica-Verlag}, address = {W{\"u}rzburg}, pages = {119 -- 121}, year = {1976}, language = {en} } @incollection{Groetschel1977, author = {Gr{\"o}tschel, Martin}, title = {Graphs with cycles containing given paths}, volume = {1}, booktitle = {Studies in Integer Programming}, editor = {Hammer, Peter and Johnson, Ellis and Korte, Bernhard and Nemhauser, George}, publisher = {North-Holland}, pages = {233 -- 245}, year = {1977}, language = {en} } @book{Groetschel1977, author = {Gr{\"o}tschel, Martin}, title = {Polyedrische Charakterisierungen kombinatorischer Optimierungsprobleme}, volume = {36}, journal = {Mathematical Systems in Economics}, publisher = {Verlag Anton Hain}, address = {Meisenheim am Glan}, isbn = {3-445-01537-6}, year = {1977}, language = {en} } @inproceedings{Groetschel1977, author = {Gr{\"o}tschel, Martin}, title = {The monotone 2-matching polytope on a complete graph}, booktitle = {Operations Research Verfahren XXIV, Symposium in Mannheim}, pages = {72 -- 84}, year = {1977}, language = {en} } @inproceedings{Groetschel1977, author = {Gr{\"o}tschel, Martin}, title = {Facetten von Matroid-Polytopen}, booktitle = {Operations Research Verfahren XXV, Symposium Heidelberg 1976}, pages = {306 -- 313}, year = {1977}, language = {en} } @incollection{GroetschelKorte1977, author = {Gr{\"o}tschel, Martin and Korte, Bernhard}, title = {Bemerkungen zur Optimierung {\"o}konomischer Modelle}, booktitle = {Quantitative Wirtschaftsforschung, Willhelm Krelle zum 60. Geburtstag}, editor = {Albach, Horst and Helmst{\"a}dter, Ernst and Henn, Rudolf}, publisher = {J. C. B. Mohr}, address = {T{\"u}bingen}, pages = {457 -- 467}, year = {1977}, language = {en} } @article{GroetschelPadberg1977, author = {Gr{\"o}tschel, Martin and Padberg, Manfred}, title = {Lineare Charakterisierungen von Travelling Salesman Problemen}, volume = {21}, journal = {Zeitschrift f{\"u}r Operations Research, Series A}, number = {1}, publisher = {Physica-Verlag}, pages = {33 -- 64}, year = {1977}, language = {en} } @article{Groetschel1978, author = {Gr{\"o}tschel, Martin}, title = {Hypo-Hamiltonian Facets of the Symmetric Travelling Salesman Polytope}, volume = {58}, journal = {Zeitschrift f{\"u}r Angewandte Mathematik und Mechanik}, pages = {T469 -- T471}, year = {1978}, language = {en} } @inproceedings{GroetschelPadberg1978, author = {Gr{\"o}tschel, Martin and Padberg, Manfred}, title = {On the symmetric travelling salesman problem}, volume = {157}, booktitle = {Optimization and operations research, Proc. Workshop, Bonn 1977}, editor = {Henn, Rudolf and Korte, Bernhard and Oettli, W.}, publisher = {Springer}, pages = {105 -- 115}, year = {1978}, language = {en} } @article{GroetschelvonRandow1978, author = {Gr{\"o}tschel, Martin and von Randow, Rabe}, title = {A property of continuous unbounded algorithms}, volume = {14}, journal = {Mathematical Programming}, pages = {373 -- 377}, year = {1978}, language = {en} } @article{Groetschel1979, author = {Gr{\"o}tschel, Martin}, title = {On minimal strong blocks}, volume = {3}, journal = {Journal of Graph Theory}, pages = {213 -- 219}, year = {1979}, language = {en} } @inproceedings{Groetschel1979, author = {Gr{\"o}tschel, Martin}, title = {Strong blocks and the optimum branching problem}, volume = {46}, booktitle = {Numerische Methoden bei graphentheoretischen und kombinatorischen Problemen, Bd. 2, Tagung in Oberwolfach 1978}, editor = {Collatz, Lothar and Meinardus, G. and Wetterling (Hrsg.), W.}, publisher = {Birkh{\"a}user}, address = {Basel}, pages = {112 -- 121}, year = {1979}, language = {en} } @article{GroetschelHarary1979, author = {Gr{\"o}tschel, Martin and Harary, Frank}, title = {The Graphs for which All Strong Orientations Are Hamiltonian}, volume = {3}, journal = {Journal of Graph Theory}, pages = {221 -- 223}, year = {1979}, language = {en} } @article{GroetschelPadberg1979, author = {Gr{\"o}tschel, Martin and Padberg, Manfred}, title = {On the symmetric travelling salesman problem I}, volume = {16}, journal = {Mathematical Programming}, pages = {265 -- 280}, year = {1979}, language = {en} } @article{GroetschelPadberg1979, author = {Gr{\"o}tschel, Martin and Padberg, Manfred}, title = {On the symmetric travelling salesman problem II}, volume = {16}, journal = {Mathematical Programming}, pages = {281 -- 302}, year = {1979}, language = {en} } @article{Groetschel1980, author = {Gr{\"o}tschel, Martin}, title = {On the symmetric travelling salesman problem}, volume = {12}, journal = {Mathematical Programming Study}, publisher = {North-Holland}, pages = {61 -- 77}, year = {1980}, language = {en} } @article{Groetschel1980, author = {Gr{\"o}tschel, Martin}, title = {On the monotone symmetric travelling salesman problem}, volume = {5}, journal = {Mathematics of Operations Research}, number = {2}, pages = {285 -- 292}, year = {1980}, language = {en} } @incollection{GroetschelWakabayashi1990, author = {Gr{\"o}tschel, Martin and Wakabayashi, Yoshiko}, title = {Composition of facets of the clique partitioning polytope}, booktitle = {Topics in combinatorics and graph theory. Essays in honour of Gerhard Ringel}, editor = {Bodendiek, Rainer and Henn, Rudolf}, publisher = {Physica-Verlag}, address = {Heidelberg}, pages = {271 -- 284}, year = {1990}, language = {en} } @inproceedings{GroetschelJuengerReinelt1987, author = {Gr{\"o}tschel, Martin and J{\"u}nger, Michael and Reinelt, Gerhard}, title = {Calculating Exact Ground States of Spin Glasses}, booktitle = {Proceedings of the Heidelberg Colloquium on "Glassy Dynamics", Lecture Notes in Physics 275}, editor = {van Hemmen, J. and Morgenstern, I.}, publisher = {Springer}, pages = {325 -- 353}, year = {1987}, language = {en} } @article{BarahonaGroetschelJuengeretal.1988, author = {Barahona, Francisco and Gr{\"o}tschel, Martin and J{\"u}nger, Michael and Reinelt, Gerhard}, title = {An application of combinatorial optimization to statistical physics and circuit layout design}, volume = {36}, journal = {Operations Research}, number = {3}, pages = {493 -- 513}, year = {1988}, language = {en} } @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} }