Completed Research Grants of the Combinatorial Optimization Group
Efficiently solvable variants of location problems: (Semi-)obnoxious, inverse and budget-constrained location problems (2006-2009)
The project deals with efficiently solvable variants of location problems. The project splits up into three subareas: semi-obnoxious location problems, inverse location problems and location problems with budget constraints. In all areas our main focus lies on the development of efficient algorithms for the solution of the considered location problems. In classical location problems, each client wishes to have its closest facility as near to itself as possible. In semi-obnoxious facility location problems, we treat the case of facilities for which closeness is desirable only for some clients while other clients prefer the facilities to be as far away as possible. Inverse location problems deal with modifying a set of input parameters at minimum cost such that a given feasible solution of the underlying location problem becomes optimal. The third subarea is concerned with three classes of location problems with budget constraints. Given a limited budget and a set of input parameters of the location problem that can be changed, the goal in improvement problems is to change the parameters within the given budget in such a way so as to improve the quality of an already given solution or of a new optimal solution of the location problem under investigation as much as possible. There also exist variants where the aim is to degrade the quality instead of improving it.
- supported by Austrian Science Fund (FWF), Grant P18918-N18 (2006-2009)
- Participants in this project:
- Rainer E. Burkard: Principal Investigator
- Bettina Klinz: Co-Principial Investigator
- Elisabeth Gassner: PostDoc (2006-2009), funded by project
- Behrooz Alizadeh: PostDoc (2009), funded by project
- Johannes Hatzl: Post-Doc, funded by TU Graz
Special Research Center (SFB) Optimization and Control (1994-2004)
The Combinatorial Optimization Group took part in the Special Research Centre (SFB) "Optimization and Control", one of the very first such centers in Austria. Two research projects of the group have been part of the SFB, for details see below.
- supported by Austrian Science Fund (FWF), Grant SFB F003 (1994-2004), City of Graz, Province of Styria.
- Participants in the Subprojects F317 and F302
- Ian Beale (PostDoc)
- Rainer E. Burkard
- Helidon Dollani (PhD student)
- Eranda Dragoti-Cela
- Tibor Dudas (PhD student)
- Tiziana Fortuna (PhD student)
- Elisabeth Gassner (PhD student)
- Johannes Hatzl (PhD student)
- Clemens Heuberger
- Astrid Kenyon (PostDoc)
- Bettina Klinz
- Christophe Meyer (PostDoc)
- Ulrich Pferschy
- Carmen Pleschiutschnig (PhD student)
- Günter Rote
- Franz Rendl
- Rüdiger Rudolf
- Clemens Saurer (PhD student)
- Tenfelde-Podehl Dagmar
- Gerhard J. Woeginger
- Christian Zelle (PhD student)
Subproject F317 Efficiently solvable special cases of NP-hard combinatorial optimization problems
The main area of research within subproject F317 is the investigation of efficiently solvable special cases NP-hard problems for which no polynomial-time solution methods are known or even expected, where "efficiently solvable" in the traditional sense means solvable by a polynomial time algorithm. The class of NP-hard problems is a class of problems which are (theoretically) difficult with respect to their solution behavior and to whom the majority of combinatorial optimization problems that arise in theory and in practice belong.
The investigation of efficiently solvable-special cases of NP-hard problems is a main research direction concerning NP-hard optimization problems. A main focus of the research within subproject F317 is on the identification of new efficiently solvable special cases and the design of the corresponding algorithms for already well investigated NP-hard problems (e.g. the traveling salesman problem, the quadratic assignment problem, etc.) as well as for problems which are less investigated with respect to efficiently solvable or approximable special cases (eg. location problems and multi-dimensional assignment problems).
Other lines of research in this project are the systematic investigation and the algorithmic recognition of the combinatorial properties which are responsible for the efficient solvability of the special cases, the investigation of the connection between efficiently solvable special cases and approximation algorithms aiming at using efficiently solvable special cases to design good approximation algorithms for general instances, and the extension of the investigations to NP-hard problems which are hard to solve approximately. For the latter problems "efficiently approximable cases" will be investigated, meaning cases which can be approximated within a nontrivial performance guarantee in polynomial time.
Subproject F302 Combinatorial Optimization in Complex Systems
The research within subproject F302 aims at the following three main goals: (1) developing new methodologies and strategies for analyzing and solving complex systems, (2) analyzing and solving concrete real-world complex systems and (3) theoretical investigations related to complex systems needed to successfully solve real-world complex systems.
In a world of ever increasing complexity, the development of a successful approach for solving complex real-world problems (improving on the current state of the art) is becoming one of the greatest challenges to combinatorial optimization in the coming years. The main aim of subproject F302 is to make at least a small step towards achieving this ambitious long-term goal.
Most combinatorial optimization problems which arise in practical applications are very complex and typically are not nice and well-investigated basic combinatorial optimization problems, but rather combine the characteristics of many different types of basic problems in a far from trivial way. Such complex combinatorial optimization problems, called complex systems, arise in many areas of modern life both in traditional application fields of operations research like production planning, flexible manufacturing, VLSI-design, distribution, public transportation systems, medicine and biology.
The design of successful solution approaches for complex combinatorial optimization problems which is a major research goal of subproject F302, requires competence in two areas. On the one hand, clearly, a comprehensive knowledge on the basic types of optimization problems which arise as sub-problems in complex systems is indispensable. On the other hand, one needs a deep understanding of the relationships and interconnections between the various sub-problems.
With respect to the investigation of theoretical aspects of complex systems the research within subproject F302 focuses mainly on the asymptotic behavior of combinatorial optimization problems and on the analysis of the performance of heuristic approaches.
START Project Combinatorial Approximation Algorithms (1997-2002)
It is often too time-consuming to compute an exact optimal solution of an NP-hard problem (non-deterministic polynomial). One way out is to be satisfied with approximate solutions. During the 1990s tremendous progress was made in the area of approximation algorithms. The goal of this project is to apply, to extend and to generalize the newly developed techniques. The main focus is on a variety of combinatorial optimization problems where special emphasis is put on sequencing, scheduling, packing and covering problems. Sequencing and scheduling problems involve the allocation of activities to resources of limited capacity and availability over time. In packing and covering problems, the goal is to pack a set of small items into a set of large items or to cover a set of large items by a set of small items.
- supported by Austrian Science Fund (FWF), Grant START Y43-MAT (1997-2002)
- Participants in this project:
- Gerhard J. Woeginger: Principal Investigator
- Walter Bucher: PostDoc
- John Noga: PostDoc
- Stephen Seiden: PostDoc