notesum.ai

Published at November 27

On the Complexity of Recoverable Robust Optimization in the Polynomial Hierarchy

cs.CC

cs.DM

math.OC

F.2.2

Released Date: November 27, 2024

Authors: Christoph Grüne¹, Lasse Wulf²

Aff.: ¹Department of Computer Science, RWTH Aachen University, Germany; ²Section of Algorithms, Logic and Graphs, Technical University of Denmark, Kongens Lyngby, Denmark

Arxiv: http://arxiv.org/abs/2411.18590v1

	$x_{1}$	$x_{2}$	$x_{3}$	$c_{1}=\overline{\ell}_{1}\lor\overline{\ell}_{2}\lor\ell_{3}$
$s_{1}$	1	0	0	0
$s_{2}$	1	0	0	1
$s_{3}$	0	1	0	0
$s_{4}$	0	1	0	1
$s_{5}$	0	0	1	1
$s_{6}$	0	0	1	0
$s_{7}$	0	0	0	1
$s_{8}$	0	0	0	2
$\Sigma$	1	1	1	4