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

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

We study the shrinking and separation properties (two notions well-known in descriptive set theory) for NP and coNP and show that under reasonable complexity-theoretic assumptions, both properties do not hold for NP and the shrinking property does not hold for coNP. In particular we obtain the following results. 1. NP ... more >>>