Abstract

We propose a model for recoverable robust optimization with commitment. Given a combinatorial optimization problem and uncertainty about elements that may fail, we ask for a robust solution that, after the failing elements are revealed, can be augmented in a limited way. However, we commit to preserve the non-failing elements of the initial solution. We settle the computational complexity of such a robust counterpart of various classical polynomial-time solvable combinatorial optimization problems. We show, for the weighted matroid independent set problem, that an optimal solution to the nominal problem is also optimal for its robust counterpart. Indeed, matroids are provably the only structures with this strong property. Robust counterparts of other problems are -hard such as the matching problem and the stable set problem, even in bipartite graphs. However, we establish polynomial-time algorithms for the robust counterparts of the unweighted stable set problem in bipartite graphs and the weighted stable set problem in interval graphs, also known as the interval scheduling problem.

1 Introduction↩︎

Robust optimization has become a central framework in operations research for addressing uncertainty in decision-making and optimization. Unlike traditional optimization, where parameters are assumed to be known precisely, robust optimization considers scenarios where some parameters are uncertain but lie within a predefined uncertainty set, which may be specified implicitly. Early research in this area focused on computing static solutions that optimize the worst-case cost. For comprehensive overviews, we refer to [2]–[4]. However, it is well recognized that this approach may lead to overly conservative solutions as a single, potentially very unlikely, scenario might heavily influence the outcome.

To address this issue of conservatism in robust optimization and introduce more flexibility, various frameworks have been proposed, including two-stage adjustable robust optimization by [5], recoverable robust optimization by [6], and demand robust optimization by [7]. These frameworks share a common two-stage structure: In the first stage, a partial solution is determined based on the uncertainty set, while in the second stage, after the uncertain scenario has been revealed, the initial solution can be adjusted within some predefined recovery bounds. This second-stage adjustment is referred to as recourse.

In this work, we use the notion of recoverable robust optimization as introduced by Liebchen, Lübbecke, Möhring and Stiller [6]. Initially developed in the context of timetabling, linear programming, and railway optimization, it seeks first-stage solutions that can be adapted feasibly across all scenarios within specified recovery limits; the corresponding recovery limits are modeled, for example, via the size of the symmetric difference of solutions. The cost is typically evaluated as the sum of the first- and second-stage costs, potentially under different cost functions. This model has been successfully applied to a variety of combinatorial optimization problems such as the shortest path problem [8]–[10], spanning tree and more general matroid problems [11]–[13], perfect matchings [14], scheduling problems [15], knapsack problems [16], [17], and selection problems [18] which led to insights into the computational complexity, as well as the development of exact and approximate algorithms for solving these problems.

A major drawback of recourse models, including the recoverable robustness framework, is that they do not necessarily preserve the elements of the initial solution during recourse. However, such preservation is crucial in many practical applications, particularly when commitments or promises have been made. In any reservation-based system—such as hotel bookings, rental car reservations, or airline seat reservations—the supplier guarantees services to the customers holding reservations. If a customer cancels her reservation, the supplier may modify the set of reserved customers, but must ensure that the previously reserved customers who did not cancel remain part of the modified solution. In such scenarios, the supplier can only augment the existing set of reserved (and not canceled) customers with new customers, without altering the existing commitments.

This motivates us to introduce our new model Recoverable Robust Optimization with Commitment, where we commit to the first-stage decision, and restrict the recourse action to augmenting the partial solution which remains after the cancellation or after some other uncertain disruption has taken place. More formally, we define the problem as follows.

1.0.0.1 Recoverable Robust Optimization with Commitment.

