Thursday, March 20th, 2014
Room: SR 15.35, RESOWI E3
Universitätsstraße 15
University of Graz
8:50-9:00 Welcome
9:00-10:00 Peter Gritzmann, TU München, Department of Mathematics
On geometric clustering and its applications
Abstract: In geometric clustering m (weighted) objects in some Rd have to be partitioned into
k clusters according to certain balancing constraints so as to optimize some objective function.
The most prominent example in our context is that of the consolidation of farmland but we will
also indicate other applications.
While the relevant speci cations of the optimization problem are NP-hard in general, we use
polyhedral approximations of corresponding clustering bodies to devise surprisingly tight approximations.
Also we show that optimal clusterings have strong separation properties. In
particular, we introduce gravity polytopes in Rkd whose vertices encode precisely the feasible
power diagrams in Rd. (Joint work with Andreas Brieden)
10:00-10:30 Coff ee break
10:30-11:30 Rico Zenklusen, ETH Zürich, Department of Mathematics
Analyzing network robustness via interdiction problems
Abstract: How susceptible is a network to failures of some of its components? What are the
weakest spots of a networked system? These questions lie at the heart of interdiction problems,
which seek to determine the maximum impact that the failure/removal of a limited number of
edges/vertices can have on the performability of a network. Interdiction problems are a natural
way to measure the robustness of a system. Furthermore, they give valuable insights in how to
best improve the failure resilience of a system, and sometimes, how to best attack it.
In this talk, I will rst give a general introduction to interdiction problems, showing some of their
varied, and sometimes surprising, applications. I will then focus on one particular interdiction
problem about graph connectivity, that captures many important aspects that are typical for
interdiction problems. More precisely, we will discuss how to maximally decrease the edgeconnectivity
of an edge-weighted graph by removing a limited set of edges. This problem allows
for nicely illustrating many interesting optimization techniques that are useful to approach a
variety of interdiction problems.
11:30-12:30 Vladimir Deineko, Warwick Business School
Modeling Operations Research applications in real life
Abstract: In our presentation we tell three stories of real life OR applications in industry, city
services and in education. The mathematical models behind the applications are of combinatorial
(discrete) nature. It is well known fact that nding optimal solutions for this type of problems
is almost impossible. Does it mean that an OR intervention in this case is bound for failure?
Is it indeed the combinatorial nature of problems that cause the troubles? To keep an intrigue,
we do not tell you in this abstract whether the applications mentioned above were successful or
not. Details are in the talk.
organized by:
Ulrich Pferschy, Department of Statistics and Operations Research
Marc Reimann, Department of Production and Operations Management
