|05.06.2008 ||New Dr!|
|On June 5th 2008, Benjamin Leroy-Beaulieu has defended his PhD thesis successfully. We all congratulate him!|
|Today, Dr. Benjamin Lévêque has joined our crew for a six month Post Doc. We are looking forward for this successful collaboration.|
|Speaker||Dr. Yury Orlovich, United Institute of Informatics Problems (Belarus)|
|Title||On independent dominating and maximal dissociation sets in graphs|
|When||Tuesday the 18th of december 2007, 2:15 PM|
|Where||Room MA 12|
|Abstract||We consider the complexity and approximability results for the Independent Dominating Set and Independent Neighborhood Set problems within some co-hereditary classes of graphs. We also show that the problem of finding a dissociation set of maximum size in a graph is NP-hard for line graphs, and the problem of finding a maximal dissociation set of minimum size is NP-hard for general graphs. Moreover, some polynomially solvable cases for both problems are derived.|
|Speaker||Prof. Valery Gordon, United Institute of Informatics Problems (Belarus)|
|Title||Cyclic properties of triangular grid graphs and locally connected graphs|
|When||Tuesday, the 11th of December 2007 at 2:15 PM|
|Where||Room MA 12|
|Abstract||It is known that all 2-connected, linearly convex triangular grid graphs, with the only one exception, are Hamiltonian (Reay and Zamfirescu, 2000). We show that this result holds for a wider class of connected, locally connected triangular grid graphs and, with more exceptions, even for some general class of graphs. Fully cycle extendibility of connected, locally connected graphs with bounded vertex degree is also considered.|
|Speaker||Prof. Bezalel Gavish, Southern Methodist University, Dallas, Texas (USA)|
|Title||Tree Based Combinatorial Optimization Problems in Local Telecommunication Networks|
|When||Tuesday, 29th of November 2007 at 2:15 PM.|
|Summary||Modern Computer Communication Networks are having a profound impact on individuals and society, the demand for higher capacity and faster networking services to the home are increasing significantly over time. This is known as the last mile problem, how to bring broadband communication services to the home at reasonable costs. Several technologies and/or their combinations have been developed to provide such services to the end user: They include Fiberoptics based systems, cable modems and wideband services through the cable TV infrastructure, wireless services through the cellular and wireless based systems and DSL/ADSL and its different variants that is based on extensions of the existing wire based phone system.|
The different technologies and the analysis of their advantages and disadvantages will be presented. Most of the technologies rely on the existing local TV cable or phone network to provide services to the home. In order to deploy the technologies efficiently in the local service system efficient algorithms have to be developed to solve existing and new combinatorial optimization problems on tree based networks. We will present several of those problems and highlight results obtained to some of them. Open problems and extensions will be discussed
|Speaker||Prof. Wieslaw Kubiak Memorial University, St.John's (Canada)|
|Title||Webster's sequence for cyclic processes sharing a common resource|
|When||Tuesday, 12th of June, 2007 at 14h00|
|Where||Room MA 12|
|Summary||We consider cyclic processes sharing a common resource. The resource can be used by at most one process at a time. We show that Webster's sequences of apportionment are the most regular words for two cyclic processes, thus they maximize utilization of the resource independently of processing times of the processes. This result is a very rare example where the fair resource allocation ensures its best utilization as well. We also show when Webster's sequences are most regular words for more than two processes by proving a symmetric case of the Fraenkel's conjecture about exact covering of integers by Beatty sequences.|
|Speaker||Prof. Rainer Burkard|
|Title||Inverse Location Problems|
|When||Tuesday, 29th of May, 2007 at 11h00|
|Where||Room MA 12|
|Summary||Classical location problems ask for an optimal site from which a finite set of customers can be served as good as possible. The inverse 1-median problem consists in changing the weights of the customers of a 1-median location problem at minimum cost such that a pre-specified point becomes the 1-median. The cost for changing the weights is proportional to the increase or decrease of the corresponding weight. We show that the inverse 1-median problem in trees and in the plane (endowed with the Manhattan metric) can be solved by greedy-like algorithms. |
Moreover, we discuss the inverse 1-median problem on a cycle with unit costs for changing the weights. By methods from computational geometry it will be possible to solve this problem in O(n2)-time. Furthermore, a first algorithm for the inverse 1-median problem in the plane endowed with the Euclidean metric and unit costs will be given.
This is a joint work with M. Galavii, E. Gassner, C. Pleschiutschnig and J. Zhang.
|Speaker||Prof. Gabriele di Stefano|
|Title || Algorithms for railway optimization:
the ARRIVAL project|
|When|| Thursday, 12.04.2007, 14h|
|Where||Room MA 31|
|Summary||Algorithmic methods have reached a state of maturity as a consequence of decades of research where real-world problems were posed to the
algorithms community triggering important developments in the field.
Despite this success, the current state of algorithmic research still
faces severe difficulties, or cannot cope at all, with highly-complex
and data-intensive applications as those dealing with optimization
issues in large-scale communication and transportation networks.
ARRIVAL (Algorithms for Robust and online Railway optimization:
Improving the Validity and reliAbility of Large scale systems)
is a Specific Targeted Research Project funded by the European Commission
within the 6th Framework Programme. ARRIVAL aims to considerably advance the
current state of algorithmic research by attacking optimization questions
in perhaps the most complex and largest in scale (transportation) setting:
that of railway systems. Railway optimization deals with planning and
scheduling problems over several time horizons. ARRIVAL faces two
important aspects of planning that pose even harder optimization questions:
robust planning and online (real-time) planning.
These two, tightly coupled, facets constitute a proactive and a reactive
approach, respectively, to deal with disruptions to the normal operation.
The seminar gives an overview of some algorithmic problems arising
in the areas of timetable information updating, rolling stock scheduling,
and delay management.