Complexity and in-approximability of a selection problem in robust optimization

V.G. Deineko; G.J. Woeginger

doi:10.1007/s10288-012-0227-7

Complexity and in-approximability of a selection problem in robust optimization

V.G. Deineko
, G.J. Woeginger

Research output: Contribution to journal › Article › Academic › peer-review

12 Citations (Scopus)

1 Downloads (Pure)

Abstract

We establish strong NP-hardness and in-approximability of the so-called representatives selection problem, a tool selection problem in the area of robust optimization. Our results answer a recent question of Dolgui and Kovalev (4OR Q J Oper Res 10:181–192, 2012). Keywords: Combinatorial optimization; Computational complexity; Robust optimization

Original language	English
Pages (from-to)	249-252
Number of pages	4
Journal	4OR : A Quarterly Journal of Operations Research
Volume	11
Issue number	3
DOIs	https://doi.org/10.1007/s10288-012-0227-7
Publication status	Published - 2013

Access to Document

10.1007/s10288-012-0227-7

Cite this

@article{e01be27904c84c4482767ca184ae7d0c,

title = "Complexity and in-approximability of a selection problem in robust optimization",

abstract = "We establish strong NP-hardness and in-approximability of the so-called representatives selection problem, a tool selection problem in the area of robust optimization. Our results answer a recent question of Dolgui and Kovalev (4OR Q J Oper Res 10:181{\textendash}192, 2012). Keywords: Combinatorial optimization; Computational complexity; Robust optimization",

author = "V.G. Deineko and G.J. Woeginger",

year = "2013",

doi = "10.1007/s10288-012-0227-7",

language = "English",

volume = "11",

pages = "249--252",

journal = "4OR : A Quarterly Journal of Operations Research",

issn = "1619-4500",

publisher = "Springer",

number = "3",

}

TY - JOUR

T1 - Complexity and in-approximability of a selection problem in robust optimization

AU - Deineko, V.G.

AU - Woeginger, G.J.

PY - 2013

Y1 - 2013

N2 - We establish strong NP-hardness and in-approximability of the so-called representatives selection problem, a tool selection problem in the area of robust optimization. Our results answer a recent question of Dolgui and Kovalev (4OR Q J Oper Res 10:181–192, 2012). Keywords: Combinatorial optimization; Computational complexity; Robust optimization

AB - We establish strong NP-hardness and in-approximability of the so-called representatives selection problem, a tool selection problem in the area of robust optimization. Our results answer a recent question of Dolgui and Kovalev (4OR Q J Oper Res 10:181–192, 2012). Keywords: Combinatorial optimization; Computational complexity; Robust optimization

U2 - 10.1007/s10288-012-0227-7

DO - 10.1007/s10288-012-0227-7

M3 - Article

SN - 1619-4500

VL - 11

SP - 249

EP - 252

JO - 4OR : A Quarterly Journal of Operations Research

JF - 4OR : A Quarterly Journal of Operations Research

IS - 3

ER -

Complexity and in-approximability of a selection problem in robust optimization

Abstract

Access to Document

Fingerprint

Cite this