Workshop on

Tractable special cases of hard combinatorial optimization problems


Graz, Austria, Dec. 15.-16.2014

The workshop will be hosted at the Department of Optimization and Discrete Mathematics
of the University of Technology in Graz.

The workshop is partially sponsored by ÖGOR - The Austrian Operations Research Society.

The workshop is a two-day, single stream event focussing at polynomially solvable or approximable special cases of provably hard combinatorial optimization problems. This line of research deals with NP-hard combinatorial optimization problems which become polynomially tractable if specific structural propertiesare imposed on their input. The identification of the sometimes thin boarderline between hard and tractable cases is often a hard and interesting challenge.

The workshop hosts invited talks as well as contributed talks and discussions or working sessions.

Invited talks

Vladimir Deineko, Warwick Business School, UK

Special structures in polynomially solvable cases: Is there much in common? Abstract (pdf)

Martin Milanič, University of Primorska, Slovenia

Vector connectivity in graphs Abstract (pdf)

Frits Spieksma, KU Leuven, Belgium

Multi-index assignment problems: an overview Abstract (pdf)

Gerhard Woeginger, Eindhoven Unioversity of Technology, The Netherlands

Tractable special cases through linear algebra Abstract (pdf)


Program (pdf-file)

Workshop folder including program and abstracts (pdf-file)

Monday, December 15, 2014

Tuesday, December 16, 2014

The workshop venue:

The workshop takes place in seminar room C208 which is located in the 2-nd floor of the building of the Department of Optimization and Discrete Mathematics, Graz University of Technology, Steyrergasse 30, 8010 Graz, Austria.

Information on how to reach the Steyrergasse 30 building can be found here. There will be signposts that will help you to find your way from the entrance of the building to the conference room.

Participation fee:

There will be a participation fee of 30 Euro payable on site (in cash). This will cover the lunches on December 15 and 16 and the refreshments during the workshop breaks.
The participants are responsable for their own travel and accomodation expenses.

Important Dates:




Eranda Çela and Bettina Klinz, Graz University of Technology, Austria

Please do not hesitate to contact scco14[at] for any additional information.

Last Update: December 2014