Lectures and Colloquia during the semester

Technische Universität Berlin

Straße des 17. Juni 136, 10623 Berlin

Mathematikgebäude - Raum MA 042

*Abstract:*
The location of facilities in order to provide service for customers
is a well-studied problem in the operations research literature. In
the basic model, there is a predefined cost for opening a facility
and also for connecting a customer to a facility, the goal being to
minimize the total cost.

Often, both in the case of public facilities (such as libraries, municipal swimming pools, fire stations, ...) and private facilities (such as distribution centers, switching stations, ...), we may want to find a "fair" allocation of the total cost to the customers - this is known as the cost allocation problem. A central question in cooperative game theory is whether the total cost can be allocated to the customers such that no coalition of customers has any incentive to build their own facility or to ask a competitor to service them.

There are strong connections between fair cost allocations and linear programming relaxations for several natural variants of the facility location problem. In particular, a fair cost allocation exists if and only if there is no integrality gap for a corresponding linear programming relaxation. We discuss a subtle variant of randomized rounding which turns a (fractional) solution to the linear programming relaxation into a feasible solution to the facility location problem. This leads to new and elegant proofs for the existence of fair cost allocations for several classes of instances.

** Colloquium - 16 Uhr s.t.**

*Abstract:*
It is well known that there exist graphs which have arbitrarily
high average degree and arbitrarily high girth
(where the girth of a graph is defined to be the length of its shortest
cycle).
In other words, such graphs are globally dense and locally sparse.
In 1983, Thomassen conjectured that such graphs are in fact contained
in any graph of sufficiently high average degree:

**Conjecture** (Thomassen) *For all integers* k,g *there
exists an integer* f(k,g) *such that every graph of average degree at
least* f(k,g) *contains a subgraph of average degree at least* k *and girth at
least* g.

The conjecture is trivially true for g=4. Recently, Daniela Kühn and I proved the case when g <= 6, i.e. we obtain dense subgraphs whose girth is at least six. In my talk, I would like to discuss the conjecture and describe our proof of the g <= 6 case.

[top]