Consider a combinatorial optimization problem \(\Pi\) with ground set \(E\), a set \(\mathcal{F} \subseteq 2^E\) of feasible solutions, and a weight function \(w \colon E \rightarrow \mathbb{R}_+\), where the task is to find a solution \(S \in \mathcal{F}\) maximizing \(w(S) = \sum_{e \in S} w(e)\). In the first stage in our model, we choose a solution \(S \in \mathcal{F}\) to the underlying problem \(\Pi\). Then, in the second stage, a set \(F\subseteq E\) of at most \(k\) elements is deleted, followed by a step in which a set \(R\subseteq E\setminus F\) of size at most \(\ell\) elements is added to \(S \setminus F\) such that the resulting set is still a solution, i.e., \(S' = (S \setminus F) \cup R\in \mathcal{F}\). We call \(S\) the first-stage solution and \(S'\) the second-stage solution. The goal is to select a first-stage solution \(S\) that maximizes the weight of the second-stage solution, \(w(S')\) in the worst case.

We refer to the set \(F\) that is deleted as the interdiction and the set \(R\) that is added as recourse. The interdiction can be seen as an adversary, who aims to delete a set \(F\subseteq E\) that decreases the final objective value \(w(S')\) as much as possible. The adversary can be assumed to have full knowledge of the set \(R\subseteq E \setminus F\) that we would optimally add during the recourse phase following the deletion of \(F\). Thus, we solve the following problem: \[\begin{align} \label{eq:3240k44l41recoverablerobustproblem} \max_{S\in \mathcal{F}}~~ \min_{\substack{F\subseteq E \\ |F| \leq k }}~~ \max_{\substack{R\subseteq E \setminus F, ~ |R| \leq \ell\\ (S \setminus F) \cup R\in \mathcal{F}}}~~ w((S \setminus F) \cup R)\;. \end{align}\tag{1}\]

For the sake of simplicity, we assume that \(E \leftarrow E \cup \{\emptyset\}\), i.e., \(\{ \emptyset \} \in E\), and we define \(w(\{\emptyset\})\mathrel{\vcenter{:}}= 0\). The inclusion of the empty set in \(E\) allows us to conveniently represent scenarios involving empty deletions or additions of the elements in \(E\). Further, throughout the paper, we consider downward-closed set systems \(\mathcal{F}\), meaning that if \(X' \subseteq X\) and \(X \in \mathcal{F}\), then \(X' \in \mathcal{F}\). Additionally, for a set \(X\) and an element \(g\), we use \(X+g \mathrel{\vcenter{:}}= X\cup\{g\}\) and \(X-g \mathrel{\vcenter{:}}= X\setminus{\{g\}}\).

A significant part of this paper will deal with the special case of the (1 ) with \(k=1\) and \(\ell = 1\). Formally we define the restricted version where \(k=1\) and \(\ell=1\) as follows: \[\begin{align} \label{eq:3240144141recoverablerobustproblem} \max_{S\in \mathcal{F}}~~ \min_{f\in E}~~ \max_{\substack{e\in E-f\\ S-f+e\in \mathcal{F}}}~~ w(S-f+e) \;. \end{align}\tag{2}\]

Without loss of generality, we assume that the interdiction is non-empty.

For a combinatorial optimization problem \(\Pi\), we call the robust variant of \(\Pi\) as in (2 ) the robust counterpart of \(\Pi\), or Robust \(\Pi\) in short. We usually call the problem \(\Pi\), i.e., \(\max \{w(f)\mid f\in \mathcal{F}\}\), the underlying or nominal problem.

As an example, consider a car-rental company with a single car, which we wish to rent out to different customers to maximize the total revenue. All customers have their own time intervals in which they want to rent the car exclusively and a price they are willing to pay. If there is no uncertainty, this is equivalent to an instance of the interval scheduling problem, where we are given a set of weighted intervals on the real line, and the goal is to find a maximum-weighted set of pairwise-disjoint intervals. However, after the selection of the initial solution, some customers might withdraw from the contract, leading to less revenue for our company. In this case, we could still add unserved customers to our remaining initial solution. Although the additional customers should not be in conflict with our remaining initial solution, as those reservations were firm. As a concrete example, consider the five intervals \((1, 3)\), \((2, 5)\), \((4, 7)\), \((6, 9)\), \((8, 10)\) with weights \(10, 8, 2, 8, 10\), respectively, each representing a customer. Picking \((1, 3)\), \((4, 7)\), and \((8, 10)\) is an optimal solution to the underlying problem with value \(22\). An optimal solution to the robust counterpart, however, is to pick only \((1, 3)\) and \((8, 10)\), knowing that if \((1, 3)\) or \((8, 10)\) is interdicted, in the recourse one can add \((2, 5)\) or \((6, 9)\), respectively. This leads to a worst-case weight of 18 after the interdiction and recourse. On the other hand, when considered the optimal solution to the underlying problem, i.e., picking \((1, 3)\), \((4, 7)\), and \((8, 10)\), the deletion of interval \((1, 3)\) would lead to a final value of 12 in the robust version, as the interval \((4, 7)\) blocks the recourse. This shows that selecting an optimal solution to the nominal problem need not be optimal for its robust counterpart.

1.0.0.2 The Adversary Problem.

A closely related problem is the adversary problem of 1 . It is the subproblem of 1 in which the set \(S \in \mathcal{F}\) is already fixed and the adversary needs to find the optimal interdiction set \(F\). That is, given some \(S \in \mathcal{F}\), the task is to solve the following problem: \[\begin{align} \label{eq:40k44l41adversaryproblem} \min_{\substack{F\subseteq E \\ |F| \leq k }}~~ \max_{\substack{R\subseteq E \setminus F, ~ |R| \leq \ell\\ (S \setminus F) \cup R\in \mathcal{F}}}~~ w((S \setminus F) \cup R)\;. \end{align}\tag{3}\]

Note that if \(\ell \geq |E|\) for 1 , it is optimal to choose an empty first-stage solution, as the recourse is essentially unbounded. Hence, for \(\ell \geq |E|\), we can assume \(S = \emptyset\). For this case, problem 3 is often called the interdiction version of the problem and is also known as the most vital edge problem. For many underlying problems, its interdiction version is -hard if \(k\) is part of the input, including spanning tree interdiction [19], [20], matching interdiction [21], [22], or shortest path interdiction [23]. However, for constant \(k\) the adversary problem is clearly polynomial time solvable by simple enumeration.

1.0.0.3 Bounded-Regret Problem.

Another closely related problem, which is both independently interesting and crucial for parts of our results, is the bounded-regret version of our problem. In the setting of our model, after the interdiction of an element \(f\in E\), one takes the recourse action that may add an element \(e \in E - f\) to the set \(S - f\) which maximizes the total weight of the final solution. However, the weight of the final solution \(w(S-f+e)\) could be less than the weight of the initial solution \(w(S)\). This weight loss, \(w(S)-w(S-f+e)\), can be seen as a regret; we denote it by \(\Delta(f,S)\) and it is formally defined as: \[\Delta(f, S) = w(S) - \max \{w(S-f+e) \mid e\in E-f, S-f+e \in \mathcal{F}\}\;.\]

The goal in the bounded-regret problem is to find a maximum-weight solution \(S\) such that, for each element \(f\in E\), the interdiction of \(f\) followed by the construction of a maximum-weight second-stage solution \(S-f+e\), results in a regret bounded by some given value \(\lambda \in \mathbb{R}\); formally: \[\begin{align} \label{eq:opt:sol:bounded-regret} \max_{\substack{S\in \mathcal{F}\\ \Delta(f, S) \leq \lambda: \forall f\in E }} w(S) \;. \end{align}\tag{4}\]

We note that for some values of \(\lambda\) the problem 4 can be infeasible. We denote by \(w_{\text{opt}}(\lambda)\) the objective value of 4 for an optimal solution, if one exists. The bounded-regret version for general values of \(k\) and \(\ell\) of the problem is defined analogously. However, in this work, we focus on the above mentioned case with \(k = \ell = 1\). Now, notice the tight connection between the bounded-regret version 4 and the robust counterpart 2 of a problem. If we have a polynomial-time algorithm for 4 , and if there are only polynomial-many different candidates for \(\lambda\) values, then one can enumerate over all \(\lambda\) values and solve 4 for each one of them. Finally, to solve 2 , we are interested in the \(\lambda\) value which maximizes \(w_{\text{opt}}(\lambda) - \lambda\). The idea is that, if we choose a set \(S \subseteq E\) corresponding to the solution \(w_{\text{opt}}(\lambda)\) while selecting the first-stage solution of 2 , the maximum regret, even after adversarial interdiction and recourse, will be at most \(\lambda\). Thus, the corresponding value \(\max_{\lambda} w_{\text{opt}}(\lambda) - \lambda\) gives us an optimal solution of 2 . Now, observe that for \(k = \ell = 1\) the number of possible \(\lambda\) values is at most \(O(|E|^2)\) and hence polynomially bounded. Note that \(\lambda\) can also be negative and hence we also enumerate over these choices.

1.1 Our Contribution↩︎

Table 1: Our results. Note that hardness results for the \((1, 1)\)-case also imply hardness for the general \((k, \ell)\)-case.
	unweighted	weighted
\((k, \ell)\)-for \(k \leq \ell\)	Polynomial	Polynomial
\((1, p)\)-for constant \(p\)	Polynomial	Polynomial
\((1, 1)\)-	-hard	-hard
\((1, 1)\)-	Polynomial	-hard

We present algorithms and complexity results for a variety of combinatorial optimization problems in the model of Recoverable Robust Optimization with Commitment. In this paper, we focus on some underlying problems that are classical downward-closed combinatorial optimization problems which can be solved in polynomial time. As one would expect, robust counterparts of some of these problems turn out to be -hard, even in the setting \(k = \ell = 1\). However, in some cases the robust counterpart indeed remains polynomial-time solvable. The most prominent problem in this category is the Robust Matroidproblem. We show that Robust Matroid is polynomial time solvable if \(k \leq \ell\). In fact, we show that it suffices to solve the nominal problem for obtaining an optimal first-stage solution for the robust counterpart. Surprisingly, this does not hold as soon as \(k>\ell\). For other problems, solving the robust counterpart is much more involved. Table 1 summarizes our results.

A major challenge in designing algorithms for the robust problem lies in the fact that a first-stage solution \(S\) must be robust against any interdiction with possible recourse taken into account, even if \(k=\ell=1\). Intuitively, we may pre-compute for each element \(f\in E\), a “backup element” for the scenario in which the element \(f\) fails. We then solve “the problem with backups”. However, this increases the problem complexity substantially as such backups must not be selected for the solution \(S\) and the uncertainty about the failing element (and its activated backup) causes complex dependencies.

Next, we discuss our main results for the variety of problems; definitions follow later.

1.1.0.1 Robust Matroid (RM).

We study the problem of finding a maximum-weight independent set of a matroid in the robust setting. We refer to this problem as Robust Matroid(RM for short). We show that an optimal solution to the nominal problem, i.e., the problem of finding a maximum-weight independent set in a matroid, is also an optimal first-stage solution for its robust counterpart, whenever \(k \leq \ell\).

Hence, the classical greedy algorithm for the nominal problem implies a polynomial-time algorithm for RM. This is a bit surprising since the adversary problem of a special case of the nominal problem, spanning tree interdiction, is -hard in general. However, this is not a contradiction since in our algorithm and proof we do not need to actually compute the adversary’s response and can simply prove that computing an optimal solution to the nominal problem is also optimal for RM.

Further, we give two cases in which this property is not true: First, we show that for \(k > \ell\), the optimum solution to the nominal problem need not be an optimum solution to RM, even if \(k=2\) and \(\ell =1\). Second, we also show that for any non-matroid this property is not true, even if \(k=\ell=1\). Therefore, for \(k \leq \ell\), matroids are exactly those structures for which the price of robustness, i.e., the worst-case ratio between the weight of an optimal solution to the underlying problem and the weight of an optimal first-stage solution to its robust counterpart, is guaranteed to be one.

1.1.0.2 Robust Stable Set in Interval Graphs (RIS).

We give a polynomial-time algorithm for \((1, 1)\)-Robust Interval Stable Set, the stable set problem in interval graphs. For convenience, we view this problem as selecting pairwise-disjoint intervals from a given set of intervals and call it Robust Interval Scheduling(RIS). Our key ingredient is a reduction of RIS to its bounded-regret version. In general, it is not straightforward to construct a polynomial-time algorithm for the bounded-regret problem, even in the case of the matroid independent set problem for which we know that the robust counterpart can be solved efficiently. As a crucial step, we show that for a given \(\lambda\), the bounded-regret Robust Interval Scheduling problem can be reduced to a more general interval scheduling problem, which we call Interval Scheduling with Colors(ISC) and for which we give an efficient dynamic program. Furthermore, we show how this result can be generalized to \((1, p)\)-Robust Interval Stable Set for any constant \(p \in \mathbb{Z}_{\geq 1}\).

1.1.0.3 Robust Bipartite Matching (RBM).

Even for the unweighted case, we show that RBM is -hard; we give a reduction from -SAT. Here, the underlying problem Bipartite Matching can be viewed as a special case of a matroid intersection problem. Hence, our complexity result for RBM reveals a drastic increase in problem difficulty when the underlying problem involves finding a maximum-weight independent set of the intersection of two matroids instead of a single matroid. This is somewhat surprising, as for a single matroid, even an optimal solution of the nominal problem is optimal for its robust counterpart.

1.1.0.4 Robust Bipartite Stable Set (RBSS).

A maximum-weight stable set in a graph is the complement of a minimum-weight vertex-cover, which in bipartite graphs can be found (in polynomial-time) via a primal-dual algorithm which simultaneously computes both, a maximum-weight matching, and a minimum-weight vertex cover. Hence, the complexity of Bipartite Stable Set and Bipartite Matching is the same and even the algorithms are very similar (which inspired us to look into these problems more closely). However, the complexity of the robust counterpart of bipartite stable set, RBSS, depends highly on the weights. We show that, for unit weights, RBSS is polynomial-time solvable (even in more general König-Egerváry graphs). We prove this by reducing the problem to finding repairable maximum stable sets, which are maximum stable sets \(S\) satisfying that for each \(v \in S\) there is some \(u \in V \setminus S\) such that \(S - v + u\) is a stable set. We then show that repairable maximum stable sets can be found in polynomial time (if they exist). Further, we show that RBSS is -hard in the weighted setting.

Recoverable robust optimization is a powerful framework for decision-making under uncertainty that combines robustness with limited adaptability. Due to its generality, many (robust) combinatorial optimization problems can be naturally interpreted as recoverable robust problems. Most research in this area has focused on settings where the second-stage costs are uncertain, and recourse actions are constrained by a parameter that restricts the symmetric difference between the first-stage and second-stage solution. When facing discrete uncertainty—where a finite list of potential cost functions is explicitly given—many recoverable robust problems turn out to be -hard, even for problems that are polynomial-time solvable in the full-information setting, such as the shortest path problem [8], basic scheduling and selection problems [2], [24], [25]. To address this issue, approximation algorithms have been proposed; see, e.g., [25], [26].

In contrast, under interval uncertainty, these problems often reduce to finding two solutions to the nominal problem minimizing the weight for two different cost functions, while ensuring that the size of the symmetric difference is bounded. This reduction has been applied to problems such as the selection problem [18], spanning trees [11], general matroids [13], the traveling salesperson problem [27], and the assignment problem [28].

While most prior work focuses on cost uncertainty, some recent works have begun assuming structural uncertainty [14], [29], as we do in this paper. For instance, [14] studied the following related model: given a bipartite graph and a set of uncertain edges \(F\), the task is to find a perfect matching \(M\) such that for any subset \(F' \subseteq F\) with \(|F'|\leq r\), the graph \(G-F'\) contains a perfect matching \(M'\) where the symmetric difference of \(M\) and \(M'\) is bounded by some parameter. [14] establish hardness results for this problem and give characterizations for graphs that admit such matchings \(M\).

Similar two-stage concepts that introduce a degree of adaptivity in robust optimization have been explored under different names. One example is adjustable robustness, studied by [5] in the context of robust linear programming and applications to multi-stage inventory management problem. Here, certain solution variables have to be fixed in the first stage, before the uncertain data is revealed (“here and now” decisions), whereas other variables can be adjusted in a second stage, after the uncertain data becomes known (“wait and see” decisions).

In contrast, in demand robustness or two-stage adjustable robustness, all solution variables are free to be adjusted in the second stage. However, the extent of these adjustments is regulated via a cost function, where the cost for setting a variable in the second stage (typically selecting it to be part of the solution) is substantially higher than its first-stage cost. This model has been studied extensively from both complexity and approximation perspectives for problems such as certain linear programs [30]–[32], a variety of discrete covering problems including shortest paths, Steiner trees, set cover, and facility location [7], [33]–[36], matching [37], and scheduling problems [38].

In all these different models, a commitment to the first-stage solution is not explicitly required. Instead, recourse is constrained by restricting the symmetric difference between first-stage and second-stage cost and/or by applying different cost functions for the two stages. In this paper, we explicitly require commitment to the first-stage solution while allowing limited adaptation in the second stage. This adaptation is achieved by adding (selecting) a restricted number of additional solution variables in the second stage. Notably, similar fine-grained restrictions on recourse budgets have been explored in some problem-specific contexts. For example, Büsing, Koster, and Kutschka explicitly limit the number of items that can be added or removed from the first-stage solution for the knapsack problem, in an experimental context [24]. Further, [15] require that a certain number of jobs must have the same scheduling position in the first and second stage in a single-machine scheduling problem. With our model, we aim to provide a general framework for recoverable robustness with commitment, unifying and extending such problem-specific approaches.

In this paper, we focus on downward-closed problems, where a solution remains feasible even if arbitrary elements are removed. Hence, the structural uncertainty impacts only the solution quality (cost) and not its feasibility. This proves to be both interesting and challenging within our model.

A somewhat opposing setting is captured by bulk-robustness and flexible network design. In this framework, we select a superset of a solution that remains feasible even if a subset of elements from a given list is deleted. Hence, considering upward-closed problems, the goal is to find a minimum-cost solution that remains feasible in any scenario. Bulk-robustness has been studied in various contexts such as connectivity and matchings [39]–[43]. The key difference between this model and ours is that, in this model, the structure of the solution can differ significantly from that of the nominal problem, whereas in our setting, the structure of a feasible solution remains unchanged.

2 Preliminaries↩︎

We consider simple undirected graphs consisting of a set of nodes denoted by \(V(G)\) and a set of edges denoted by \(E(G)\). Occasionally, we omit the notation \(G\) and instead only write \(V\) or \(E\). A stable set, widely also known as an independent set in a graph \(G\) is a subset of vertices \(V'\subseteq V\) such that the induced subgraph \(G[V']\) does not contain any edge. A matching in a graph consists of a set of pairwise-disjoint edges. A graph \(G\) is bipartite if the vertex set can be partitioned into two disjoint sets \(V = A\;\dot{\cup}\;B\) such that each edge \(e \in E\) has one endpoint in \(A\) and the other in \(B\). An interval graph is a graph that has an interval representation: each vertex \(v \in V\) can be associated with an interval \(i_v\) on the real line and two vertices share an edge if and only if their corresponding intervals intersect. The line graph of a graph \(G\) contains the vertex set corresponding to \(E(G)\), and there is an edge between two vertices if and only if the corresponding edges share an endpoint in \(G\).

A non-empty downward-closed set system \((E, \mathcal{I})\) with \(\mathcal{I}\subseteq 2^E\) is a matroid if it satisfies the exchange property: \[\label{ex1} ifI,J \in \mathcal{I}and|I|<|J|,thenI+g \in \mathcal{I}{ for some } g\in J\setminus{I}.\tag{5}\]

Given a matroid \(\mathcal{M}=(E,\mathcal{I})\), a subset \(I\subseteq E\) is called independent if \(I\in \mathcal{I}\), and dependent otherwise. For \(X\subseteq E\), an inclusion-wise maximal independent subset of \(X\) is called a basis of \(X\). Let us denote by \(\mathcal{B}\) the collection of all bases of \(E\) which are also the bases of the matroid \(\mathcal{M}\). It follows from (5 ) that all bases of \(\mathcal{M}\) have the same cardinality. For an element \(f\in E\), we define \(\mathcal{M}-f\mathrel{\vcenter{:}}= (E - f, \mathcal{I}')\), where \(\mathcal{I}' \mathrel{\vcenter{:}}= \{ I \in \mathcal{I} \mid f\notin I \}\).

It is a well-known fact [44] that a non-empty collection \(\mathcal{B}\subseteq 2^E\) of sets forms the base set of a matroid if and only if the following strong basis exchange property holds: \[\begin{align} & ifB_1, B_2 \in \mathcal{B},\;a \in B_1 \setminus{B_2},then\exists b \in B_2 \setminus{B_1}\\ & withB_1-a+b \in \mathcal{B}andB_2-b+a \in \mathcal{B}. \end{align}\]

3 Robust Matroid↩︎

In this section, we consider the problem \((k, \ell)\)-Robust Matroid(\((k,\ell)\)-RM) for \(k \leq \ell\), where we are given a matroid \(\mathcal{M}=(E, \mathcal{I})\) with weight function \(w \colon E \rightarrow \mathbb{R}\), and the task is to solve 1 for \(k \leq \ell\) with the feasibility set \(\mathcal{F}\) equal to the independent set system \(\mathcal{I}\). That is, in this section, we consider the following problem:

|@ l@ X l
Given: & A matroid \(\mathcal{M}=(E, \mathcal{I})\) with weight function \(w \colon E \rightarrow \mathbb{R}_+\).
Task: & Find \(I\in \mathcal{I}\) such that for all \(F\subseteq E, |F|\leq k\), there exists \(R\subseteq E\setminus F, |R|\leq \ell\) such that \((I\setminus F)\cup R\in \mathcal{I}\), and the weight \(w((I\setminus F)\cup R)\) is maximized.

A circuit of a matroid is an inclusion-wise minimal dependent set. Recall that for any basis \(B\in \mathcal{B}\) of a matroid \(\mathcal{M}\), and any \(g\in E\setminus{B}\), there exists a unique circuit, called \(C(B,g)\), among the elements in \(B\cup \{g\}\). Recall further that the collection of circuits \(\mathcal{C}\) of a matroid satisfies the following cycle exchange property: for any two circuits \(C_1, C_2\in \mathcal{C}\), and any \(g\in C_1\cap C_2\), there exists a circuit \(C_3\in \mathcal{C}\) with \(C_3\subseteq (C_1\cup C_2) \setminus{\{g\}}\).

Furthermore, matroids are closed under deletion and contraction operations. That is, for any matroid \(\mathcal{M} = (E, \mathcal{I})\) and any \(F\subseteq E\), the system \(\mathcal{M} \setminus F= (E \setminus F, \mathcal{I} \setminus F)\) with independence system \(\mathcal{I} \setminus F\mathrel{\vcenter{:}}= \{I \subseteq E \setminus F\mid I \in \mathcal{I}\}\), as well as the system \(\mathcal{M} /F = (E \setminus F, \mathcal{I} / F)\) with independence system \(\mathcal{I} / F \mathrel{\vcenter{:}}= \{I \subseteq E \setminus F\mid F\cup I \in \mathcal{I}\}\), are again matroids. For more details see, e.g., [45].

Let \(\mathcal{B}\) be the collection of bases of the matroid \(\mathcal{M}=(E,\mathcal{I})\). We will prove that for any weight function \(w \colon E \rightarrow \mathbb{R}\), any maximum-weight basis in \(\mathcal{B}\) is also an optimal solution to \((k,\ell)\)-RMif \(k \leq \ell\). We use the following lemma.

lemmamatroidhelper Let \(B\) be a maximum-weight basis of \(\mathcal{M}\) and let \(f\in B\). Further, let \(e\in \mathop{\mathrm{arg\,max}}\{ w(g) \mid g\in E\setminus{\{f\}}, \;B - f+ g \in \mathcal{B} \}\). Then \(B - f+ e\) is a maximum-weight basis of \(\mathcal{M} - f\).

Proof. Let \(B' = B - f+ e\), and let \(B^\star\) be a maximum weight independent set in \(\mathcal{M}-f\) with \(|B^\star \cap B'|\) maximum. If \(B' \neq B^\star\), take any \(a \in B^\star \setminus B'\). By the strong basis exchange property there exists \(b \in B' \setminus B^\star\) with \(B^\star - a + b \in \mathcal{B}\) and \(B' -b + a \in \mathcal{B}\). Therefore we have that (i) \(w(a) > w(b)\), since \(B^\star\) is a maximum weight basis of \(\mathcal{M}-f\), and by our choice of \(B^\star\) being closest to \(B'\). Hence, \(B - b + a\) cannot be a basis of \(\mathcal{M}\), since \(w(B - b + a) > w(B)\), and \(B\) was a maximum weight basis of \(\mathcal{M}\). Therefore we have that \(b \notin C(B, a)\), but \(b \in C(B', a)\), where \(B'= B -f+e\). This implies that \(f\in C(B, a)\), and thus (ii) \(w(a) \leq w(e)\) by the choice of \(e\) as an element of maximum weight among those that can be feasibly exchanged with \(f\). But then (i) and (ii) together imply that \(w(b) < w(e)\). Since \(f\in C(B,e)\cap C(B,a)\), by the circuit exchange property, there exists a circuit \(\bar{C}\subseteq \left( C(B,e)\cup C(B,a) \right) \setminus\{f\}\subseteq B-f+e+a=B'+a\). Thus, this circuit \(\bar{C}\) must be equal to the unique circuit \(C(B',a)\) which contains \(b\). It follows that \(b\in C(B',a)=\bar{C} \subseteq \left( C(B,e)\cup C(B,a) \right) \setminus\{f\}\) with \(b\not\in C(B,a)\), implying that \(b\in C(B,e)\). Summarizing, \(B-b+e\) is a basis of larger weight in matroid \(\mathcal{M}\) than \(B\), a contradiction. ◻

theoremmatroidbasisopt Any maximum-weight basis of \(\mathcal{M}\) is an optimal first-stage solution for \((k,\ell)\)-Robust Matroidif \(k \leq \ell\). Thus, \((k,\ell)\)-Robust Matroid is polynomial-time solvable if \(k \leq \ell\).

Proof. Let \(S\) be a maximum weight basis of \(\mathcal{M}\) and let \(S^\star\) be an optimal first-stage solution to RM. Furthermore, let \(F\) be the set of elements that are deleted by the adversary in the worst-case for the first-stage solution \(S\) and let \(S'\) be its second-stage solution after the deletion of \(F\) and the recourse. Thus, \(S'\) is a maximum-weight basis in matroid \(\mathcal{M} \setminus{F}/(S\setminus{F})\). Additionally, let \(S^\star_F\) be the second-stage solution for the first-stage solution \(S^\star\) with interdiction set \(F\). We will show that \(w(S') \geq w(S^\star_F)\). Since \(F\) was the worst-case choice of the adversary for \(S\) and \(F\) could also be chosen as an interdiction set for \(S^\star\), we have that then \(S\) is also an optimal first-stage solution. Hence, it remains to prove \(w(S') \geq w(S^\star_F)\).

Consider the adversary and the recourse as a one-by-one process, in which the elements in \(F\) are deleted one after the other in a fixed order, and after each deletion of an element (the adversary’s action) another element is added to the solution (the recourse), until all elements of \(F\) have been deleted and each recourse has been added. That is, we have a fixed order of the elements in \(F\), i.e., \(f_1, f_2, \dots, f_k\), \(f_i \in F\) for \(1 \leq i \leq k\) and in step \(i\) the element \(f_i\) is deleted and an element \(e_i \in E \setminus (S \cup \{f_1, f_2, \dotsc, f_i\})\) is added to \(S\) such that \((S \cup \{e_1, e_2, \dots, e_i\}) \setminus \bigcup_{j = 1}^{i} \{f_j\}\) is an independent set (or an element \(e_i^\star \in E \setminus (S^\star \cup \{f_1, f_2, \dots, f_i\})\) for \(S^\star\), respectively). Hence, we consider this process for \(S\) and \(S^\star\). Note that we can do this process if \(k \leq \ell\).

In this process, one can potentially add elements from \((E \setminus S) \cap F\) that are then removed again in a later step (and the same for \(S^\star\)). Furthermore, in this process, as recourse for the elements in the first-stage solution \(S\) we always add the elements from the remaining set of elements \(E \setminus (S \cup \{f_1, f_2, \dots, f_{i-1}\})\) that maximizes the weight of the resulting basis of \(\mathcal{M} \setminus \bigcup_{j = 1}^{i-1} \{f_j\}\). That is, \(e_i \in \mathop{\mathrm{arg\,max}}\{ w(g) \mid \big( (S + g - f_i \cup \{e_1, e_2, \dots, e_{i-1}\}) \setminus \bigcup_{j = 1}^{i} \{f_j\} \big) \in \mathcal{I} \}\). Note that this is always possible due to the strong basis exchange property (taking \(B_1:= S\cup\{e_1, \ldots, e_{i-1}\} \setminus{\{f_1, \ldots, f_{i-1}\}}\), \(a:=f_j\), and \(B_2:=S'\)).

For the optimal first-stage solution \(S^\star\), if some element is deleted during the process, we simply add some element from the final solution \(S^\star_F\). Let \(S_i\) and \(S_i^\star\), \(0 \leq i \leq k\), be the intermediate bases obtained by this process for \(S\) and \(S^\star\), respectively. Again, note that we can always add an element for each removed element since \(k \leq \ell\).

Now we invoke Lemma [lem:matroid-helper] and have that \(S_1\) is a maximum weight basis of \(\mathcal{M}-f_1\). Furthermore, iteratively we can now invoke Lemma [lem:matroid-helper] to show that \(S_i\) is a maximum weight basis of \(\mathcal{M} \setminus \bigcup_{j = 1}^{i} \{f_j\}\). Hence, we have that \(w(S_i) \geq w(S^\star_i)\) for all \(1 \leq i \leq k\). In particular, since \(S_k\) is an optimal basis of \(\mathcal{M}\setminus{F}\), and since \(S_k\) contains all elements from \(S\setminus{F}\), it follows that \(w(S')=w(S_k)\), implying \(w(S') = w(S_k) \geq w(S_k^\star) = w(S^\star_F)\). Consequently, by using the polynomial-time greedy algorithm for the matroid basis problem [46], we can compute an optimal first-stage solution for \((k,\ell)\)-Robust Matroid in polynomial time if \(k \leq \ell\). ◻

We observe that this result does not hold if \(k > \ell\), which is highlighted in the following example. It remains open whether this problem admits a polynomial-time algorithm for \(k > \ell\).

Figure 1: Counterexample showing that an optimal nominal solution (middle) need not be optimal for the robust counterpart of the (2,1)-Robust Matroid problem. — Figure 1: Counterexample showing that an optimal nominal solution (middle) need not be optimal for the robust counterpart of the \((2,1)\)-Robust Matroid problem.

Example 1. Consider the instance of \((2,1)\)-Robust Matroid as illustrated in Figure 1, in the left picture. The maximum-weight independent sets, i.e., the bases of the (graphic) matroid are the spanning trees of the depicted graph. It is not hard to see that the unique maximum-weight basis, which is the spanning tree shown in the middle with a total weight \(17\), is not an optimum solution for the robust counterpart: If we start with the spanning tree of value \(17\) as first-stage solution, the guaranteed surviving value is only \(7\), since the adversary might delete the two edges of weight \(5\) and \(8\), and we can only augment by adding one of the two edges of value \(3\). Instead, if we start with the spanning tree consisting of the edges of values \(3, 5\) and \(3\) as shown in the right picture, the adversary will delete edges with value \(8\) and \(3\) (vertical). Without adding any other edge in the recourse step, the total weight is \(8\).

Further, we show that matroids are the only downward-closed set systems for which an optimal solution to the nominal problem is also an optimal solution to its robust counterpart.

Theorem 1. For every non-empty downward-closed set system \(\mathcal{F} \subseteq 2^E\) which is not a matroid, there exist weights \(w \colon E \to \mathbb{R}_+\) such that an optimal solution to the nominal problem is not an optimal first-stage solution for the robust counterpart.

Recall that a non-empty downward-closed system \(\mathcal{F}\subseteq 2^E\) is not a matroid if the exchange property (5 ) is violated. Such non-matroids can be characterized via the following Lemma (see, e.g., [47] for the proof).

Lemma 1. Let \(\mathcal{F}\subseteq 2^E\) be a non-empty downward-closed system which is not a matroid, and let \(\bar{\mathcal{F}}\subseteq \mathcal{F}\) be the collection of the inclusion-wise maximal sets in \(\mathcal{F}\). Then there exist two sets \(X,Y\in \bar{\mathcal{F}}\), and three elements \(\{a,b,c\}\subseteq X\Delta Y \mathrel{\vcenter{:}}= (X\setminus{Y})\cup (Y\setminus{X})\) such that for each set \(Z\in \bar{\mathcal{F}}\) with \(Z\subseteq X\cup Y\), either \(a\in Z\), or \(\{b,c\}\subseteq Z\).

Proof of Theorem 1.. Take \(X,Y\in \bar{\mathcal{F}}\), and the three elements \(\{a,b,c\}\subseteq X\Delta Y\) as in the statement of Lemma 1. We set the weights of all elements in \(E\setminus{\{a,b,c\}}\) to zero, and \(w(a) = 3\), \(w(b) = w(c) = 2\). Then the optimal first-stage solution for the \((1, 1)\)-robust counterpart is to select either \(S=\{b\}\), or \(S=\{c\}.\) Then, if the adversary interdicts, one can still add \(\{a \}\) and achieve a second-stage value of 3. Otherwise, if the adversary does not interdict, one can extend to the optimal solution of the underlying problem \(\{b, c\}\) of value 4.

In contrast, if the first-stage solution \(S\) is equal to a nominal optimal solution, then \(S\) necessarily contains \(\{b, c \}\), and one can only achieve a value of \(2\). Because if either \(b\) or \(c\) is interdicted, one cannot extend \(S\) by an element of positive value in the recourse. ◻

4 Robust Stable Set in Interval Graphs↩︎

In this section we consider Robust Stable Set in interval graphs. For convenience, we use the standard interval representation of an interval graph \(G=(V,E)\) where each node is represented as an interval in \(\mathbb{R}\), and a stable set in \(G\) corresponds to a selection of pairwise-disjoint intervals. We refer to the task of finding a maximum-weighted set of disjoint intervals as Interval Scheduling(InS) and its robust counterpart as Robust Interval Scheduling(RIS). Further, we refer to the intervals as jobs as it is common in scheduling. It is known that InS is solvable in polynomial time via dynamic programming [48]. We formally define the Robust Interval Scheduling problem as follows.

|@ l@ X l
Given: & A set of intervals \(I = \{i_1, i_2, \dots, i_n\}\), where \(i_j = [a_j, b_j)\), \(a_j < b_j\), \(a_j, b_j\in \mathbb{N}\), a weight function \(w \colon I\to \mathbb{R}_{\geq 0}\), and a family \(\mathcal{F}\subseteq 2^{I}\) of sets of pairwise-disjoint intervals in \(I\).
Task: & Find a set \(S \in \mathcal{F}\) which maximizes the total weight \(w(S - i_j + i_\ell)\) for the deletion of any interval \(i_j\) and the best possible recourse by another interval \(i_\ell\) thereafter.

Note that \(\{\emptyset\}\in I\), since we redefine each of our ground sets such that it includes \(\{\emptyset\}\); this way the empty set in \(I\) can be used to show the possible empty deletion and empty recourse. We prove the following main result.

Theorem 2. There is a polynomial-time algorithm for \((1,1)\)-Robust Interval Scheduling.

Later in Subsection 4.3, we show how to generalize this theorem to \((1,p)\)-Robust Interval Scheduling for any constant \(p\in \mathbb{N}\), in which we can add up to \(p\) intervals as recourse after the deletion of a single interval.

4.1 Algorithm Outline and Proof Roadmap↩︎

Here, we outline our algorithmic approach for the proof of Theorem 2. As mentioned in the introduction, one can reduce the robust counterpart of a nominal problem to its bounded-regret version (4 ). The bounded-regret version of RIS, which we denote as \(\lambda\)-Robust Interval Scheduling(\(\lambda\)-RIS), asks to find \(S \in \mathcal{F}\) which optimizes the following objective function: \[\begin{align} \label{eq:opt:sol:RIS-bounded-regret} \max_{\substack{S\in \mathcal{F}\\ \Delta(i_j, S) \leq \lambda \colon\forall i_j \in I }} ~w(S), \end{align}\tag{6}\]

where \(\Delta(i_j, S) = w(S) - \max \{w(S-i_j+i_{\ell}) \mid i_{\ell}\in I-i_j, S-i_j+i_{\ell} \in \mathcal{F}\}.\) The value \(\Delta(i_j, S)\) defines the loss in the objective value occurred due to the change in the solution in case \(i_j\) fails. Note that, if \(i_j \in S\), then we simply have \(\Delta(i_j, S) = w(i_j) - \max \left\{w(i_{\ell}) \mid i_{\ell} \in I\setminus S,\;S-i_j+i_{\ell} \in \mathcal{F} \right\}\).

Due to the established tight connection between (4 ) and (2 ) formulations, a polynomial-time algorithm for \(\lambda\)-RIS implies a polynomial-time algorithm for RIS, since here the number of different values of regrets is bounded by \(\mathcal{O}(|I|^2)\). As a result, we have the following proposition.

Proposition 3. A polynomial-time algorithm for the problem \(\lambda\)-Robust Interval Scheduling implies a polynomial-time algorithm for \((1,1)\)-Robust Interval Scheduling.

Given Proposition 3, it remains to provide a polynomial-time algorithm for \(\lambda\)-RIS for an arbitrary fixed value of \(\lambda \in \mathbb{R}\). Recall that \(\lambda\) corresponds to the maximum loss (regret) in the objective value for any job that gets deleted. Therefore, it will be convenient to hedge against regrets larger than \(\lambda\) by defining for each job \(i_j\) a backup of weight at least \(w(i_j)-\lambda\); this backup can then be used in the recourse if job \(i_j\) fails. Further, we give a formal definition of a backup of an interval.

4.1.0.1 Defining backups.

Let \(\mathcal{F}(I)\) be a collection of sets of pairwise-disjoint intervals in \(I\), and \(S\in \mathcal{F}(I)\). We define, for each element \(i_j \in I\), a backup element \(\boldsymbol{b}(i_j, S)\): \[\boldsymbol{b}(i_j, S) \in \mathop{\mathrm{arg\,max}}_{\substack{i_\ell \in I \setminus (S + i_j)\\ S - i_j + i_\ell \in \mathcal{F}(I)}} \;w(i_\ell) \;.\] Informally speaking, \(\boldsymbol{b}(i_j, S)\) is a best possible recourse that can be added to the remaining solution \(S - i_j\) when \(i_j\) is interdicted. Hence, \(\boldsymbol{b}(i_j, S)\) serves as a backup for \(i_j\).

Note that, for a job \(i_j\in S\), its backup \(\boldsymbol{b}(i_j, S)=i_{j'}\) may or may not intersect with \(i_j\). Hence, the backup job \(i_{j'}\) of \(i_j\) satisfies one of the following two conditions, depending on whether or not \(i_j\) and \(i_{j'}\) intersect.

\(S + i_{j'} \notin \mathcal{F}(I)\), or
\(S + i_{j'} \in \mathcal{F}(I)\).

In case (a), job \(i_{j'}\) cannot be used as a backup for any other job \(i \neq i_j\), since \(i_j\in S\) and \(i_j\cap i_{j'}\neq \emptyset\). Hence, we call such a backup the private backup of job \(i_j\). In case (b), job \(i_{j'}\) can be used as a backup for any job \(i \in I\setminus \{i_{j'}\}\), since \(i_{j'}\) does not intersect with any job in \(S\), and hence we call such a backup a universal backup. Note that since a universal backup, say \(u\), can be used as a backup for any job \(i \in I- u\), it is enough to have one such backup for all jobs that might not have a private backup. For a first-stage solution set \(S\), we want a universal backup \(u\) to be in \(\mathop{\mathrm{arg\,max}}\{ w(i_{j'}) \mid i_{j'} \in I \setminus S \text{ and } S + i_{j'} \in \mathcal{F}(I) \}\).

For the case where \(\lambda<0\) and the universal backup \(u\) is interdicted, if there is no recourse, the value \(\Delta(u,S)=0\) is strictly larger than \(\lambda\). This contradicts the feasibility of \(S\). To deal with this issue, we choose an extra backup \(b\) along with our universal backup \(u\). In particular, we aim to have \(b \in \mathop{\mathrm{arg\,max}}\{ w(i_{j'}) \mid i_{j'} \in I \setminus (S + u) \text{ and } S + i_{j'} \in \mathcal{F}(I)\}\). Moreover, we have \(w(u) \geq w(b)\). Note that, since we have \(\{\emptyset\} \in I\), if there is no candidate job to serve as a universal backup or an extra backup, we have \(u=\{\emptyset\}\) or \(b =\{\emptyset\}\). All in all, we solve an instance of the \(\lambda\)-RIS problem by first guessing a pair of universal and extra backup, \(u,b \in I\), and then solving the problem.

In Section 4.2, we show that for the correct guess of universal and extra backup, \(\lambda\)-RIS can be reduced to solving a more general interval scheduling problem, which we call Interval Scheduling with Colors(ISC). Below we give a formal definition of Interval Scheduling with Colors(ISC): An instance \(\mathcal{I}=(I,w)\) of ISC consists of a set \(I\) of jobs and a weight function \(w \colon I \rightarrow \mathbb{R}_{\geq 0}\). Each job \(i_j\in I\) potentially has two half open intervals \([\ell_j, r_j)\) and \([a_j, b_j)\) satisfying \(\ell_j \leq a_j < b_j \leq r_j\) associated with it. The inner interval \([a_j, b_j)\) is red and the interval \([\ell_j, r_j)\) is blue. A feasible solution is a subset \(S\) of jobs such that for any two jobs \(i_j, i_k \in S\), we have that \([a_j, b_j)\) and \([\ell_k, r_k)\) do not intersect and that \([a_k, b_k)\) and \([\ell_j, r_j)\) do not intersect. That is, the red interval of any job in the solution is not allowed to intersect with the blue interval of any other job in the solution. The task is to pick a feasible solution of maximum weight. We show in Theorem [thm:interval-selection-soft-hard] in Section 4.2 that this problem can be solved in polynomial time.

4.2 The Algorithm for Bounded-Regret Interval Scheduling↩︎

We present an efficient algorithm for \(\lambda\)-Robust Interval Scheduling for a fixed value of \(\lambda\).

theoremboundedregretinterval Given a polynomial-time algorithm for Interval Scheduling with Colors, there is a polynomial-time algorithm for \(\lambda\)-Robust Interval Scheduling.

Proof. To prove the theorem, we first describe the reduction from \(\lambda\)-Robust Interval Scheduling to Interval Scheduling with Colors(ISC) and then prove its correctness.

Let \(\mathcal{I}=(I,w)\) be an instance of \(\lambda\)-RIS. In the first step, we enumerate over all pairs of jobs \(u, b \in I\) such that \(w(u) \geq w(b) \geq - \lambda\), and corresponding to each such pair, we construct an instance \(\mathcal{I}_{u, b}'(\lambda)=(I_{u, b}'(\lambda), w')\) of ISC.

First, fix a pair \(u,b\in I\) corresponding to the universal backup and the extra backup, respectively, each of which may be empty. Note that there are three cases: (i) both a universal and extra backup exist, (ii) an extra backup exists, but a universal backup does not, or (iii) neither a universal nor an extra backup exists.

For each job \(i_j\in I\), we add the following set of jobs in \(I_{u,b}'\) with weights \(w'\), which cover all possible recourse actions for \(i_j\). We further define a function \(\lambda_{u, b}\) to model the regret and use this function to prune \(I_{u,b}'\) in order to obtain \(I_{u, b}'(\lambda)\).

The first set of jobs covers the possibility of using the universal backup \(u\) as recourse. Thus, for each job \(i_j \in I \setminus \{ u, b \}\) in \(\lambda\)-RIS, we add a job \(i'_j\) to \(I_{u, b}'\) in ISC with \(w'(i'_j) = w(i_j)\). Moreover, the red and blue interval of \(i'_j\) is set to \([a_j, b_j)\), which is the interval of \(i_j\). We set \(\lambda_{u, b}(i'_j) = w(i_j) - w(u)\).
The second set of jobs corresponds to the possibility of using a private backup. Thus, for each ordered pair of jobs \((i_j, i_k)\) from set \(I \setminus \{ u, b \}\), \(i_j \neq i_k\), such that \(i_j\) and \(i_k\) intersect, we add a job \(i^k_j\) to \(I_{u, b}'\). We set \(w'(i^k_j) = w(i_j)\) and \(\lambda_{u, b}(i^k_j) = w(i_j) - w(i_k)\). Let \(\ell_{j,k} \mathrel{\vcenter{:}}= \min \{a_j, a_k \}\) and \(r_{j,k} \mathrel{\vcenter{:}}= \max \{ b_j, b_k \}\). Then we define the red interval of \(i^k_j\) to be \([a_j, b_j)\) and the blue interval to be \([\ell_{j,k}, r_{j,k})\).

Pruning: Finally we want to make sure that the red interval of a job does not intersect with the jobs corresponding to the universal and extra backups. For that, we simply delete all those jobs from \(I'_{u,b}\) which intersect with \(u\) and \(b\). Further, we define \(I'_{u, b}(\lambda) \mathrel{\vcenter{:}}= \{ i'_j \in I'_{u, b} \mid \lambda_{u, b}(i'_j) \leq \lambda \}\) to include all jobs of \(I'_{u, b}\) that have a \(\lambda_{u, b}\)-value of at most \(\lambda\). As a result we get our instance \(\mathcal{I}'_{u, b}(\lambda)= (I'_{u, b}(\lambda), w')\), here \(w'\) is restricted to the set \(I'_{u, b}(\lambda)\). See Figure 2 for reference. Let \(\mathcal{F}(I'_{u, b}(\lambda))\) be the set of feasible solutions of \(\mathcal{I}'_{u, b}(\lambda)\).

Figure 2: Reduction from (1,1)-Robust Interval Scheduling to Interval Scheduling with Colors. Here, we guessed \lambda = -1, and i_2 as the universal and i_1 as the extra backup. The crossed jobs in the instance of ISC are the pruned jobs. The jobs i_5', i_6', i_5^3, i_6^4, i_5^6, and i_6^5 are pruned because their red part overlaps with the universal backup. Additionally, the jobs i_3' and i_4' are pruned because their \lambda' values are greater than the current \lambda =-1 value. — Figure 2: Reduction from \((1,1)\)-Robust Interval Scheduling to Interval Scheduling with Colors. Here, we guessed \(\lambda = -1\), and \(i_2\) as the universal and \(i_1\) as the extra backup. The crossed jobs in the instance of ISC are the pruned jobs. The jobs \(i_5', i_6', i_5^3, i_6^4, i_5^6\), and \(i_6^5\) are pruned because their red part overlaps with the universal backup. Additionally, the jobs \(i_3'\) and \(i_4'\) are pruned because their \(\lambda'\) values are greater than the current \(\lambda =-1\) value.

In the remainder of the proof, we show that an optimal solution \(S^\star\) of \(\mathcal{I}\) is in one-to-one correspondence with the optimal solution \(S\) of \(\mathcal{I}'_{u, b}(\lambda)\) which maximizes the value \(w'(S)\) over all \(u, b \in I\). Moreover, the set \(S\) has the same weight and regret value as that of \(S^\star\). To get an intuition, first observe that all jobs in \(I'_{u, b}(\lambda)\) correspond to the jobs in \(I\); we simply add some blue intervals to them. Blue intervals of jobs correspond to their respective backup jobs, and hence they are allowed to intersect in a chosen solution of ISC. Furthermore, note that for all jobs \(i_j' \in I'_{u, b}(\lambda)\) we have \(\lambda_{u, b}(i'_j) \leq \lambda\), which encodes that the regret we suffer if the corresponding interval \(i_j\) is interdicted is indeed at most \(\lambda\). Now, it remains to show that from an optimum solution \(S^\star\) of \(\mathcal{I}\), we can compute an optimum solution \(S\) of \(\mathcal{I}'_{u, b}(\lambda)\) of the same weight, and from an optimum solution \(S\) to \(\mathcal{I}'_{u, b}(\lambda)\) we can compute an optimum solution \(S^\star\) to \(\mathcal{I}\) of the same weight and regret \(\lambda\).

Let \(S^\star\) be an optimum solution to \(\mathcal{I}\). We now construct in polynomial time a solution to the corresponding instance \(\mathcal{I}'_{u, b}(\lambda)\) of Interval Scheduling with Colors of the same weight. By definition we have that \(w(i_j) - w( \boldsymbol{b}(i_j, S^\star)) \leq \lambda\). Without loss of generality, we assume that \(S^\star\) does not contain \(u\) and \(b\).

By construction of \(\mathcal{I}'_{u, b}(\lambda)\), for each \(i_m \in S^\star\) that uses the universal backup \(u\) when \(i_m\) fails, there is a new job \(i'_m\) in \(I_{u, b}'(\lambda)\) with \(w'(i_m') = w(i_m)\) and \(\lambda_{u, b}(i'_m) = w(i_m) - w(u)\). Since \(w(i_m) - w(\boldsymbol{b}(i_m, S^\star)) \leq \lambda\), we have that \(\lambda_{u, b}(i'_m) \leq \lambda\), and hence \(i'_m \in I'_{u, b}(\lambda)\). We let \[S_U \mathrel{\vcenter{:}}= \{ i'_m \mid i_m \in S^\star \text{ and i_m has {universal} backup} \} \;.\]

Now consider any job \(i_m \in S^\star\) that has a private backup \(i_k \mathrel{\vcenter{:}}= \boldsymbol{b}(i_m, S^\star)\). By construction of \(I'_{u, b}(\lambda)\), there is a job \(i^k_m \in \mathcal{I}'_{u, b}(\lambda)\) with \(w'(i^k_m)= w(i_m)\) and \(\lambda_{u, b}(i^k_m) \leq w(i_m) - w(i_{k}) \leq \lambda\). Hence, \(i^k_m\) is contained in \(I_{u, b}'(\lambda)\). We let \[S_P \mathrel{\vcenter{:}}= \{ i^k_m \mid i_m \in S^\star \text{ and i_m has a {private} backup i_k \mathrel{\vcenter{:}}= \boldsymbol{b}(i_m, S^\star)} \} \;.\]

Let \(S = S_P \cup S_U\). We claim that \(S\) is a feasible solution to \(\mathcal{I}'_{u, b}(\lambda)\). This directly follows from the definition of blue and red intervals: First, observe that all jobs in \(S\) are indeed contained in \(I_{u, b}'(\lambda)\). Second, note that no two red intervals of jobs in \(S\) intersect, since \(S^\star\) is a feasible solution before the failure of any job. Third, observe that no blue interval intersects with any red interval in \(S\), as \(S^\star - i_m + \boldsymbol{b}(i_m, S^\star)\) is feasible for any job \(i_m \in S^\star\) and its backup \(\boldsymbol{b}(i_m, S^\star)\).

Next, we show how to construct in polynomial time a feasible solution to \(\mathcal{I}\) from an optimum solution to \(\mathcal{I}'_{u, b}(\lambda)\) with the same weight and regret \(\lambda\).

The proof of this direction is similar to the previous direction and hence we only sketch it here. From an optimal solution \(S\) to \(\mathcal{I}'_{u, b}(\lambda)\) one can obtain in a straightforward way a solution \(S^\star\) to \(\mathcal{I}\). It is then easy to see that the regret of \(S^\star\) is at most \(\lambda\) and the weights of the solutions \(S\) and \(S^\star\) coincide.

This concludes the proof. ◻

Finally, we provide a dynamic program that solves Interval Scheduling with Colors in polynomial time.

theoremthmISSHpolytime There is a polynomial-time algorithm for Interval Scheduling with Colors.

Proof. We extend the classical dynamic programming algorithm for Interval Scheduling [48] to ISC. We denote by \(\mathcal{F}(I)\) the set of feasible solutions for the set of jobs in \(I\), where \(I\) is an instance of Interval Scheduling with Colors. In particular, any \(S \in \mathcal{F}(I)\) satisfies that for any job in \(S\), the red part of that job does not overlap with the red or blue part of any other job in \(S\). Let \(A = \{ a_1, \dots, a_n \}\) and \(B = \{ b_1, \dots, b_n \}\) be the sets of start and end points of all red intervals of the jobs, respectively. Furthermore, let \(L = \{ \ell_1, \dots, \ell_n \}\) and \(R = \{ r_1, \dots, r_n \}\) be the sets of start and end points of all blue intervals of the jobs, respectively. These sets \(A\), \(B\), \(L\), and \(R\) need not be ordered. We define \(T_b = \max_{1 \leq i \leq n} b_i\) and \(T_r = \max_{1 \leq i \leq n} r_i\).

For all \(t_b \in B\) and for all \(t_r \in R\), define \(B_{t_b, t_r} = \{i_j \in I \mid b_j = t_b \text{ and } r_j \leq t_r \}\) and \(R_{t_b, t_r} = \{i_j \in I \mid r_j = t_r \text{ and } b_j \leq t_b \}\). Additionally, let \(I_{t_b, t_r} = \{ i_j \in I \mid b_j \leq t_b \text{ and } r_j \leq t_r \}\). Analogous to \(\mathcal{F}(I)\) we also define \(\mathcal{F}(I_{t_b, t_r})\).

In the algorithm, for each tuple \((t_b, t_r)\in B\times R\), we compute a maximum weight set \(S \in \mathcal{F}(I_{t_b, t_r})\). We define \[S^\star(t_b, t_r) \mathrel{\vcenter{:}}= \mathop{\mathrm{arg\,max}}_{S \in \mathcal{F}(I_{t_b, t_r})} w(S) \quad \text{ and } \quad s^\star(t_b, t_r) \mathrel{\vcenter{:}}= \max_{S \in \mathcal{F}(I_{t_b, t_r})} w(S) \;.\]

Additionally, for \(t, t' \in A \cup B \cup L \cup R\), let \(s^\star(t, t') \mathrel{\vcenter{:}}= \max_{t_b \leq t, t_r \leq t'} s^\star(t_b, t_r)\) (and similarly \(S^\star(t, t')\)). Our goal is to find \(S^\star(T_b, T_r)\) and \(s^\star(T_b, T_r)\). Suppose that we have computed the following:

\(S^\star(t, t')\) and \(s^\star(t, t')\) for all \(t \leq \tau_b\) and \(t' \leq \tau_r\), \(t, t' \in A \cup B \cup L \cup R\) for some \(\tau_b \in B\) and \(\tau_r \in R\) such that \(\tau_b \leq \tau_r\), and
\(S^\star(t, t')\) and \(s^\star(t, t')\) for all \(t < \tau_b\) and \(t, t' \in A \cup B \cup L \cup R\).

For the first step, let \(t'_r \mathrel{\vcenter{:}}= \min \{t'_r \in R \mid t'_r > \tau_r \}\) be the next time point after \(\tau_r\) at which a blue interval of some job ends.

We get \[s^\star(\tau_b, t'_r) = \max \Big\{ s^\star(\tau_b, \tau_r), ~ \max_{i_j \in R_{\tau_b, t'_r}} \{ s^\star(\ell_j, a_j) + w(i_j) \} \Big\} \;\]

and \(S^\star(\tau_b, t'_r)\) is the corresponding set where \(s^\star(\tau_b, t'_r)\) is attained. After exhaustively computing this first step for all \(t_r'\in R\), we can compute \(S^\star(t, t')\) and \(s^\star(t, t')\) for all \(t \leq \tau_b\) and \(t' \in A \cup B \cup L \cup R\).

For the second step, let \(t'_b \mathrel{\vcenter{:}}= \min \{t'_b \in B \mid t'_b > \tau_b \}\) be the next time point after \(\tau_b\) at which a red interval of some job ends. Furthermore, let \(r_{t'_b} \mathrel{\vcenter{:}}= \min \{ r \in R \mid \exists i_j \in I \text{ such that } b_j = t'_b \text{ and } r_j = r \}\) and define \(I^=_{t_b, t_r} = \{i_j \in I \mid b_j = t_b \text{ and } r_j = t_r \}\). Note that \(I^=_{t'_b, r_{t'_b}} \neq \emptyset\). We obtain \(S^\star(t'_b, r_{t_b'})\) and \(s^\star(t'_b, r_{t_b'})\) as follows: \[s^\star(t'_b, r_{t_b'}) = \max \Big\{ s^\star(\tau_b, r_{t_b'}), ~ \max_{i_j \in I^=_{t'_b, r_{t_b'}}} \{ s^\star(\ell_j, a_j) + w(i_j) \} \Big\} \;\]

and \(S^\star(t'_b, r_{t_b'})\) is the corresponding set where \(s^\star(t'_b, r_{t_b'})\) is attained. Furthermore, after each of the above two steps, for \(t, t' \in A \cup B \cup L \cup R\), we update \(s^\star(t, t')\) and \(S^\star(t, t')\).

It is straightforward to verify that the above dynamic programming algorithm produces an optimal solution in polynomial time, which proves the theorem. ◻

Combining Proposition 3 with Theorem [thm:IS:helper] and Theorem [thm:interval-selection-soft-hard] directly implies Theorem 2.

4.3 Generalization to \((1,p)\)-Robust Interval Scheduling↩︎

In this section, we consider the \((1,p)\)-Robust Interval Scheduling problem (\((1,p)\)-RIS), a natural generalization of \((1,1)\)-Robust Interval Scheduling, in which the adversary still deletes one element but the algorithm may recover by adding up to \(p\) elements. We extend the ideas from the previous section to \((1,p)\)-RIS for an arbitrary constant \(p \in \mathbb{Z}_{\geq 1}\).

Theorem 4. There is a polynomial-time algorithm for \((1,p)\)-Robust Interval Scheduling for any constant \(p \in \mathbb{Z}_{\geq 1}\).

To prove this theorem, we show that Proposition 3 and Theorem [thm:IS:helper] can be generalized. The generalization of Proposition 3 is straightforward, since the total number of distinct values that the regret \(\lambda\) can attain is \(\mathcal{O}(n^{p+1})\). Consequently, we can again exploit the strong connection between the robust version of the problem and its bounded-regret variant. In particular, this observation yields a polynomial-time algorithm for \((1,p)\)-RIS for any constant \(p\), provided that the bounded-regret version can be solved efficiently for each fixed value of \(\lambda\). We refer to the bounded-regret problem as \(\lambda\)-\((1,p)\)-RIS and it remains to solve \(\lambda\)-\((1,p)\)-RIS. To this end, in the next paragraphs we show that \(\lambda\)-\((1,p)\)-RIS can be reduced to a polynomial number of Interval Scheduling with Colors instances, each of which being solvable in polynomial time due to Theorem [thm:interval-selection-soft-hard]. This reduction, in turn, provides the desired generalization of Theorem [thm:IS:helper]. To do this, we first define a generalized notion of private, universal, and extra backup.

4.3.0.1 Defining backups for \((1,p)\)-Robust Interval Scheduling.

We generalize the notion of backups introduced in the last section to \((1,p)\)-Robust Interval Scheduling. For a job \(i_j\), let \(P^{i_j}\mathrel{\vcenter{:}}= \{i_k \in I \mid [a_k, b_k) \cap [a_j, b_j) \neq \emptyset\}\) be the set of jobs that intersect \(i_j\). Let \(\mathcal{F}(I)\) be a collection of sets of pairwise-disjoint intervals in \(I\), and \(S\in \mathcal{F}(I)\). We define, for each element \(i_j \in I\), a backup set \(\boldsymbol{b}_p(i_j, S)\) of size at most \(p\): \[\boldsymbol{b}_p(i_j, S) \in \mathop{\mathrm{arg\,max}}_{\substack{R \subseteq I \setminus (S + i_j)\\ (S - i_j) \cup R \in \mathcal{F}(I)\\ |R| \leq p}} \;w(R) \;.\] Informally speaking, \(\boldsymbol{b}_p (i_j, S)\) is a best possible recourse of size at most \(p\) that can be added to the remaining solution \(S - i_j\) when \(i_j\) is interdicted. Hence, \(\boldsymbol{b}_p (i_j, S)\) serves as a backup for \(i_j\). For technical reasons later we assume that this backup is unique, which can be obtained by slightly perturbing the weights of the jobs so that optimum solutions do not change.

Note that, for a job \(i_j\in S\), its backup \(\boldsymbol{b}_p (i_j, S)\) can be partitioned into a private part \(\boldsymbol{b}_p^{\rm pr} (i_j, S)\) and a universal part \(\boldsymbol{b}_p^{\rm un} (i_j, S)\) such that \(\boldsymbol{b}_p (i_j, S) = \boldsymbol{b}_p^{\rm pr} (i_j, S) \cup \boldsymbol{b}_p^{\rm un} (i_j, S)\), \(\boldsymbol{b}_p^{\rm pr} (i_j, S) \cap \boldsymbol{b}_p^{\rm un} (i_j, S) =~\emptyset\), and

\(\boldsymbol{b}_p^{\rm pr} (i_j, S) \subseteq P^{i_j}\), and
\(\boldsymbol{b}_p^{\rm un} (i_j, S) \cap P^{i_j} = \emptyset\).

This is simply a generalization of the \((1, 1)\)-case: All jobs of \(\boldsymbol{b}_p (i_j, S)\) that intersect with \(i_j\), i.e., the jobs in \(\boldsymbol{b}_p^{\rm pr} (i_j, S)\), can only be added if \(i_j\) is removed from \(S\) and hence they are private for job \(i_j\). If \(|\boldsymbol{b}_p^{\rm pr} (i_j, S)| = q\), we call this a \(q\)-private backup for \(i_j\). Similarly, all jobs in \(\boldsymbol{b}_p^{\rm un} (i_j, S)\) can be added to \(S\) without deleting \(i_j\). Hence, \(\boldsymbol{b}_p^{\rm un} (i_j, S)\) can be added to \(S\) as a recourse for any \(i_j \in S\). If \(|\boldsymbol{b}_p^{\rm un} (i_j, S)| = q\), we call this a \(q\)-universal backup. However, there is a fundamental difference compared to the \((1, 1)\)-case: Now, the recourse after deleting \(i_j\) from \(S\) may consist of both, private and universal backups. Hence, there might exist multiple distinct \(q\)-universal backups for a solution \(S\), depending on the deletion of the adversary. To handle this, we show in the following decomposition lemma that the number of different \(q\)-universal backups is bounded. For this, we define \(U_q \mathrel{\vcenter{:}}= \{ \boldsymbol{b}_p^{\rm un} (i_j, S) \mid i_j \in S \text{ and } |\boldsymbol{b}_p^{\rm un} (i_j, S)| = q \}\), i.e., the set of distinct universal backups of \(S\) of size exactly \(q\). Recall that we can assume that \(\boldsymbol{b}_p (i_j, S)\) is unique and hence \(\boldsymbol{b}_p^{\rm un} (i_j, S)\) is well-defined.

Figure 3: The set of red intervals consists of a solution, and the set of gray intervals are the corresponding free intervals which together form the set Free. Additionally, the green intervals form the set I_{\rm Free} \subseteq I. — Figure 3: The set of red intervals consists of a solution, and the set of gray intervals are the corresponding free intervals which together form the set Free. Additionally, the green intervals form the set \(I_{\rm Free} \subseteq I\).

Lemma 2. Let \(I\) be an instance of \((1,p)\)-Robust Interval Scheduling and let \(S\) be an optimum first-stage solution of \(I\). Then the following holds.

\(\boldsymbol{b}_p (i_j, S)\) can be decomposed into a private part \(\boldsymbol{b}_p^{\rm pr} (i_j, S)\) and a universal part \(\boldsymbol{b}_p^{\rm un} (i_j, S)\) as above.
There are at most \(2q+1\) many \(q\)-universal backups, i.e., \(|U_q| \leq 2q+1\).

Proof. The first part is trivial due to our discussion above. Hence, it remains to prove the second part. Let \(S = \{ i_1, \ldots, i_m\}\) be the first-stage solution ordered non-decreasingly by starting times of the jobs, where \(i_j = [a_j, b_j)\). Let \(a_0\) be the smallest starting time of any job in \(I\) and let \(b_n\) be the largest finishing time of any job in \(I\). Define the free intervals \(f_0 = [a_0, a_1)\), \(f_1 = [b_1, a_2)\), \(f_2 = [b_2, a_3)\), …, \(f_m=[b_m, b_n)\) to be the intervals that are not occupied by \(S\) and let \({\rm Free} = \{f_0, f_1, \ldots, f_m\}\). Let \(I_{{\rm Free}} \subseteq I\) be the set of jobs that lie completely within some \(f_i \in {\rm Free}\). See Figure 3 for reference. By definition of universal backups, any universal backup \(i_k \in I \setminus S\) cannot intersect a job of \(S\) and hence must lie in some \(f_i \in {\rm Free}\). Therefore, \(i_k \in I_{{\rm Free}}\). Note, however, that the private backup \(\boldsymbol{b}_p^{\rm pr} (i_j, S)\) of some job \(i_j \in S\) can intersect \(f_{j-1}\) and \(f_j\) but no other \(f_i\), \(i \notin \{j-1, j\}\). Otherwise, if \(\boldsymbol{b}_p^{\rm pr} (i_j, S)\) intersects some \(f_i\), \(i \notin \{j-1, j\}\), \(\boldsymbol{b}_p^{\rm pr} (i_j, S)\) is not a feasible backup, since \(\boldsymbol{b}_p^{\rm pr} (i_j, S)\) is a subset of \(P^{i_j}\) and hence it must intersect \(i_{j-1}\) or \(i_{j+1}\).

Let \(R_f^q \subseteq I_{{\rm Free}}\) be the maximum weight set of at most \(q\) jobs from \(I_{{\rm Free}}\). Note that \(R_f^q\) can intersects at most \(q\) intervals of \({\rm Free}\) and let these intervals be \({\rm Free}' \subseteq {\rm Free}\). By the properties of a private backups, for any \(j\) such that \(f_{j-1}, f_j \notin {\rm Free}'\), the job \(i_j \in S\) can have \(R_f^q\) as a \(q\)-universal backup. Since \(R_f^q \subseteq I_{{\rm Free}}\) is the maximum weight subset of jobs of \(I_{{\rm Free}}\) that selects at most \(q\) jobs, we have \(\boldsymbol{b}_p^{\rm un} (i_j, S) = R_f^q\) (recall that we assume the backup to be unique). Furthermore, since \(|R_f^q| \leq q\) and hence \(|{\rm Free}'|\leq q\), there are at most \(2q\) jobs \(i_j \in S\) such that \(\boldsymbol{b}_p^{\rm pr} (i_j, S)\) intersects with a job in \(R_f^q\). Each such job might have its unique \(q\)-universal backup \(\boldsymbol{b}_p^{\rm un} (i_j, S)\). Hence, in total there are at most \(2q+1\) many \(q\)-universal backups, which proves the Lemma. ◻

Similar to the \((1, 1)\)-case, we also have extra backups: For the case where \(\lambda<0\) and a job \(i_j\) of a \(p\)-universal backup is interdicted, we need an extra backup. However, note that there is at most one \(p\)-universal backup, since the recourse is bounded by \(p\) and in that case the private backup for any job is empty. Therefore, the \(p\)-universal backup of any job \(i_j \in S\) is \(R^p\), where \(R^p\) is the maximum weight set of jobs that does not intersect \(S\) and contains at most \(p\) jobs. Since any job \(i_k\) of \(R^p\) can be removed, for each such case we need at most one extra backup of size \(p\) that does not contain any job from \(S \cup \{i_k\}\), and hence the number of extra backups is bounded by \(p\). This leads to the following lemma.

Lemma 3. Let \(I\) be an instance of \((1,p)\)-Robust Interval Scheduling and let \(S\) be an optimum first-stage solution of \(I\). Then the total number of universal and extra backups is bounded by \(p \cdot (p+3)\).

Proof. Due to Lemma 2, we know that the total number of \(q\)-universal backups is bounded by \(2q+1\). Hence, the total number of universal backups is bounded by \[\sum_{q=1}^p (2q+1) = p + 2 \cdot \sum_{q=1}^p q = p + p \cdot (p+1) = p \cdot (p+2) \;.\] By our previous discussion, the number of extra backups is bounded by \(p\) and hence the total number of universal and extra backups is bounded by \[p \cdot (p+2) + p = p \cdot (p+3) \;,\] which proves the lemma. ◻

Lemma 3 allows us to guess the set of universal and extra backups of an optimum solution: The size of each set is bounded by \(p\) and there are at most \(p \cdot (p+3)\) many distinct sets. Hence, the total number of guesses we need to perform is \(\mathcal{O}((n^p)^{p \cdot (p+3)})\), which is polynomial if \(p\) is constant.

After guessing the value of \(\lambda\) and guessing the set of universal and extra backups of an optimum solution, we construct an instance of Interval Scheduling with Colors, similar to the \((1, 1)\)-case. Here, it remains to construct, for each \(i_j \in I\), the appropriate private backups. Recall that a \(q\)-private backup of \(i_j \in I\) must intersect \(P^{i_j}\mathrel{\vcenter{:}}= \{i_k \in I \mid [a_k, b_k) \cap [a_j, b_j) \neq \emptyset\}\). Each \(P^{i_j}\), \(i_j\in I\), can be calculated in \(\mathcal{O}(n)\) time. To obtain all possibilities for a \(q\)-private backup, for each \(q \in \{1, 2, \ldots, p\}\) we enumerate over all starting points \(\ell\) and ending points \(r\) of that private backup such that \(\ell \leq r\). For each \(q\) and each such pair of endpoints \((\ell, r)\), we compute in polynomial time the maximum weighted set of pairwise disjoint intervals in the set \(\{i_k\in P^{i_j} \mid l\leq a_k < b_k\leq r\}\) that contains at most \(q\) intervals. The total number of \((\ell,r)\) pairs possible is \(\binom{2n}{2}\). All in all, we can calculate \(q\)-private backups for all \(q\in[p]\) of all jobs in polynomial time.

Finally, we construct the instance of Interval Scheduling with Colors by computing all \(q\)-private backups for each \(i_j \in I\) and define the corresponding jobs with red and blue intervals. Afterwards, we prune the resulting jobs from the instance of Interval Scheduling with Colors according to the guessed value of \(\lambda\), where we consider for each job its \(q\)-private backup and the best feasible \((p-q)\)-universal backup (from the set of guessed universal backups). Then the proof of Theorem 4 is similar to the proof of Theorem 2.

5 Robust Bipartite Matching↩︎

Maximum Matching is a classical combinatorial optimization problem in which we are given an undirected graph \(G\), and the task is to find a matching in \(G\) of maximum cardinality. It is well known that one can find a maximum-cardinality matching in polynomial time even in general graphs. In stark contrast to this, we show that the robust counterpart of Maximum Matching becomes intractable even when we restrict ourselves to bipartite graphs. In this section, we consider the problem Robust Bipartite Matching(RBM), which is the problem 2 where \(\mathcal{F}\) consists of all matchings in an underlying bipartite graph. We study the decision version of this problem. Note that the problem of finding a maximum-cardinality matching in a bipartite graph is a classical example for Matroid Intersection, i.e., the problem to find a maximum-cardinality set which is independent in two matroids on the same ground set \(E\). Hence, the following result illustrates a drastic increase in the complexity when considering the intersection of two matroids instead of a single matroid. Below we give a definition of the Unweighted Robust Bipartite Matching problem.

|@ l@ X l
Given: & An undirected bipartite graph \(G = (V, E)\) and a positive integer \(k\).
Task: & Is there a matching \(M\) in \(G\) such that for each \(f\in E\) there exists an edge \(e\in E-f\) for which \(M-f+e\) is a matching of cardinality at least \(k\)?

Before we proceed, we make a general statement on Robust maximum-cardinality problems. Consider the unweighted version of problem 2 , where the task is to find a set \(S \in \mathcal{F}\) which maximizes \(|S - f+ e|\) after the interdiction of \(f\in E\) and the possible recourse of element \(e\in E - f\). Note that \(|S-f+e| \geq |S|-1\). Thus, it suffices to restrict our search of \(S\) to the maximum cardinality sets in \(\mathcal{F}\). Moreover, it suffices to consider \(f\in S\). We call a solution \(S \in \mathcal{F}\) of the nominal problem repairable, if for each \(f\in S\) there exists an element \(e\in E \setminus S\) such that \(S-f+e\in \mathcal{F}\).

Observation 5. For the robust counterpart 2 of a combinatorial problem \(\Pi\) with unit weights, there is a maximum-cardinality solution \(S\) to \(\Pi\) that is optimal for 2 . Furthermore, if there is a maximum-cardinality solution \(S\) of \(\Pi\) that is repairable, then \(S\) is optimal.

We are now ready to state and prove the main result of this section.

theoremmatching Unweighted Robust Bipartite Matching problem is -complete.

Proof. Clearly, the Unweighted Robust Bipartite Matching problem is in , because for any given matching \(M\), one can enumerate for each possible deletion of edge \(f\in E\) the recourse \(e\in E-f\), and verify whether \(|M-f+e| \geq k\).

If we set \(k\) to be the size of a maximum-cardinality matching, then by Observation 5, we need to essentially find a repairable matching in the graph. Thus, it suffices to show that deciding whether there exists a repairable matching of maximum cardinality is -hard. We refer to this problem as Repairable Bipartite Matching(RepBM) and give a reduction from -SAT: given a set of Boolean variables \(X=\{x_1, x_2, \dots, x_n\}\) and a formula \(\varphi\) in conjunctive normal form, where each clause has \(3\) variables, does there exist a truth assignment that satisfies \(\varphi\)?

Let \(I\) be an instance of -SATwith a set \(X\) of Boolean variables and a set \(Y=\{C_1, C_2, \dots C_m\}\) of clauses in which \(|C_i|=3\). We construct an instance \(I_\text{{\sc RepBM}}\) of the problem RepBM with input graph \(G=(V,E)\) as follows (see also Figure 4):

For each variable \(x_i\in X\) in \(I\), we add two nodes \(a_i\) and \(\bar{a}_i\) in \(V(G)\) corresponding to a positive and negative literal of \(x_i\), respectively. We set \(A \mathrel{\vcenter{:}}= \{a_1,\dots, a_n, \bar{a}_1, \dots, \bar{a}_n\}\). Moreover, we add \(b_i\) in \(V(G)\) for each \(x_i\in X\) and set \(B \mathrel{\vcenter{:}}= \{b_1, \dots, b_n \}\). Additionally, for each clause \(C_j\in Y\), we add two nodes \(c_j, z_j\) in \(V(G)\) and set \(C \mathrel{\vcenter{:}}= \{c_1, \dots, c_m \}\) and \(Z \mathrel{\vcenter{:}}= \{z_1, \dots, z_m \}\). Finally, we have \(V(G) = A \cup B \cup C \cup Z\).
Let the edge set \(E(G)\) be the union of the following set of edges.
- For all \(i\in [n]\), add \(a_ib_i, \bar{a}_ib_i\) to \(E(G)\).
- For all \(j\in [m]\), add \(c_jz_j\) to \(E(G)\).
- If \(x_i\in C_j\), then add \(a_ic_j\) to \(E(G)\) and if \(\bar{x}_i\in C_j\), then add \(\bar{a}_ic_j\) to \(E(G)\).

Note that \(G\) is bipartite as \(V(G)\) can be partitioned into two stable sets, \(A \cup Z\) and \(B \cup C\).

Figure 4: -hardness reduction from -SAT to Unweighted Robust Bipartite Matching.

Given a satisfying truth assignment \(\gamma: X\rightarrow\{0,1\}\) of \(I\), we show that the matching \(M=\{c_j z_j \mid j \in [m]\}\cup \{a_i b_i\mid \gamma(x_i)=0\}\cup \{\bar{a}_ib_i\mid \gamma(x_i)=1\}\) is a solution for \(I_\text{{\sc RepBM}}\). Notice that \(|M|=m+n\) as \(M\) leaves exactly \(n\) unsaturated vertices in \(V(G)\). The set of these \(n\) unsaturated vertices constitutes of one element from each \(\{a_i,\bar{a}_i\}\) where \(i\in [n]\). These are precisely the literals with truth value 1 assigned to them by \(\gamma\). All edges \(e\in M\) contain either some \(b_i\), \(i \in [n]\), or some \(c_j\), \(j \in [m]\), as an endpoint. Note that \(M\) is a matching in \(G\) of maximum cardinality.

To prove that \(M\) is a solution of \(I_\text{{\sc RepBM}}\), we show that for each edge \(f\in M\) there is an edge \(e\in E(G)\setminus M\) such that \(M-f+e\) is a matching. In other words, for each edge \(f\), there is an edge \(e\) connecting an unsaturated vertex in \(V(G)\) to an endpoint of \(f\). If \(f\) is incident to \(b_i\), we take as \(e\) the other edge incident to \(b_i\). If \(f\) is incident to \(c_j\), then there is an unsaturated vertex \(a_i\) such that \(a_ic_j\in E(G)\setminus M\), or an unsaturated vertex \(\bar{a}_i\) such that \(\bar{a}_ic_j \in E(G)\setminus M\). This is because \(M\) is derived from the satisfying truth assignment \(\gamma\) of \(I\), and clause \(C_j\) contains some literal \(x_i\) or \(\bar{x}_i\) with truth assignment \(1\).

Next, we show that if \(I_\text{{\sc RepBM}}\) is a yes-instance of RepBM, then \(I\) also is a yes-instance of -SAT. If \(I_\text{{\sc RepBM}}\) is a yes-instance of RepBM, then there is a matching \(M'\) of size \(m+n\) in which each \(f\in M'\) has an edge \(e\in E(G)\setminus M'\) such that \(M'-f+e\) is a matching.

First, we claim that we can assume without loss of generality that \(M'\) contains all edges in \(\{ c_j z_j \mid j \in [m] \}\). Assume this is not true. Then, since \(M'\) has to have size \(m+n\), there must exist some edge \(a_i c_j \in M'\) or some edge \(\bar{a}_i c_j \in M'\). Without loss of generality, assume we are in the former case. Then we claim that \(M'' = M' + c_j z_j - a_i c_j\) is also a repairable matching of cardinality \(m+n\). Clearly, \(M''\) is a matching of cardinality \(m+n\). Hence, it remains to show that for each \(f\in M''\) there exists some \(e\in E \setminus M''\) such that \(M'' - f+ e\) is also a matching. First, consider some \(f\in M'' \setminus \{ c_j z_j \}\). In that case, set \(e\) to be some edge such that \(M' - f+ e\) is a matching (which exists since \(M'\) is repairable). Observe that \(e\) cannot be incident to \(c_j\) (since \(a_i c_j \in M'\)) and also not incident to \(z_j\) (since \(z_j\) has degree 1). Hence, \(M'' - f+ e\) is a matching. Second, consider the case \(f= c_j z_j\). Now choose \(e= a_i c_j\). In this case, clearly, \(M'' - f+ e\) is a matching since \(M'' - f+ e= M'\). By applying this procedure iteratively to all edges \(a_i c_j \in M'\), we obtain the desired result.

Observe that all edges in \(M'\) are either of the form \(c_j z_j\) for some \(j \in [m]\), or of the form \(a_i b_i\) or \(\bar{a}_i b_i\) for some \(i \in [n]\). Hence, since \(M'\) has cardinality exactly \(m+n\), either \(a_i\) or \(\bar{a}_i\), \(i \in [n]\) is saturated by \(M'\). Let \(U\subseteq A\) be the set of vertices in \(A\) that are not saturated by \(M'\). Let \(\gamma: X\rightarrow \{0,1\}\) where \(\gamma(x_i)=1\) if \(a_i\in U\), and \(\gamma(x_i)=0\) if \(\bar{a}_i\in U\). We claim that this assignment satisfies the formula \(\varphi\).

For the sake of contradiction, assume that \(\gamma\) does not satisfy \(\varphi\). Then there is a clause \(C_j\) for which all three literals in \(C_j\) evaluate to 0. Now consider the corresponding vertices in the graph \(G\); the literals evaluate to 0 because the corresponding vertices are matched to \(b_i\) in matching \(M'\). This implies there is no \(e\in E(G)\setminus M'\) which replaces the edge \(c_jz_j \in M'\). However, this contradicts the fact that \(M'\) is a solution to \(I_\text{{\sc RepBM}}\). ◻

6 Robust Stable Set in Bipartite Graphs↩︎

This section is devoted to the Robust Stable Set(RSS) problem, which is the problem 2 where the feasibility set \(\mathcal{F}\) is the set of all stable sets, commonly also known as independent sets, of the input graph. In the following we consider bipartite graphs and show that the Unweighted Robust Stable Set problem admits an efficient algorithm in bipartite graphs. This result extends to König-Egerváry graphs which generalize bipartite graphs; they are graphs in which the size of a minimum vertex cover equals the size of a maximum matching [49]. Finally, we show that the weighted problem is -hard even in bipartite graphs.

Theorem 6. Unweighted Robust Stable Set is polynomial-time solvable in bipartite graphs.

By Observation 5, it suffices to show that we can find in polynomial time a repairable maximum-cardinality stable set in bipartite graphs if it exists, or declare that none exist. Hence, Theorem 6 follows directly from the following lemma.

Lemma 4. A bipartite graph \(G\) contains a repairable maximum-cardinality stable set if and only if the underlying graph admits a perfect matching such that each edge in the matching has a degree-one endpoint.

Note that in order to check whether a graph admits a perfect matching such that each edge in the matching has a degree-one endpoint, it suffices to compute a maximum-cardinality matching \(M\), and check whether \(M\) is perfect, and whether each edge of \(M\) has at least one endpoint of degree \(1\).

Proof. Let \(G\) admit a maximum stable set \(S\subseteq V(G)\) which is repairable. Then by definition, for all \(v\in S\), there is a vertex \(w\in V\setminus S\) such that \(S-v+w\) is also a stable set. Note that, if \(w\notin N(v)\), where \(N(v) \mathrel{\vcenter{:}}= \{ w \in V \mid \{v, w \} \in E \}\) is the set of neighbors of \(v\), then \(S+w\) is a stable set in contradiction to the fact that \(S\) is a stable set of maximum cardinality in \(G\). Hence for all \(v\in S\), there is a vertex \(w\in N(v)\) such that \(S-v+w\) is a stable set. We call \(w\) the backup vertex of \(v\). Note that \(N(w) \cap S = \{ v \}\). This implies that in a repairable stable set \(S\), each vertex \(v\in S\) has a distinct backup vertex \(w\). Hence, there should be at least \(|S|\) many backup vertices in the graph (one for each \(v \in S\)), and since the backup vertices do not belong to the stable set \(S\), we have \(|S|\leq \frac{n}{2}\). As the size of a maximum stable set in a bipartite graph is at least \(\frac{n}{2}\), we have \(|S|=\frac{n}{2}\). Therefore, \(G\) contains a perfect matching \(M = \{vw\in E\mid v\in S, w \text{ is a backup of } v\}\). Now consider vertex \(v\in S\) and its backup vertex \(w\in N(v)\); \(w\) is the only neighbor of \(v\), otherwise \(S\) is not a stable set or some vertex \(u\in V\setminus S\) is not a backup vertex. Thus each \(v \in S\) is degree-one.

Now let us assume that \(G\) has the desired properties. We show that there is a repairable maximum-cardinality stable set in \(G\). If the graph contains a perfect matching and every matching edge is incident to a degree one vertex, then a collection of these degree-one vertices, \(S \subseteq V(G)\), one from each edge in the perfect matching, is a solution of the instance of the problem. Observe that for each vertex \(v\in S\), the unique neighbor \(w\) of \(v\) serves as a backup vertex. ◻

Notice that the crucial properties used to prove Lemma 4 and Theorem 6 even hold for König-Egerváry graphs and thus we get the following.

Corollary 1. Unweighted Robust Stable Set is polynomial-time solvable in König-Egerváry graphs.

This is interesting in the following sense: Theorem [thm:hardness:matching] implies a hardness result for Unweighted Robust Bipartite Matching. Recall that the line graph of a graph \(G\) contains the vertex set corresponding to \(E(G)\), and there is an edge between two vertices if and only if the corresponding edges share an endpoint in \(G\). In general, a maximum stable set in the line graph of a graph \(G\) corresponds to a maximum matching in \(G\), and hence can be computed in polynomial time. However, while Theorem 6 gives a polynomial-time algorithm for Unweighted Robust Stable Set in bipartite graphs, this one-to-one correspondence and Theorem [thm:hardness:matching] imply that Unweighted Robust Stable Set is -hard in line graphs of bipartite graph.

Corollary 2. Unweighted Robust Stable Set is -hard in line graphs of bipartite graphs.

Next, we show that the complexity of Robust Stable Set in bipartite graphs changes with weights. We now consider the decision version of the Robust Stable Set problem.

|@ l@ X l
Given: & An undirected graph \(G\), a weight function \(w \colon V \to \mathbb{R}_+\), and a positive integer \(k\).
Task: & Is there a stable set \(S\) in \(G\) such that for each \(v \in V\) there exists a node \(v' \in V-v\) which gives another stable set \(S-v+v'\) such that \(w(S-v+v') \geq k\)?

theoremweightedstableset Robust Stable Set is -complete in bipartite graphs.

Proof. We prove that the above mentioned decision variant of the problem Robust Weighted Stable Setis -hard in bipartite graphs. We give a reduction from -SAT. Given an instance \(I\) of -SATwith the set of variables \(X=\{x_1, x_2, \dots, x_n\}\) and a satisfiability formula \(\varphi\) with clauses \(Y=\{C_1, C_2, \dots C_m\}\), we construct an instance \(I' = (G, w, k)\) of the Robust Weighted Stable Setproblem as follows:

For each variable \(x_i\in X\), we take vertices \(a_i, \bar{a}_i, b_i, b_i^1, b_i^2\) in \(V(G)\). For each clause \(C_j\) in \(\varphi\), we add a vertex \(c_j\) in \(V(G)\). Moreover, we add 3 representative vertices, \(c_j^1,c_j^2,c_j^3\), corresponding to each literal in \(C_j\).
The edge set \(E(G)\) consists of the following set of edges:
- For all \(i\in[n]\), \(b_ib_i^1, b_ib_i^2, b_i^1a_i, b_i^2\bar{a}_i \in E(G)\).
- For all \(j\in[m]\), \(c_jc_j^1, c_jc_j^2, c_jc_j^3 \in E(G)\).
- Connect the three vertices \(c_j^1, c_j^2, c_j^3\) to the corresponding literals in the clause, e.g.if \(C_1=(v_1\vee\bar{v}_2\vee v_4)\), then add edges \(c_1^1a_1, c_1^2\bar{a}_2, c_1^3a_4\in E(G)\).
For the weight function \(w: V(G)\rightarrow \mathbb{R}_{\geq0}\), consider \(1 \ll r \ll s\), \(r,s\in \mathbb{R}_{\geq0}\) and set \[\begin{align} w(v) & = \begin{cases} s &\quad\text{if } v \in \{c_j\mid j\in[m]\} \cup \{b_i\mid i\in[n]\},\\ r &\quad\text{if } v \in \{c_j^1, c_j^2, c_j^3\mid j\in[m]\}\cup \{b_i^1, b_i^2\mid i\in[n]\},\\ 1 &\quad\text{if } v \in \{a_i, \bar{a}_i\mid i\in[n]\} \;. \end{cases} \end{align}\]
Set \(k=(m+n-1)s+r+n\).

Note that the constructed graph is bipartite.

First, let us assume that \(\varphi\) is a yes-instance and let \(\gamma: X \rightarrow \{0,1\}\) be the truth assignment. We claim that \(S=\{c_j\mid j\in[m]\} \cup \{b_i\mid i\in[n]\}\cup \{a_i\mid \gamma(x_i)=0\}\cup \{\bar{a}_i\mid \gamma(x_i)=1\}\) is a solution to \(I'\) of weight at least \(k\). First, observe that \(S\) is a stable set and that \(w(S) = (m+n)s+n = k + s - r\). Moreover, note that \(a_i\notin S\) if and only if \(\gamma(x_i)=1\). For all \(j\in[m]\), there exists a vertex \(c_j'\in\{c_j^1,c_j^2, c_j^3\}\) such that \(c_j'\) corresponds to a literal \(a\) for which \(\gamma(a)=1\), and hence \(a\notin S\). Thus, \(c_j'\) is only connected to \(c_j\) in \(S\). Therefore, this vertex \(c_j'\) can be a backup vertex of \(c_j\), meaning that \(S + c_j' - c_j\) is a stable set of value \(k\). Also, with a similar argument, there is a backup vertex \(b_i^1\) or \(b_i^2\) for every \(b_i\in S\). Thus, for each \(v\in S\) of weight \(w(v)=s\), there is a backup vertex \(v'\) of weight \(w(v')=r\). Consequently, for each \(v\in S\) there exists some \(v' \in V \setminus S\) such that \(w(S) + w(v') - w(v)\geq (m+n-1)s+r+n = k\), as claimed.

Next, let us assume that there is a stable set \(S\) of \(G\) such that for each \(v \in S\) there is some \(v' \in V \setminus S\) with \(w(S) + w(v') - w(v) \geq (m+n-1)s+r+n = k\). We construct a truth assignment \(\gamma\) for \(I\). Observe that \(S\) must contain all \(m+n\) vertices of weight \(s\), and none of the weight \(r\) vertices since they are all neighbors of weight \(s\) vertices. Furthermore, by the property of \(S\), for each \(c_j\) there is a vertex \(c_j'\in \{c_j^1, c_j^2, c_j^3\}\), such that the corresponding literal of \(c_j'\), say \(a\), is not in \(S\), i.e., \(S + c_j' - c_j\) is a stable set (i). Since for all \(v \in S\) there exists some \(v' \in V \setminus S\) such that \(w(S) - w(v) + w(v')\geq (m+n-1)s+r+n\), the set \(S\) must contain \(n\) vertices from set \(A=\{a_1, \dots, a_n, \bar{a}_1,\dots, \bar{a}_n\}\). Furthermore, since for each \(b_i\) there is a vertex \(v'\) of value \(r\) such that \(S + v' - b_i\) is a stable set, not both \(a_i\) and \(\bar{a}_i\) are in \(S\). Hence, exactly one of \(a_i,\bar{a}_i\) belongs to \(S\) (ii). We take the set of vertices in \(A\) which are not part of \(S\) and define the assignment \(\gamma(x_i)=1\) if and only if \(a_i\notin S\). We claim that \(\gamma\) is a truth assignment. Clearly, by (ii), \(\gamma\) is an assignment; and by (i), \(\gamma\) satisfies exactly the definitions of a truth assignment. ◻

7 Conclusion and Future Research↩︎

In this paper we have introduced the model Recoverable Robust Optimization with Commitment and investigated it for various combinatorial optimization problems, settling their computational complexity. While our focus was on polynomial-time solvable problems with a downward-closed feasibility set, it would be interesting to extend the study to a broader class of problems including -hard problems. Problems whose feasibility set is not downward-closed pose the additional challenge that the deletion of some elements might destroy feasibility which needs to be repaired by the recourse action.

Furthermore, we often have restricted our considerations to problem settings, where the adversary is only allowed to delete a single element (i.e., \(k=\ell=1\)), which seems most fundamental. It would be interesting to see how the computation complexity unravels for the general setting with arbitrary valued \(k\) and \(\ell\). For \((k,\ell)\)-Robust Matroid with \(k\le \ell\), we showed that the nominal optimal solution is also optimal for the robust counterpart, and gave an example illustrating that this property does not necessarily hold for \(k>\ell\), or non-matroid structures. It still remains an open question whether or not \((k,\ell)\)-RM is polynomial-time solvable if \(k> \ell\). Similarly, even though we have efficient algorithms for \((1,p)\)-Robust Interval Scheduling for a constant value \(p\), the complexity status of \((k,\ell)\)-Robust Interval Scheduling and also the \((k,\ell)\)-Robust Stable Set remain open.

Finally, the bounded-regret problem was crucial for solving Robust Interval Scheduling. It remains open whether the bounded-regret version of other problems can be solved in polynomial time. Particularly interesting is Robust Matroid which we can solve efficiently for \(k\leq \ell\), but the complexity of the bounded-regret version is open.

Acknowledgements↩︎

We thank Ruiyang Zhang for discussions on Robust Interval Scheduling during his master’s thesis and for observing Example 1.

References↩︎

[1]

F. Hommelsheim, N. Megow, K. Muluk, and B. Peis, “Recoverable robust optimization with commitment,” Mathematical Programming, 2026, doi: https://doi.org/10.1007/s10107-026-02385-7.

[2]

P. Kouvelis and G. Yu, Robust discrete optimization and its applications. Dordrecht: Kluwer Academic Publishers, 1997.

[3]

A. Ben-Tal, L. El Ghaoui, and A. Nemirovski, Robust optimization. Princeton University Press, 2009.

[4]

C. Buchheim and J. Kurtz, “Robust combinatorial optimization under convex and discrete cost uncertainty,” EURO Journal on Computational Optimization, vol. 6, no. 3, pp. 211–238, 2018.

[5]

A. Ben-Tal, A. Goryashko, E. Guslitzer, and A. Nemirovski, “Adjustable robust solutions of uncertain linear programs,” Mathematical Programming, vol. 99, no. 2, pp. 351–376, 2004.

[6]

C. Liebchen, M. E. Lübbecke, R. H. Möhring, and S. Stiller, “The concept of recoverable robustness, linear programming recovery, and railway applications,” in Robust and online large-scale optimization, vol. 5868, Springer, 2009, pp. 1–27.

[7]

K. Dhamdhere, V. Goyal, R. Ravi, and M. Singh, “How to pay, come what may: Approximation algorithms for demand-robust covering problems,” in FOCS, 2005, pp. 367–376.

[8]

C. Büsing, “Recoverable robust shortest path problems,” Networks, vol. 59, no. 1, pp. 181–189, 2012.

[9]

M. Jackiewicz, A. Kasperski, and P. Zielinski, “Computational complexity of the recoverable robust shortest path problem with discrete recourse,” Discret. Appl. Math., vol. 370, pp. 103–110, 2025.

[10]

M. Jackiewicz, A. Kasperski, and P. Zielinski, “Recoverable robust shortest path problem under interval uncertainty representations,” Networks, vol. 85, no. 1, pp. 127–141, 2024.

[11]

M. Hradovich, A. Kasperski, and P. Zieliński, “Recoverable robust spanning tree problem under interval uncertainty representations,” Journal of Combinatorial Optimization, vol. 34, pp. 554–573, 2017.

[12]

M. Hradovich, A. Kasperski, and P. Zielinski, “The recoverable robust spanning tree problem with interval costs is polynomially solvable,” Optim. Lett., vol. 11, no. 1, pp. 17–30, 2017.

[13]

S. Lendl, B. Peis, and V. Timmermans, “Matroid bases with cardinality constraints on the intersection,” Mathematical Programming, vol. 194, no. 1, pp. 1–24, 2021.

[14]

M. C. Dourado, D. Meierling, L. D. Penso, D. Rautenbach, F. Protti, and A. R. de Almeida, “Robust recoverable perfect matchings,” Networks, vol. 66, no. 3, pp. 210–213, 2015, doi: 10.1002/net.21624.

[15]

M. Bold and M. Goerigk, “Investigating the recoverable robust single machine scheduling problem under interval uncertainty,” Discret. Appl. Math., vol. 313, pp. 99–114, 2022.

[16]

C. Büsing, S. Goderbauer, A. M. C. A. Koster, and M. Kutschka, “Formulations and algorithms for the recoverable \(\Gamma\)-robust knapsack problem,” EURO J. Comput. Optim., vol. 7, no. 1, pp. 15–45, 2019.

[17]

C. Büsing, A. M. C. A. Koster, and M. Kutschka, “Recoverable robust knapsacks: \(\Gamma\)-scenarios,” in INOC, 2011, vol. 6701, pp. 583–588.

[18]

T. Lachmann, S. Lendl, and G. J. Woeginger, “A linear time algorithm for the robust recoverable selection problem,” Discret. Appl. Math., vol. 303, pp. 94–107, 2021.

[19]

G. N. Frederickson and R. Solis-Oba, “Increasing the weight of minimum spanning trees,” Journal of Algorithms, vol. 33, no. 2, pp. 244–266, 1999.

[20]

R. Zenklusen, “An O(1)-approximation for minimum spanning tree interdiction,” in FOCS, 2015, pp. 709–728.

[21]

R. Zenklusen, B. Ries, C. Picouleau, D. De Werra, M.-C. Costa, and C. Bentz, “Blockers and transversals,” Discrete Mathematics, vol. 309, no. 13, pp. 4306–4314, 2009.

[22]

R. Zenklusen, “Matching interdiction,” Discrete Applied Mathematics, vol. 158, no. 15, pp. 1676–1690, 2010.

[23]

A. Bar-Noy, S. Khuller, and B. Schieber, The complexity of finding most vital arcs and nodes. Digital Repository at the University of Maryland, 1998.

[24]

C. Büsing, A. M. C. A. Koster, and M. Kutschka, “Recoverable robust knapsacks: The discrete scenario case,” Optim. Lett., vol. 5, no. 3, pp. 379–392, 2011.

[25]

M. Goerigk, S. Lendl, and L. Wulf, “Recoverable robust representatives selection problems with discrete budgeted uncertainty,” Eur. J. Oper. Res., vol. 303, no. 2, pp. 567–580, 2022.

[26]

A. B. Chassein and M. Goerigk, “On the recoverable robust traveling salesman problem,” Optim. Lett., vol. 10, no. 7, pp. 1479–1492, 2016.

[27]

M. Goerigk, S. Lendl, and L. Wulf, “On the recoverable traveling salesman problem,” arXiv preprint, 2021, doi: arXiv:2111.09691.

[28]

D. Fischer, T. A. Hartmann, S. Lendl, and G. J. Woeginger, “An investigation of the recoverable robust assignment problem,” in IPEC, 2021, vol. 214, pp. 19:1–19:14.

[29]

T. Ito, N. Kakimura, N. Kamiyama, Y. Kobayashi, and Y. Okamoto, “A parameterized view to the robust recoverable base problem of matroids under structural uncertainty,” Operations Research Letters, vol. 50, no. 3, pp. 370–375, 2022.

[30]

D. Bertsimas and V. Goyal, “On the power of robust solutions in two-stage stochastic and adaptive optimization problems,” Math. Oper. Res., vol. 35, no. 2, pp. 284–305, 2010.

[31]

J. Zhen, D. den Hertog, and M. Sim, “Adjustable robust optimization via Fourier-Motzkin elimination,” Oper. Res., vol. 66, no. 4, pp. 1086–1100, 2018.

[32]

O. E. Housni, A. Foussoul, and V. Goyal, “LP-based approximations for disjoint bilinear and two-stage adjustable robust optimization,” Mathematical Programming, vol. 206, no. 1, pp. 239–281, 2024.

[33]

U. Feige, K. Jain, M. Mahdian, and V. Mirrokni, “Robust combinatorial optimization with exponential scenarios,” in IPCO, 2007, pp. 439–453.

[34]

R. Khandekar, G. Kortsarz, V. Mirrokni, and M. R. Salavatipour, “Two-stage robust network design with exponential scenarios,” Algorithmica, vol. 65, pp. 391–408, 2013.

[35]

A. Gupta, V. Nagarajan, and R. Ravi, “Thresholded covering algorithms for robust and max–min optimization,” Mathematical Programming, vol. 146, no. 1–2, pp. 583–615, 2014.

[36]

O. E. Housni, V. Goyal, and D. B. Shmoys, “On the power of static assignment policies for robust facility location problems,” in IPCO, 2021, vol. 12707, pp. 252–267.

[37]

O. E. Housni, V. Goyal, O. Hanguir, and C. Stein, “Matching drivers to riders: a two-stage robust approach,” in APPROX-RANDOM, 2021, vol. 207, pp. 12:1–12:22.

[38]

L. Chen, N. Megow, R. Rischke, and L. Stougie, “Stochastic and robust scheduling in the cloud,” in APPROX-RANDOM, 2015, vol. 40, pp. 175–186.

[39]

D. Adjiashvili, S. Stiller, and R. Zenklusen, “Bulk-robust combinatorial optimization,” Mathematical Programming, vol. 149, pp. 361–390, 2015.

[40]

D. Adjiashvili, F. Hommelsheim, and M. Mühlenthaler, “Flexible graph connectivity: Approximating network design problems between 1-and 2-connectivity,” Mathematical Programming, vol. 192, no. 1–2, pp. 409–441, 2022.

[41]

F. Hommelsheim, M. Mühlenthaler, and O. Schaudt, “How to secure matchings against edge failures,” SIAM Journal on Discrete Mathematics, vol. 35, no. 3, pp. 2265–2292, 2021.

[42]

C. Chekuri and R. Jain, “Approximation algorithms for network design in non-uniform fault models,” in ICALP, 2023, vol. 261, pp. 36:1–36:20.

[43]

S. C. Boyd, J. Cheriyan, A. Haddadan, and S. Ibrahimpur, “Approximation algorithms for flexible graph connectivity,” Mathematical Programming, vol. 204, no. 1, pp. 493–516, 2024.

[44]

R. A. Brualdi, “Comments on bases in dependence structures,” Bulletin of the Australian Mathematical Society, vol. 1, no. 2, pp. 161–167, 1969.

[45]

A. Schrijver, Combinatorial optimization: Polyhedra and efficiency. Springer, 2003.

[46]

J. B. Kruskal, “On the shortest spanning subtree of a graph and the traveling salesman problem,” Proceedings of the American Mathematical Society, vol. 7, no. 1, pp. 48–50, 1956.

[47]

S. Fujishige, M. X. Goemans, T. Harks, B. Peis, and R. Zenklusen, “Matroids are immune to Braess’ paradox,” Mathematics of Operations Research, vol. 42, no. 3, pp. 745–761, 2017.

[48]

A. Frank, “Some polynomial algorithms for certain graphs and hypergraphs.” Proc. 5th Br. comb. Conf., Aberdeen 1975, 211-226., 1976.

[49]

R. W. Deming, “Independence numbers of graphs-an extension of the Kőnig-Egerváry theorem,” Discrete Mathematics, vol. 27, no. 1, pp. 23–33, 1979.

University of Cologne, Cologne, Germany. hommelsheim@cs.uni-koeln.de↩︎
University of Bremen, Germany. nicole.megow@uni-bremen.de↩︎
TU Dortmund University, Germany. komal.muluk@math.tu-dortmund.de↩︎
RWTH Aachen University, Germany. peis@oms.rwth-aachen.de↩︎
This article has been published in Mathematical Programming [1]. Moreover, this work was conducted when the first and the third authors were affiliated to the University of Bremen and RWTH Aachen University, respectively.↩︎

Recoverable Robust Optimization with Commitment⁵

Abstract

1 Introduction↩︎

1.0.0.1 Recoverable Robust Optimization with Commitment.

1.0.0.2 The Adversary Problem.

1.0.0.3 Bounded-Regret Problem.

1.1 Our Contribution↩︎

1.1.0.1 Robust Matroid (RM).

1.1.0.2 Robust Stable Set in Interval Graphs (RIS).

1.1.0.3 Robust Bipartite Matching (RBM).

1.1.0.4 Robust Bipartite Stable Set (RBSS).

2 Preliminaries↩︎

3 Robust Matroid↩︎

4 Robust Stable Set in Interval Graphs↩︎

4.1 Algorithm Outline and Proof Roadmap↩︎

4.1.0.1 Defining backups.

4.2 The Algorithm for Bounded-Regret Interval Scheduling↩︎

4.3 Generalization to \((1,p)\)-Robust Interval Scheduling↩︎

4.3.0.1 Defining backups for \((1,p)\)-Robust Interval Scheduling.

5 Robust Bipartite Matching↩︎

6 Robust Stable Set in Bipartite Graphs↩︎

7 Conclusion and Future Research↩︎

Acknowledgements↩︎

References↩︎

Subjects

Updated on Academus

Recoverable Robust Optimization with Commitment5

Abstract

1 Introduction↩︎

1.0.0.1 Recoverable Robust Optimization with Commitment.

1.0.0.2 The Adversary Problem.

1.0.0.3 Bounded-Regret Problem.

1.1 Our Contribution↩︎

1.1.0.1 Robust Matroid (RM).

1.1.0.2 Robust Stable Set in Interval Graphs (RIS).

1.1.0.3 Robust Bipartite Matching (RBM).

1.1.0.4 Robust Bipartite Stable Set (RBSS).

1.2 Further Related Work↩︎

2 Preliminaries↩︎

3 Robust Matroid↩︎

4 Robust Stable Set in Interval Graphs↩︎

4.1 Algorithm Outline and Proof Roadmap↩︎

4.1.0.1 Defining backups.

4.2 The Algorithm for Bounded-Regret Interval Scheduling↩︎

4.3 Generalization to \((1,p)\)-Robust Interval Scheduling↩︎

4.3.0.1 Defining backups for \((1,p)\)-Robust Interval Scheduling.

5 Robust Bipartite Matching↩︎

6 Robust Stable Set in Bipartite Graphs↩︎

7 Conclusion and Future Research↩︎

Acknowledgements↩︎

References↩︎

Subjects

Updated on Academus

Recoverable Robust Optimization with Commitment⁵