On the approximability of minmax (regret) network optimization problems

Simple item page
dc.creatorKasperski, Adam
dc.creatorZielinski, Pawel
dc.date2008-04-02
dc.date2008-10-23
dc.date.accessioned2026-07-07T10:12:16Z
dc.date.available2026-07-07T10:12:16Z
dc.descriptionIn 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.
dc.identifierhttps://arxiv.org/abs/0804.0396
dc.identifierhttp://arxiv.org/abs/0804.0396
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/172127
dc.subjectComputational Complexity
dc.subjectDiscrete Mathematics
dc.titleOn the approximability of minmax (regret) network optimization problems
dc.typetext

Files

Collections

arXiv