Skip to main content

Advertisement

Springer Nature Link
Log in

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

  • Research paper
  • Published:
4OR Aims and scope Submit manuscript

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

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
€32.70 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (France)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Aissi H, Bazgan C, Vanderpooten D (2009) Minmax and minmax regret versions of combinatorial optimization problems: a survey. Eur J Oper Res 197:427–438

    Google Scholar 

  • Dolgui A, Kovalev S (2012) Min-max and min-max (relative) regret approaches to representatives selection problem. 4OR Q J Oper Res 10:181–192

    Article  Google Scholar 

  • Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, San Francisco

    Google Scholar 

  • Khot S, Regev O (2008) Vertex cover might be hard to approximate to within \(2-\varepsilon \). J Comput Syst Sci 74:335–349

    Article  Google Scholar 

  • Kouvelis P, Yu G (1997) Robust discrete optimization and its applications. Kluwer Academic Publishers, Boston

    Book  Google Scholar 

Download references

Acknowledgments

Vladimir Deineko acknowledges support by Warwick University’s Centre for Discrete Mathematics and Its Applications (DIMAP) and by EPSRC fund EP/F017871. Gerhard Woeginger acknowledges support by the Netherlands Organization for Scientific Research (NWO), grant 639.033.403, and by DIAMANT (an NWO mathematics cluster).

Author information

Authors and Affiliations

  1. Warwick Business School, The University of Warwick, Coventry, CV4 7AL, UK

    Vladimir G. Deineko

  2. Department of Mathematics and Computer Science, TU Eindhoven, P.O. Box 513, 5600 MB , Eindhoven, The Netherlands

    Gerhard J. Woeginger

Authors
  1. Vladimir G. Deineko
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Gerhard J. Woeginger
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Gerhard J. Woeginger.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Deineko, V.G., Woeginger, G.J. Complexity and in-approximability of a selection problem in robust optimization. 4OR-Q J Oper Res 11, 249–252 (2013). https://doi.org/10.1007/s10288-012-0227-7

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10288-012-0227-7

Keywords

Mathematics Subject Classification

Search

Navigation