English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In the well-known complexity class NP are combinatorial problems, whoseoptimization counterparts are important for many practical settings. Theseproblems typically consider full knowledge about the input. In practicalsettings, however, uncertainty in the input data is a usual phenomenon, wherebythis is normally not covered in optimization versions of NP problems. Oneconcept to model the uncertainty in the input data, is recoverable robustness.The instance of the recoverable robust version of a combinatorial problem P issplit into a base scenario $\sigma_0$ and an uncertainty scenario set$\textsf{S}$. The base scenario and all members of the uncertainty scenario setare instances of the original combinatorial problem P. The task is to calculatea solution $s_0$ for the base scenario $\sigma_0$ and solutions $s$ for alluncertainty scenarios $\sigma \in \textsf{S}$ such that $s_0$ and $s$ are nottoo far away from each other according to a distance measure, so $s_0$ can beeasily adapted to $s$. This paper introduces Hamming Distance RecoverableRobustness, in which solutions $s_0$ and $s$ have to be calculated, such that$s_0$ and $s$ may only differ in at most $\kappa$ elements. We survey thecomplexity of Hamming distance recoverable robust versions of optimizationproblems, typically found in NP for different scenario encodings. Thecomplexity is primarily situated in the lower levels of the polynomialhierarchy. The main contribution of the paper is a gadget reduction frameworkthat shows that the recoverable robust versions of problems in a large class ofcombinatorial problems is $\Sigma^P_{3}$-complete. This class includes problemssuch as Vertex Cover, Coloring or Subset Sum. Additionally, we expand theresults to $\Sigma^P_{2m+1}$-completeness for multi-stage recoverable robustproblems with $m \in \mathbb{N}$ stages.

The Complexity Classes of Hamming Distance Recoverable Robust Problems