@misc{Groetschel, author = {Gr{\"o}tschel, Martin}, title = {My Favorite Theorem: Characterizations of Perfect Graphs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4053}, number = {SC-99-17}, abstract = {This paper summarizes and discusses various characterizations of perfect graphs and mentions some open problems in this area.}, language = {en} } @misc{Groetschel, author = {Gr{\"o}tschel, Martin}, title = {Frequency Assignment in Mobile Phone Systems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6265}, number = {00-58}, abstract = {Wireless communication networks employ radio frequencies to establish communication links. The available radio spectrum is very limited. To meet today's radio communication demand, this resource has to be administered and reused carefully in order to control mutual interference. The reuse can be organized via separation in space, time, or frequency, for example. The problem, therefore, arises to distribute frequencies to links in a ``reasonable manner''. This is the basic form of the frequency assignment problem. What ``reasonable'' means, how to quantify this measure of quality, which technical side constraints to consider cannot be answered in general. The exact specification of this task and its mathematical model depend heavily on the particular application considered. In this paper we discuss this issue with respect to the GSM standard for mobile communication.}, language = {en} } @misc{GroetschelNemhauser, 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}, 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} } @misc{BorndoerferGroetschelJaeger, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and Jaeger, Ulrich}, title = {Planning Problems in Public Transit}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11252}, number = {09-13}, abstract = {Every day, millions of people are transported by buses, trains, and airplanes in Germany. Public transit (PT) is of major importance for the quality of life of individuals as well as the productivity of entire regions. Quality and efficiency of PT systems depend on the political framework (state-run, market oriented) and the suitability of the infrastructure (railway tracks, airport locations), the existing level of service (timetable, flight schedule), the use of adequate technologies (information, control, and booking systems), and the best possible deployment of equipment and resources (energy, vehicles, crews). The decision, planning, and optimization problems arising in this context are often gigantic and "scream" for mathematical support because of their complexity. This article sketches the state and the relevance of mathematics in planning and operating public transit, describes today's challenges, and suggests a number of innovative actions. The current contribution of mathematics to public transit is — depending on the transportation mode — of varying depth. Air traffic is already well supported by mathematics. Bus traffic made significant advances in recent years, while rail traffic still bears significant opportunities for improvements. In all areas of public transit, the existing potentials are far from being exhausted. For some PT problems, such as vehicle and crew scheduling in bus and air traffic, excellent mathematical tools are not only available, but used in many places. In other areas, such as rolling stock rostering in rail traffic, the performance of the existing mathematical algorithms is not yet sufficient. Some topics are essentially untouched from a mathematical point of view; e.g., there are (except for air traffic) no network design or fare planning models of practical relevance. PT infrastructure construction is essentially devoid of mathematics, even though enormous capital investments are made in this area. These problems lead to questions that can only be tackled by engineers, economists, politicians, and mathematicians in a joint effort. Among other things, the authors propose to investigate two specific topics, which can be addressed at short notice, are of fundamental importance not only for the area of traffic planning, should lead to a significant improvement in the collaboration of all involved parties, and, if successful, will be of real value for companies and customers: • discrete optimal control: real-time re-planning of traffic systems in case of disruptions, • model integration: service design in bus and rail traffic. Work on these topics in interdisciplinary research projects could be funded by the German ministry of research and education (BMBF), the German ministry of economics (BMWi), or the German science foundation (DFG).}, language = {en} }