Approximability of the robust representatives selection problem

DOI10.1016/J.ORL.2014.10.007MaRDI QIDQ1785311zbMATH OpenOpenAlexFDO

Authors Adam Kasperski, Adam Kurpisz, Paweł Zieliński

Publication date 28 September 2018

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1405.5381

zbMATH Keywords

computational complexityuncertaintyrobust optimizationselection problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Integer programming (90C10)

Abstract: In this paper new complexity and approximation results on the robust versions of the representatives selection problem, under the scenario uncertainty representation, are provided, which extend the results obtained in the recent papers by Dolgui and Kovalev (2012), and Deineko and Woeginger (2013). Namely, it is shown that if the number of scenarios is a part of input, then the min-max (regret) representatives selection problem is not approximable within a ratio of $O(lo{g}^{1-epsilon}K)$ for any $epsilon>0$, where $K$ is the number of scenarios, unless the problems in NP have quasi-polynomial time algorithms. An approximation algorithm with an approximation ratio of $O(logK/loglogK)$ for the min-max version of the problem is also provided.

Recommendations

• Complexity and in-approximability of a selection problem in robust optimization
• Min-max and min-max (relative) regret approaches to representatives selection problem
• Approximating the min-max (regret) selecting items problem
• Representative scenario construction and preprocessing for robust combinatorial optimization problems
• Robust approach to restricted items selection problem

Cites work

• scientific article; zbMATH DE number 1405893 (Why is no real title available?)
• Complexity and in-approximability of a selection problem in robust optimization
• Generating Randomized Roundings with Cardinality Constraints and Derandomizations
• Improved approximation algorithms for the Min-Max selecting items problem
• Min-max and min-max (relative) regret approaches to representatives selection problem
• Min-max and min-max regret versions of combinatorial optimization problems: A survey
• On the approximability of minmax (regret) network optimization problems
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• Robust discrete optimization and its applications
• Single machine scheduling with scenarios

Cited in

(11)

• A single representative min-max-min robust selection problem with alternatives and budgeted uncertainty
• Robust approach to restricted items selection problem
• Benchmarking problems for robust discrete optimization
• Two-stage combinatorial optimization problems under risk
• Min-max and min-max (relative) regret approaches to representatives selection problem
• Recoverable robust representatives selection problems with discrete budgeted uncertainty
• Robust two-stage combinatorial optimization problems under discrete demand uncertainties and consistent selection constraints
• Approximating the shortest path problem with scenarios
• Representative scenario construction and preprocessing for robust combinatorial optimization problems
• Complexity and in-approximability of a selection problem in robust optimization
• Robust two-stage combinatorial optimization problems under convex second-stage cost uncertainty

This page was built for publication: Approximability of the robust representatives selection problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1785311)