@misc{BodlaenderKosterEijkhofetal., author = {Bodlaender, Hans L. and Koster, Arie M.C.A. and Eijkhof, Frank van den and Gaag, Linda C. van der}, title = {Pre-processing for Triangulation of Probabilistic Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6655}, number = {01-39}, abstract = {The currently most efficient algorithm for inference with a probabilistic network builds upon a triangulation of a network's graph. In this paper, we show that pre-processing can help in finding good triangulations for probabilistic networks, that is, triangulations with a minimal maximum clique size. We provide a set of rules for stepwise reducing a graph, without losing optimality. This reduction allows us to solve the triangulation problem on a smaller graph. From the smaller graph's triangulation, a triangulation of the original graph is obtained by reversing the reduction steps. Our experimental results show that the graphs of some well-known real-life probabilistic networks can be triangulated optimally just by preprocessing; for other networks, huge reductions in their graph's size are obtained.}, language = {en} } @misc{BodlaenderFominKosteretal., author = {Bodlaender, Hans L. and Fomin, Fedor V. and Koster, Arie M.C.A. and Kratsch, Dieter and Thilikos, Dimitrios M.}, title = {On exact algorithms for treewidth}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9265}, number = {06-32}, abstract = {We give experimental and theoretical results on the problem of computing the treewidth of a graph by exact exponential time algorithms using exponential space or using only polynomial space. We first report on an implementation of a dynamic programming algorithm for computing the treewidth of a graph with running time \$O^\ast(2^n)\$. This algorithm is based on the old dynamic programming method introduced by Held and Karp for the {\sc Tra veling Salesman} problem. We use some optimizations that do not affect the worst case running time but improve on the running time on actual instances and can be seen to be practical for small instances. However, our experiments show that the space use d by the algorithm is an important factor to what input sizes the algorithm is effective. For this purpose, we settle the problem of computing treewidth under the restriction that the space used is only polynomial. In this direction we give a simple \$O^\ast(4^n)\$ al gorithm that requires {\em polynomial} space. We also show that with a more complicated algorithm, using balanced separators, {\sc Treewidth} can be computed in \$O^\ast(2.9512^n)\$ time and polynomial space.}, language = {en} } @misc{HoeselKosterLeenseletal., author = {Hoesel, Stan P.M. van and Koster, Arie M.C.A. and Leensel, Robert L.M.J. van de and Savelsbergh, Martin W.P.}, title = {Polyhedral Results for the Edge Capacity Polytope}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5907}, number = {00-22}, abstract = {Network loading problems occur in the design of telecommunication networks, in many different settings. The polyhedral structure of this problem is important in developing solution methods for the problem. In this paper we investigate the polytope of the problem restricted to one edge of the network (the edge capacity problem). We describe classes of strong valid inequalities for the edge capacity polytope, and we derive conditions under which these constraints define facets. As the edge capacity problem is a relaxation of the network loading problem, their polytopes are intimately related. We, therefore, also give conditions under which the inequalities of the edge capacity polytope define facets of the network loading polytope. Furthermore, some structural properties are derived, such as the relation of the edge capacity polytope to the knapsack polytope. We conclude the theoretical part of this paper with some lifting theorems, where we show that this problem is polynomially solvable for most of our classes of valid inequalities. In a computational study the quality of the constraints is investigated. Here, we show that the valid inequalities of the edge capacity polytope are not only important for solving the edge capacity problem, but also for the network loading problem, showing that the edge capacity problem is an important subproblem.}, language = {en} } @misc{KosterBodlaenderHoesel, author = {Koster, Arie M.C.A. and Bodlaender, Hans L. and Hoesel, Stan P.M. van}, title = {Treewidth: Computational Experiments}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6644}, number = {01-38}, abstract = {Many {\cal NP}-hard graph problems can be solved in polynomial time for graphs with bounded treewidth. Equivalent results are known for pathwidth and branchwidth. In recent years, several studies have shown that this result is not only of theoretical interest but can successfully be applied to find (almost) optimal solutions or lower bounds for diverse optimization problems. To apply a tree decomposition approach, the treewidth of the graph has to be determined, independently of the application at hand. Although for fixed \$k\$, linear time algorithms exist to solve the decision problem ``treewidth \$\leq k\$'', their practical use is very limited. The computational tractability of treewidth has been rarely studied so far. In this paper, we compare four heuristics and two lower bounds for instances from applications such as the frequency assignment problem and the vertex coloring problem. Three of the heuristics are based on well-known algorithms to recognize triangulated graphs. The fourth heuristic recursively improves a tree decomposition by the computation of minimal separating vertex sets in subgraphs. Lower bounds can be computed from maximal cliques and the minimum degree of induced subgraphs. A computational analysis shows that the treewidth of several graphs can be identified by these methods. For other graphs, however, more sophisticated techniques are necessary.}, language = {en} } @misc{AardalHoeselKosteretal., author = {Aardal, Karen I. and Hoesel, Stan P.M. van and Koster, Arie M.C.A. and Mannino, Carlo and Sassano, Antonio}, title = {Models and Solution Techniques for Frequency Assignment Problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6667}, number = {01-40}, abstract = {{\begin{rawhtml} Revised Version unter http://dx.doi.org/10.1007/s10479-007-0178-0 \end{rawhtml}} Wireless communication is used in many different situations such as mobile telephony, radio and TV broadcasting, satellite communication, and military operations. In each of these situations a frequency assignment problem arises with application specific characteristics. Researchers have developed different modelling ideas for each of the features of the problem, such as the handling of interference among radio signals, the availability of frequencies, and the optimization criterion. This survey gives an overview of the models and methods that the literature provides on the topic. We present a broad description of the practical settings in which frequency assignment is applied. We also present a classification of the different models and formulations described in the literature, such that the common features of the models are emphasized. The solution methods are divided in two parts. Optimization and lower bounding techniques on the one hand, and heuristic search techniques on the other hand. The literature is classified according to the used methods. Again, we emphasize the common features, used in the different papers. The quality of the solution methods is compared, whenever possible, on publicly available benchmark instances.}, language = {en} } @misc{EisenblaetterGroetschelKoster, author = {Eisenbl{\"a}tter, Andreas and Gr{\"o}tschel, Martin and Koster, Arie M.C.A.}, title = {Frequency Planning and Ramifications of Coloring}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6152}, number = {00-47}, abstract = {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.}, language = {en} } @misc{EisenblaetterGroetschelKoster, author = {Eisenbl{\"a}tter, Andreas and Gr{\"o}tschel, Martin and Koster, Arie M.C.A.}, title = {Frequenzplanung im Mobilfunk}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6762}, number = {02-09}, abstract = {Telekommunikation ist seit Jahren \glqq in\grqq. Zun{\"a}chst gab es einen enormen Aufschwung; neue Technologien und Dienste haben eine {\"u}berw{\"a}ltigende, nicht vorhersehbare Akzeptanz gefunden. Derzeit ist -- ausgel{\"o}st durch die UMTS-Lizenzversteigerungen, Rezessions- und S{\"a}ttigungstendenzen -- eine Krise zu verzeichnen. Viele (auch wir) sind davon {\"u}berzeugt, dass technischer Fortschritt und n{\"u}tzliche Dienste demn{\"a}chst die Stimmung wieder {\"a}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 {\"U}berblick {\"u}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{\"a}quater Algorithmen erreichen kann.}, language = {de} } @misc{ZymolkaKosterWessaely, author = {Zymolka, Adrian and Koster, Arie M.C.A. and Wess{\"a}ly, Roland}, title = {Transparent optical network design with sparse wavelength conversion}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7017}, number = {02-34}, abstract = {We consider the design of transparent optical networks from a practical perspective. Network operators aim at satisfying the communication demands at minimum cost. Such an optimization involves three interdependent planning issues: the dimensioning of the physical topology, the routing of lightpaths, and the wavelength assignment. Further topics include the reliability of the configuration and sparse wavelength conversion for efficient use of the capacities. In this paper, we investigate this extensive optical network design task. Using a flexible device-based model, we present an integer programming formulation that supports greenfield planning as well as expansion planning on top of an existing network. As solution method, we propose a suitable decomposition approach that separates the wavelength assignment from the dimensioning and routing. Our method in particular provides a lower bound on the total cost which allows to rate the solution quality. Computational experiments on realistic networks approve the solution approach to be appropriate.}, language = {en} } @misc{EisenblaetterFuegenschuhKochetal., author = {Eisenbl{\"a}tter, Andreas and F{\"u}genschuh, Armin and Koch, Thorsten and Koster, Arie M.C.A. and Martin, Alexander and Pfender, Tobias and Wegel, Oliver and Wess{\"a}ly, Roland}, title = {Modelling Feasible Network Configurations for UMTS}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6837}, number = {02-16}, abstract = {A model for the optimisation of the location and configuration of base stations in a UMTS network is described. The focus is primarily on modelling the configuration problem sufficiently accurate using mixed-integer variables and (essentially) linear constraints. These constraints reflect the limited downlink code capacity in each cell, the interference limitations for successful up- and downlink transmissions, the need for sufficiently strong (cell) pilot signals, and the potential gain for mobiles from being in soft(er) hand-over. It is also explained how to use the model as a basis for rating network configurations.}, language = {en} } @misc{Koster, author = {Koster, Arie M.C.A.}, title = {Wavelength Assignment in Multi-Fiber WDM Networks by Generalized Edge Coloring}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8478}, number = {05-13}, abstract = {In this paper, we study wavelength assignment problems in multi-fiber WDM networks. We focus on the special case that all lightpaths have at most two links. This in particular holds in case the network topology is a star. As the links incident to a specific node in a meshed topology form a star subnetwork, results for stars are also of interest for general meshed topologies. We show that wavelength assignment with at most two links per lightpath can be modeled as a generalized edge coloring problem. By this relation, we show that for a network with an even number of fibers at all links and at most two links per lightpath, all lightpaths can be assigned a wavelength without conversion. Moreover, we derive a lower bound on the number of lightpaths to be converted for networks with arbitrary numbers of fibers at the links. A comparison with linear programming lower bounds reveals that the bounds coincide for problems with at most two links per lightpath. For meshed topologies, the cumulative lower bound over all star subnetworks equals the best known solution value for all realistic wavelength assignment instances available, by this proving optimality.}, language = {en} }