2011/2012


12X Michał Tuczyński
"O zliczaniu zbiorów niezależnych w grafach K_{1,3}-wolnych.

19X Adrian Bondy
"Directed Cages and the Caccetta–Haggkvist Conjecture"  abstrakt

16 XI Grzegorz Gutowski
"Kolorowanie z list on-line"

23 XI  Paweł Rzążewski
"Faktoryzacje grafów i przydział częstotliwości, czyli szybko i dobrze."

30 XI   Paweł Rzążewski
"Ogólny algorytm dokładny dla problemów przydziału częstotliwości" abstrakt

11 I Kostek Szaniawski
"Algorytmy przybliżone dla problemu kwadratury kwadratu"

18 I
9:00 Torsten Klug - Konrad Zuse Zentrum fuer Informationstechnik Berlin
"Smart Destination-Call Elevator Control Algorithms "
"Freight Train Routing"

10:15 Thomas Schlechte - Konrad Zuse Zentrum fuer Informationstechnik Berlin
"Railway Track Allocation - Simulation, Aggregation, and Optimization"

"Smart Destination-Call Elevator Control Algorithms "
Algorithmic control of elevator systems has been studied for a long time. More recently, a new paradigm for elevator control has
emerged. In destination call systems, the passenger specifies not only the direction of his ride, but the destination floor.
Destination call systems are interesting from an optimization point of view, since more information is available earlier, which
should allow improved planning. We model this as a mixed integer program and use column generation and branch and bound techniques
to solve it. In this talk we introduce our algorithmic approach, illuminate some aspects and issues of real-time planning and present some computational results on real-life data.

"Freight Train Routing"
We consider the following freight train routing problem. Given is a transportation network with fixed routes for passenger trains
and a set of freight train requests, each defined by an origin and destination station pair. The objective is to calculate a
route for each freight train such that a sum of expected delays and running times is minimal. Previous research concentrated on
microscopic train routings for junctions or major stations. Only recently approaches were developed to tackle larger corridors or
even networks. We also investigate the routing problem from a strategic perspective, calculating the routes in a macroscopic
transportation network. In this approach, complex structures are aggregated into smaller elements. Furthermore the departure and
arrival times of freight trains are approximated. We propose two mixed integer programming models for the freight train routing
problem and present computational results.

"Railway Track Allocation - Simulation, Aggregation, and Optimization"
Today the railway timetabling process and the track allocation is one of the most challenging problems to solve by a railway infrastructure provider. Especially due to the deregulation of the transport market in the recent years several suppliers of railway traffic have entered the market. This leads to an increase of slot requests and then it is natural that conflicts occur among them. Furthermore, railway infrastructure networks consist of very expensive assets, even more they are rigid due to the long-term upgrade process.

In order to make best use of these valuable infrastructure and to ensure economic operation, efficient planning of the railway operation is indispensable. Mathematical optimization models and algorithmic methodology can help to automatize and tackle these challenges. Our goal is to resolve them by producing a feasible and conflict free
timetable where a maximum of utilization is attained. From a mathematical point of view the optimization problem can be stated as a multi-commodity flow problem through an extremely large network in space and time with certain additional constraints. The problem is well known in the literature and Caprara et al. showed that it is NP-hard.

Only recently practical problem sizes are tractable due to the development of improved models and algorithms.We present a fully integrated bottom-up approach that is based on microscopic simulation data, automatic network creation and discrete optimization at the end. Our contribution is to put several pieces together, i.e., OpenTrack, netcast and TS-OPT, to release the optimization potential of the railway track allocation process. One challenging part was to establish interfaces between railway simulation software and state of the art mathematical
optimization tools.

We present computational results to different kinds of optimization scenarios. One set of instances are difficult instances of the benchmark library TTPlib. Furthermore, we discuss solutions produced by TS-OPT for instances based on an auctioning simulation for a German sub-network. Finally, we present results to prominent experiments for real world data of the Simplon corridor that highlight the fully integrated approach and demonstrates the benefit of applying optimization techniques to railway planning problems in practice.

25I Grzegorz Matecki.
"O pewnej hipotezie uogólniającej twierdzenie Dilwortha''.

Semiantyłańcuchem w produkcie PxQ nazywamy podzbiór, którego dowolne
dwa elementy są nieporównywalne w PxQ lub różnią się na obu
współrzędnych. Uniłańcuchem w produkcie PxQ nazywamy rodzinę
elementów, która jest stała na jednej współrzędnej oraz jest łańcuchem
na drugiej. Saks i West postawili hipotezę, zwaną hipotezą o
semiantyłańcuchach, że każdy produkt PxQ ma pokrycie uniłańcuchami w
liczbie równej maksymalnej wielkości semiantyłańcucha w PxQ.
Szczególnym przypadkiem tej hipotezy jest twierdzenie
Greene’ego-Kleitmana o nasyconych dekompozycjach łańcuchowych.

Niedawno Bosek, Felsner, Knauer i Matecki znaleźli kilka nowych klas
zbiorów częściowo uporządkowanych dla których hipoteza jest prawdziwa.
Ponadto autorzy pokazali kontrprzykład dla ogólnym przypadku. To w
końcu dało odpowiedź na pytanie postawione 30 lat temu przez Saksa i
Westa.

29 II Przemysław Gordinowicz
"O automorfizmach grafu zaburzenie domkniętego"

14 III Paweł Naroski
"Złożoność problemów dwukolorowania hipergrafów klikowych"

21 III Sławomir Kwasiborski
"Algorytm znajdowania silnych mostów i silnych punktów rozcinających w grafach skierowanych".

28 III Bartłomiej Bosek
"Powrót do szkoły - kolorowanki, ułamki i tabliczka mnożenia"

11 IV Paweł Rzążewski, Konstanty Szaniawski
"Maksymalna liczba zbiorów 2-niezależnych w grafach regularnych"

18 IV Krzysztof Węsek
"b-Ograniczona cyrkularna liczba chromatyczna"

prof. Adrian Bondy, Université Paris 6,
"Beautiful Conjectures in Graph Theory I", wtorek 24.04.2012, godz. 14.30 sala 107 GMINI
"Beautiful Conjectures in Graph Theory II", środa 25.04.2012, godz. 10.15, sala 101 GMINI.

Abstract:
The mathematician’s patterns, like the painter’s or the poet’s must
be beautiful; the ideas, like the colors or the words, must fittogether
in a harmonious way. Beauty is the first test: there is no permanent
place in this world for ugly mathematics.(G.H. Hardy)
We propose six criteria of the beauty of a mathematical conjecture,
and present a selection of conjectures in graph theory whichrespond
to some or all of these criteria.

9 V Sławomir Kwasiborski
"Problem uszeregowania pociągów a cykle eulera"

16 V Przemysław Wenus
"Hipoteza Rao o ciągach stopni w grafie"

23 V  Paweł Petecki (AGH)
"Dekompozycje hipergrafów jednorodnych na cykle Hamiltona"

6 VI Sebastian Czerwiński (UZ) 
"Kolorowanie losowych grafów Cayleya"

13 VI Jakub Kierzkowski
"Spektrum sąsiedztwa grafu - ścieżki i cykle".
Powered by CMSimple