@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} } @misc{KosterZymolka, author = {Koster, Arie M.C.A. and Zymolka, Adrian}, title = {Provably Good Solutions for Wavelength Assignment in Optical Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8155}, number = {04-40}, abstract = {In this paper, we study the minimum converter wavelength assignment problem in optical networks. To benchmark the quality of solutions obtained by heuristics, we derive an integer programming formula tion by generalizing the formulation of Mehrotra and Trick (1996) for the vertex coloring problem. To handle the exponential number of variables, we propose a column generation approach. Computational experiments show that the value of the linear relaxation states a good lower bound and can often prove optimality of the best solution generated heuristically.}, language = {en} } @misc{KosterZymolka, author = {Koster, Arie M.C.A. and Zymolka, Adrian}, title = {Linear Programming Lower Bounds for Minimum Converter Wavelength Assignment in Optical Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8160}, number = {04-41}, abstract = {In this paper, we study the conflict-free assignment of wavelengths to lightpaths in an optical network with the opportunity to place wavelength converters. To benchmark heuristics for the problem, we develop integer programming formulations and study their properties. Moreover, we study the computational performance of the column generation algorithm for solving the linear relaxation of the most promising formulation. In many cases, a non-zero lower bound on the number of required converters is generated this way. For several instances, we in fact prove optimality since the lower bound equals the best known solution value.}, language = {en} }