<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>304</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1997-07-11</completedDate>
    <publishedDate>1997-07-11</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Frequency Assignment in Cellular Phone Networks</title>
    <abstract language="eng">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.</abstract>
    <identifier type="serial">SC-97-35</identifier>
    <identifier type="opus3-id">305</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-3044</identifier>
    <identifier type="doi">10.1023/A:1018908907763</identifier>
    <enrichment key="SourceTitle">Appeared in: Annals of OR 76 (1998), 73-93</enrichment>
    <author>Ralf Borndörfer</author>
    <author>Andreas Eisenblätter</author>
    <author>Martin Grötschel</author>
    <author>Alexander Martin</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-97-35</number>
    </series>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="groetschel">Grötschel, Martin</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/304/SC-97-35.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/304/SC-97-35.pdf</file>
  </doc>
  <doc>
    <id>562</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1998-04-03</completedDate>
    <publishedDate>1998-04-03</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The Orientation Model for Frequency Assignment Problems</title>
    <abstract language="eng">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.</abstract>
    <identifier type="serial">TR-98-01</identifier>
    <identifier type="opus3-id">563</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-5627</identifier>
    <author>Ralf Borndörfer</author>
    <author>Andreas Eisenblätter</author>
    <author>Martin Grötschel</author>
    <author>Alexander Martin</author>
    <series>
      <title>ZIB-Report</title>
      <number>TR-98-01</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Minimum-Cost Flow Problems</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Cellular Radio Telephone Systems</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Frequency Assignment Problem</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Integer Programming</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="90B10">Network models, deterministic</collection>
    <collection role="msc" number="90B80">Discrete location and assignment [See also 90C10]</collection>
    <collection role="msc" number="90C10">Integer programming</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="groetschel">Grötschel, Martin</collection>
    <collection role="projects" number="eplus-FAP">eplus-FAP</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/562/TR-98-01.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/562/TR-98-01.pdf</file>
  </doc>
  <doc>
    <id>615</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2000-12-12</completedDate>
    <publishedDate>2000-12-12</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Frequency Planning and Ramifications of Coloring</title>
    <abstract language="eng">This paper surveys frequency assignment problems coming up in planning wireless communication services. It particularly focuses on cellular mobile phone systems such as GSM, a technology that revolutionizes communication. Traditional vertex coloring provides a conceptual framework for the mathematical modeling of many frequency planning problems. This basic form, however, needs various extensions to cover technical and organizational side constraints. Among these ramifications are $T$-coloring and list coloring. To model all the subtleties, the techniques of integer programming have proven to be very useful. The ability to produce good frequency plans in practice is essential for the quality of mobile phone networks. The present algorithmic solution methods employ variants of some of the traditional coloring heuristics as well as more sophisticated machinery from mathematical programming. This paper will also address this issue. Finally, this paper discusses several practical frequency assignment problems in detail, states the associated mathematical models, and also points to public electronic libraries of frequency assignment problems from practice. The associated graphs have up to several thousand nodes and range from rather sparse to almost complete.</abstract>
    <identifier type="serial">00-47</identifier>
    <identifier type="opus3-id">616</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-6152</identifier>
    <enrichment key="SourceTitle">Appeared in: Discussiones Mathematicae, Graph Theory 22 (2002) 51-88</enrichment>
    <author>Andreas Eisenblätter</author>
    <author>Martin Grötschel</author>
    <author>Arie M.C.A. Koster</author>
    <series>
      <title>ZIB-Report</title>
      <number>00-47</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>frequency assignment</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>graph coloring</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="05-02">Research exposition (monographs, survey articles)</collection>
    <collection role="msc" number="05C15">Coloring of graphs and hypergraphs</collection>
    <collection role="msc" number="05C90">Applications [See also 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15]</collection>
    <collection role="msc" number="90-02">Research exposition (monographs, survey articles)</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="persons" number="groetschel">Grötschel, Martin</collection>
    <collection role="projects" number="eplus-FAP">eplus-FAP</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/615/ZR-00-47.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/615/ZR-00-47.pdf</file>
  </doc>
  <doc>
    <id>676</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>deu</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2002-02-15</completedDate>
    <publishedDate>2002-02-15</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="deu">Frequenzplanung im Mobilfunk</title>
    <abstract language="deu">Telekommunikation ist seit Jahren \glqq in\grqq. Zunächst gab es einen enormen Aufschwung; neue Technologien und Dienste haben eine überwältigende, nicht vorhersehbare Akzeptanz gefunden. Derzeit ist -- ausgelöst durch die UMTS-Lizenzversteigerungen, Rezessions- und Sättigungstendenzen -- eine Krise zu verzeichnen. Viele (auch wir) sind davon überzeugt, dass technischer Fortschritt und nützliche Dienste demnächst die Stimmung wieder ändern werden. Wenigen ist allerdings bewusst, welche Rolle Mathematik bei der Entwicklung und dem effizienten Einsatz vieler der neuen Kommunikationstechnologien spielt. In diesem Artikel soll kein Überblick über diesen umfangreichen Themenkreis gegeben werden. Wir zeigen lediglich an einem konkreten Beispiel aus dem Mobilfunk, der Frequenzplanung in GSM-Funknetzen, was man durch geeignete Modellierung der praktischen Fragestellung und den Einsatz problemadäquater Algorithmen erreichen kann.</abstract>
    <identifier type="serial">02-09</identifier>
    <identifier type="opus3-id">677</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-6762</identifier>
    <enrichment key="SourceTitle">Erschienen in: DMV-Mitteilungen 1 (2002) S. 18-25</enrichment>
    <author>Andreas Eisenblätter</author>
    <author>Martin Grötschel</author>
    <author>Arie M.C.A. Koster</author>
    <series>
      <title>ZIB-Report</title>
      <number>02-09</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Telekommunikation</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Frequenzplanung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Mobilfunk</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>GSM-Funknetze</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="05-02">Research exposition (monographs, survey articles)</collection>
    <collection role="msc" number="90-02">Research exposition (monographs, survey articles)</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="persons" number="groetschel">Grötschel, Martin</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/676/ZR-02-09.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/676/ZR-02-09.pdf</file>
  </doc>
  <doc>
    <id>3185</id>
    <completedYear>2008</completedYear>
    <publishedYear>2008</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>40</pageFirst>
    <pageLast>46</pageLast>
    <pageNumber/>
    <edition/>
    <issue>6</issue>
    <volume>35</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Planning UMTS Radio Networks</title>
    <parentTitle language="eng">OR/MS Today</parentTitle>
    <identifier type="url">http://www.lionhrtpub.com/orms/orms-12-08/frradio.html</identifier>
    <author>Andreas Eisenblätter</author>
    <author>Hans-Florian Geerdes</author>
    <author>Martin Grötschel</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="groetschel">Grötschel, Martin</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>3118</id>
    <completedYear>1998</completedYear>
    <publishedYear>1998</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>73</pageFirst>
    <pageLast>93</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>76</volume>
    <type>article</type>
    <publisherName>J. C. Baltzer AG, Science Publishers</publisherName>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Frequency assignment in cellular phone networks</title>
    <parentTitle language="eng">Annals of Operations Research</parentTitle>
    <identifier type="doi">10.1023/A:1018908907763</identifier>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-3044</enrichment>
    <author>Ralf Borndörfer</author>
    <author>Andreas Eisenblätter</author>
    <author>Martin Grötschel</author>
    <author>Alexander Martin</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="groetschel">Grötschel, Martin</collection>
    <collection role="projects" number="eplus-FAP">eplus-FAP</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>3152</id>
    <completedYear>2002</completedYear>
    <publishedYear>2002</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>51</pageFirst>
    <pageLast>88</pageLast>
    <pageNumber/>
    <edition/>
    <issue>22</issue>
    <volume/>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Frequency Planning and Ramifications of Coloring</title>
    <parentTitle language="eng">Discussiones Mathematicae, Graph Theory</parentTitle>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-6152</enrichment>
    <author>Andreas Eisenblätter</author>
    <author>Martin Grötschel</author>
    <author>Arie M.C.A. Koster</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="groetschel">Grötschel, Martin</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>3151</id>
    <completedYear>2002</completedYear>
    <publishedYear>2002</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>18</pageFirst>
    <pageLast>25</pageLast>
    <pageNumber/>
    <edition/>
    <issue>1</issue>
    <volume/>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Frequenzplanung im Mobilfunk</title>
    <parentTitle language="eng">DMV-Mitteilungen</parentTitle>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-6762</enrichment>
    <author>Andreas Eisenblätter</author>
    <author>Martin Grötschel</author>
    <author>Arie M.C.A. Koster</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="groetschel">Grötschel, Martin</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>2836</id>
    <completedYear>1996</completedYear>
    <publishedYear>1996</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>17</pageFirst>
    <pageLast>21</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>conferenceobject</type>
    <publisherName>Universidade de São Paulo, Instituto de Matemática e Estatística</publisherName>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Stable-Set and Other Techniques for Frequency Assignment Problems</title>
    <parentTitle language="eng">Anais da I Oficina Nacional em Problemas de Corte &amp; Empacotamento</parentTitle>
    <author>Ralf Borndörfer</author>
    <author>Andreas Eisenblätter</author>
    <author>Martin Grötschel</author>
    <author>Alexander Martin</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="groetschel">Grötschel, Martin</collection>
    <collection role="projects" number="eplus-FAP">eplus-FAP</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
</export-example>
