Recent Trends in Combinatorial Optimization

Bachem, Achim and Euler, Reinhardt (1984) Recent Trends in Combinatorial Optimization.
Published in: OR-Spektrum : quantitative approaches in management Vol. 6 (1). pp. 1-21.

Abstract

We survey important parts of the theory of combinatorial optimization as it is developed today. The emphasis lies on new theoretical results, which have proven useful in practical applications. In Section 2 we present some examples and explain our basic notation. The purpose of Section 3 is to introduce central concepts of complexity theory, in particular the notions of easy and hard problems. Starting from matroid, matching and network flow problems we describe how polynomially solvable generalizations of these can be obtained, taking account of the theory of submodular functions as a general framework. Oriented matroids as a suitable concept by which to generalize the theory of convex polyhedra in a purely combinatorial setting are discussed in the first part of a section on polyhedral theory. Part 2 is concerned with the relations between linear systems and combinatorics, in particular integer polyhedra. The structure and evaluation of heuristic algorithms is the subject of Section 6. Finally, we describe basic ideas for the solution of hard optimization problems as they have proven efficient for particular problem classes.


Actions:
Full text not available from this repository.
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr84-002
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 25 Oct 2011 13:48
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/2