### Project 07: "Structural investigations on combinatorial optimisation problems"

*This project is running since 2010.*

Principal investigator: Bettina Klinz

Graz University of Technology, Austria.

*Mentor for*: Paul, Weinberger; de Parada; Cuno, Schmuck.

Associated scientist: Rainer Burkard

Graz University of Technology, Austria.

*Mentor for*: Lendl; Ćustić, Ebner.

### DK Students

**Third phase of the doctoral program:****Lasse Wulf**(Germany; since November 2019)

*Email*: wulf@math.tugraz.at

*Mentors*: Michael Kerber, Eranda Dragoti-Cela, Stefan Lendl.

**Second phase of the doctoral program:****Stefan Lendl**(Austria; October 2015–August 2019)

*Email*: lendl@math.tugraz.at

*Mentors*: Oswin Aichholzer, Rainer Burkard, Eranda Dragoti-Cela.

*Thesis Title*: "Efficiently solvable cases of hard combinatorial optimization problems".

*PhD Defense*: August 19, 2019.

*Referees*: B. Klinz, F. C.R. Spieksma (Eindhoven), F. Rendl (Klagenfurt).

*Examiners*: B. Klinz, F. Rendl (Klagenfurt).**First phase of the doctoral program:**-
**Ante Ćustić**(Croatia; October 2010–September 2014)

Personal homepage;*Email*: custic@math.tugraz.at

*Mentors*: Rainer Burkard, Wolfgang Woess.

*PhD Defense*: September 24, 2014.

*Referees*: B. Klinz, R. Euler (Brest), F. Rendl (Klagenfurt).

*Examiners*: B. Klinz, F. Rendl (Klagenfurt).

### Project description

The research work of Bettina Klinz takes place in the common overlap of mathematics, theoretical computer science and operations research. Her research interests are centred around combinatorial optimization and the theory of algorithms. The main objective of the research is the design of efficient exact and approximate algorithms for combinatorial optimization problems. A key research topic is to investigate how special structures posed on the input data of a combinatorial optimization problem can be exploited to arrive at more efficient solution approaches. This question is closely related to the investigation of the borderline between between efficiently solvable problems and NP-hard problems. Additional conditions that might turn hard into easy problems include special cost structures such as circulant matrices, Toeplitz matrices and Monge matrices as well as special graph classes such as trees, planar graphs and series-parallel graphs. In recent years special attention has been paid to the treatment of various hard assignment and transportation problems (multidimensional, nonlinear, bilevel, parametric etc). This area still offers a large number of challenging open problems.