On the approximability of minmax (regret) network optimization problems

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

In this paper the minmax (regret) versions of some basic polynomially solvable deterministic network problems are discussed. It is shown that if the number of scenarios is unbounded, then the problems under consideration are not approximable within $\log^{1-ε} K$ for any $ε>0$ unless NP $\subseteq$ DTIME$(n^{\mathrm{poly} \log n})$, where $K$ is the number of scenarios.

Keywords

Computational Complexity, Discrete Mathematics

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/172127

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0804.0396
 http://arxiv.org/abs/0804.0396

Collections

arXiv