Monday, December 8, 2014
Humboldt-Universität zu Berlin
Institut für Informatik
Rudower Chaussee 25
12489 Berlin
room: Humboldt-Kabinett (1. Etage)
Lecture - 14:15
Abstract:
Two graphs are Hanf-equivalent with respect to radius r if there is a bijection between their vertex sets which preserves the isomorphism types of the vertices' neighbourhoods of radius r. For r = 1 this implies that the graphs have the same degree sequence. A classical result in Finite Model Theory is Hanf's Theorem, stating that for every
quantifier rank r there is a radius R such that any two graphs which are Hanf-equivalent with respect to radius R satisfy the same first-order sentences of quantifier rank r. This result has found numerous applications, for instance in showing that certain properties are not first-order definable, or in evaluation algorithms for first-order logic.
In this talk I want to give an introduction to the concept of Hanf-equivalence, and I will show a connection between Hanf-equivalence and the number of occurrences of induced subgraphs of a certain order.
Colloquium - 16:00
Abstract:
In the design and planning of telecommunication networks, in particular access and distribution networks, a set of clients with demands and a set of potential facility locations are given. Furthermore, a set of access cables with decreasing cost per capacity ratio is given. The task of a network planner is to open facilities and serve all client demands via a routing network built using the access cables. The demand at a client node will be routed from an open facility to the client along a path of the built routing network. The set of access cables installed on an edge of the routing network should be of sufficient capacity to support all demands routed along that edge. The objective is to minimize the total cost of opening facilities and installing access
cables. This can be modeled as a multiple-sink buy-at-bulk network design with facility location problem.
In this talk, we present an exact solution method for this problem, which so far had been only addressed from the perspective of designing approximation algorithms. We provide compact and path-based formulations for the problem and we design an exact branch-cut-and-price algorithm for solving the path based formulation.. We introduce two classes of valid inequalities to improve the lower bounds. In addition to this, we present three different types of primal heuristics and employed a hybrid approach to effectively make use of these heuristics in order to improve the primal bounds.
Finally, we evaluate the algorithm on a set of real world instances.
Joint work with Ashwin Arulselvan and Wolfgang A. Welz.