Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Heinz Schmitz:

TR10-031 | 4th March 2010
Christian Glaßer, Christian Reitwießner, Heinz Schmitz, Maximilian Witek

Hardness and Approximability in Multi-Objective Optimization

We systematically study the hardness and the approximability of combinatorial multi-objective NP optimization problems (multi-objective problems, for short).

We define solution notions that precisely capture the typical algorithmic tasks in multi-objective optimization. These notions inherit polynomial-time Turing reducibility from multivalued functions, which allows us to compare the solution notions and ... more >>>

TR07-094 | 3rd August 2007
Christian Glaßer, Heinz Schmitz, Victor Selivanov

Efficient Algorithms for Membership in Boolean Hierarchies of Regular Languages

The purpose of this paper is to provide efficient algorithms that decide membership for classes of several Boolean hierarchies for which efficiency (or even decidability) were previously not known. We develop new forbidden-chain characterizations for the single levels of these hierarchies and obtain the following results:

1. The classes of ... more >>>

ISSN 1433-8092 | Imprint