All reports by Author Maximilian Witek:

__
TR13-188
| 13th December 2013
__

Christian Glaßer, Maximilian Witek#### Autoreducibility and Mitoticity of Logspace-Complete Sets for NP and Other Classes

__
TR13-047
| 27th March 2013
__

Christian Glaßer, Dung Nguyen, Christian Reitwießner, Alan Selman, Maximilian Witek#### Autoreducibility of Complete Sets for Log-Space and Polynomial-Time Reductions

Comments: 1

__
TR11-053
| 11th April 2011
__

Krzysztof Fleszar, Christian Glaßer, Fabian Lipp, Christian Reitwießner, Maximilian Witek#### The Complexity of Solving Multiobjective Optimization Problems and its Relation to Multivalued Functions

__
TR10-031
| 4th March 2010
__

Christian Glaßer, Christian Reitwießner, Heinz Schmitz, Maximilian Witek#### Hardness and Approximability in Multi-Objective Optimization

__
TR09-076
| 19th August 2009
__

Christian Glaßer, Christian Reitwießner, Maximilian Witek#### Improved and Derandomized Approximations for Two-Criteria Metric Traveling Salesman

Revisions: 1

Christian Glaßer, Maximilian Witek

We study the autoreducibility and mitoticity of complete sets for NP and other complexity classes, where the main focus is on logspace reducibilities. In particular, we obtain:

- For NP and all other classes of the PH: each logspace many-one-complete set is logspace Turing-autoreducible.

- For P, the delta-levels of ...
more >>>

Christian Glaßer, Dung Nguyen, Christian Reitwießner, Alan Selman, Maximilian Witek

We investigate the autoreducibility and mitoticity of complete sets for several classes with respect to different polynomial-time and logarithmic-space reducibility notions.

Previous work in this area focused on polynomial-time reducibility notions. Here we obtain new mitoticity and autoreducibility results for the classes EXP and NEXP with respect to some restricted ... more >>>

Krzysztof Fleszar, Christian Glaßer, Fabian Lipp, Christian Reitwießner, Maximilian Witek

Instances of optimization problems with multiple objectives can have several optimal solutions whose cost vectors are incomparable. This ambiguity leads to several reasonable notions for solving multiobjective problems. Each such notion defines a class of multivalued functions. We systematically investigate the computational complexity of these classes.

Some solution notions S ... more >>>

Christian Glaßer, Christian Reitwießner, Heinz Schmitz, Maximilian Witek

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 >>>

Christian Glaßer, Christian Reitwießner, Maximilian Witek

We improve and derandomize the best known approximation algorithm for the two-criteria metric traveling salesman problem (2-TSP). More precisely, we construct a deterministic 2-approximation which answers an open question by Manthey.

Moreover, we show that 2-TSP is randomized $(3/2+\epsilon ,2)$-approximable, and we give the first randomized approximations for the two-criteria ... more >>>