WorksComputer Science
Approximation and Hardness for the Data Validation Problem
Abstract
Finnah, Gönsch and Otto [Eur. J. Oper. Res. 2025] recently introduced the Data Validation Problem (DVP): Given a transitive directed acyclic graph on vertices (resp. tasks) and edges (resp. precedences) and a probing budget, a policy can successively pay a probing fee and probe an edge in as long as the total probing fees do not exceed the budget. If a probe succeeds, the targeted edge is removed from and we receive a reward; if the probe fails, the edge stays in and cannot be probed again. We seek a policy with maximum expected cumulative reward. Crucially, must stay transitive throughout the probing process, so a policy can only challenge the precedence between consecutive tasks, that is, only probe edges in the transitive reduction of the current precedence graph. We show that DVP is strongly NP-hard and W[1]-hard with the probing budget as a parameter, even in the deterministic case (when every probe has probability or to succeed) and with unit probing costs and rewards. For the same setting, we give an approximation-preserving reduction from the Densest -Subgraph (DS) Problem, with the consequence that there is no polynomial-time -approximation algorithm and no FPT -approximation algorithm for DVP, assuming the Almost-Exponential Time Hypothesis and the Strongish Planted Clique Hypothesis, respectively. We also present the first known policies with provable worst-case guarantees for DVP, namely an -approximation algorithm for instances with uniform probabilities and probing costs, a -approximation algorithm for general instances, where is the minimum probing success probability, and an exact FPT algorithm on tournament graphs, in the deterministic setting.
Introduction
Scheduling under precedence constraints is a classic topic in theoretical computer science and operations research. In a precedence-constrained scheduling instance, a set of tasks is given together with a partial order , which is the set of precedence constraints. The partial order can also be encoded as a so-called precedence graph. Given two tasks , whenever , task must be completed before task can start. Tasks that are incomparable in the partial order may be processed in any order. The focus of the literature for scheduling with precedence constraints has considered the partial order as an input and has been primarily focused on scheduling tasks according to some objective function depending on when tasks are assigned on a time line. Many variations of precedence constraints have been studied, where the structure of the partial order can strongly affect both the computational complexity of the problem and the optimal objective value [PBM18]. A more basic question has received much less attention: how is the precedence structure obtained in the first place? In practice, the precedence constraints are rarely given explicitly with full confidence and must first be determined. This is a question that has been considered in the operations research community as the Data Validation Problem (DVP) introduced by Finnah, Gönsch and Otto [7]. However, to the best of our knowledge, the computational complexity or approximation bounds for this problem have not been studied from a theoretical perspective. In this paper, we initiate the theoretical study of the problem of determining the precedence structure of a scheduling problem. We give complexity results and approximation guarantees for this problem and several natural variants.
We formally describe DVP following the definition in [7]. We are given a probing budget and a directed acyclic graph (DAG) which is also transitive, that is, and imply . Let and . Each edge has a weight , a probing cost , and a success probability , to which is tied a random variable . We assume the random variables to be (mutually) independent.
Iteratively, an (adaptive) probing policy can probe an edge by paying , i.e., by decreasing the probing budget by . Then, we reveal the outcome of (which is unknown before the probe). If the probe succeeds, i.e., in the event that , we collect as a reward, and is removed from ; otherwise, if the probe fails, i.e., if , we collect no reward, stays in and cannot be probed anymore. Crucially, we impose that an edge can only be probed if it lies in the transitive reduction of , which is the set of all edges such that contains no (directed) --path,1 which we denote by . The transitive reduction of can be computed in time [1, 3] statically and be updated in time at each edge deletion [10]. The policy must halt if every edge in has already been probed or if for any unprobed edge . Thereby, a policy yields the expected total reward , where denotes the indicator function of an event ; the goal is to find a policy with maximum expected reward, i.e., .
We remark that we allow policies to sample random variables other than but that we are independent of . For any , we write , and .
Intuitively, the assumption of only probing edges in the transitive reduction is motivated by the interpretation of as a precedence graph. If a precedence graph contains a path , by transitivity, it also contains the edge , so removing but no edge in cancels transitivity, meaning that this framework no longer models the removal of redundant precedences in a meaningful way.
Determining the precedence constraints between tasks is a problem that is often faced in practice. The problem arises in many industries with business processes subject to hard constraints such as precedence constraints, including product design, assembly and manufacturing, project scheduling, construction, and logistics [7, 22]. In such processes, the relation between every pair of tasks is rarely documented explicitly and an expert must be consulted to determine it. Moreover, Otto and Otto [17] showed that probing direct precedence relations can increase the probability of being able to remove the edge in automotive assembly processes. Wang et al. [22] investigated the Assembly Sequence Problem, a problem similar to DVP, which is a well-studied problem in the operations research community. Finnah et al. [7] recently expanded on the model by imposing constraints on the available expert time or cost. They showed that solving the problem, even approximately, can significantly improve business outcomes. Other questions regarding the complexity or approximation guarantees remained open.
Our results
We significantly strengthen the hardness result in [7]. Via an FPT reduction from the -Clique problem, we show that DVP is strongly NP-hard and W[1]-hard, even in the deterministic setting (when all probabilities are either 0 or 1) and with unit costs and weights.
Theorem 1. DVP is strongly NP-hard and W[1]-hard when parametrized in , even if and for every edge .
We also achieve an approximation-preserving reduction to the Densest -Subgraph Problem (DkS). Thereby, using known (parametrized) inapproximability results for DkS, we achieve strong bounds for DVP as well. The bounds assume the Almost-Exponential Time Hypothesis (Almost-ETH) [13] (a slightly weaker assumption than the Exponential Time Hypothesis) and the Strongish Planted Clique Hypothesis (SPCH) [14], respectively.
Theorem 2. If there is an -approximation for DVP ( can depend on , or ), even restricted to the special case that and for every edge , there is an -approximation for DkS (with , where opt is the optimum of the DkS instance). As a consequence, even in this special case,
(1) assuming the Almost-ETH, for every there is no polynomial-time -approximation algorithm for DVP;
(2) assuming the SPCH, there is no -approximation algorithm for DVP in time for any function .
As pointed out in [7], a greedy policy that only considers the currently probable edges, e.g., that always picks as a next probe the best cost-per-value edge , performs arbitrarily badly, even for very simple instances.
In contrast, we present an adaptive policy which is an -approximation in the case of uniform costs and success probabilities and arbitrary weights and arbitrary DAGs.
Theorem 3. For any fixed , there exists an -approximation algorithm for DVP with running time in the case , for every .
We also present a more general policy for arbitrary instances of DVP with an approximation factor that depends on the budget and the minimum non-zero success probability.
Theorem 4. There exists an -approximation algorithm for DVP with running time , where .
Notice that in the deterministic case, the latter algorithm is a -approximation, which comes close to the lower bound in Theorem 2. We remark that none of the algorithms above actually requires to be transitive.
For the special case of total order, that is, if forms a (acyclic) tournament (for every either or ), or equivalently, if is a path on , in the deterministic setting, the optimal policy is computable in FPT time.
Theorem 5. If is a (acyclic) tournament, assuming and for every , the probing set with maximum weight can be computed in time .
Related work
In the Pandora’s Box problem (PBP), as in DVP, each item has an associated probing cost and a random reward. However, the objective is to maximize the expected maximum sampled reward minus the total probing cost. An optimal policy can be found in polynomial time for tree-like precedences [BFLL20, Wei79], however, it is NP-hard to approximate PBP above a factor 0.9997 for general precedences or matroid constraints.
PBP belongs to the family utility/disutility-optimization problems, for which there are generic greedy constant-factor approximation algorithms [20]. Similarly, if the objective function of a stochastic problem is adaptive submodular (the probabilistic equivalent of submodular functions), which is unfortunately not the case for DVP, there are simple greedy policies that are constant-factor approximations [9].
Another problem similar to DVP is the Stochastic Probing problem [11]. Here, as in DVP, every element to be probed has a weight and a success probability, and the goal is to maximize the expected total weight of the successively probed elements. The rule is that during the entire probing process, the set of probed and successfully probed elements, respectively, must satisfy packing constraints like Knapsack or matroid constraints, and the approximation ratio of the policy in [11] depends on the complexity of the constraints. For example, if the sets have to belong to the intersection of matroids, the approximation ratio is .
The --unreliability problem asks for the probability that a pair of vertices and become disconnected when each edge of a graph is independently removed with probability . By Proposition 10, it is the same as to ask, assuming , whether the edge can successively be probed or not, so the problem can be helpful to provide success bounds for DVP algorithms. Unfortunately, the problem is #BIS-hard [FGV24], meaning that there is most likely no (randomized) PTAS for the problem [5].
Hardness results
We construct a parametrized and approximation-preserving reduction from -Clique and DkS, respectively. Both problems are strongly NP-hard and W[1]-hard [CFK^{+}15, GJ79, LMFB24].
We recall that in DkS, the goal is, given an undirected graph , to find the induced subgraph of with vertices and with a maximum number of edges, that is, to find , where is the density of ( is the edge set of the subgraph induced by ). The -Clique problem is to check whether the optimal solution to DkS is a clique. For a positive integer , we denote . For a set , denotes its cardinality.
Let and consider an undirected graph . Let to be fixed later. We consider the DVP instance with vertex and edge sets

Figure 1. Example of a reduction from -Clique to DVP for . The green and red edges represent the optimal probes.
where edges are defined as (where is incident to ), and . All edges in have success probability and probing cost 1, the edges have weight 1, other edges in have weight 0. Notice that only the edges can yield profit. To probe , where , it is necessary and sufficient to probe or for every and every . Clearly, is a transitive DAG.
Proof of Theorem 1. Set and . We show that the construction above is a parametrized reduction (see [4] for the definition) from -Clique to DVP. More precisely, we show that the graph has a -clique if and only if , where OPT is the optimal solution (the edges in removed by an optimal policy) of the DVP instance . Let for some . Clearly, is feasible and also optimal since and .
Assume , and so . For each , let . We have
The second inequality holds because there are at most many vertices with and for every pair . All inequalities are tight, so , and we have exactly many vertices with and . Therefore, those vertices form a -clique in .
Conversely, if has a -clique , then probing the edges needs exactly probes and yields a profit , thus , and therefore as shown above.
To derive the approximation hardness of DVP, we state the currently sharpest known (parametrized) inapproximability results known for DkS.
Proposition 6. We have the following hardness results for DkS:
[13 Theorem 1]: Assuming the Almost-ETH, for any there is no polynomial-time algorithm such that, given an integer and any graph on vertices that contains at least one -clique, always output with such that
ii) [14 Theorem 2]: Assuming the SPCH, for every function and every function , there is no -time algorithm such that, given an integer and any graph on vertices that contains at least one -clique, always outputs with such that .
Proof of Theorem 2. Let be an optimal solution of the DkS instance . First, we guess the optimal number of edges 2 and set and .
Let now be the optimal solution of the DVP instance . Probing all the edges in the set needs exactly probes and yields a profit , so .
The reduction. Assume now that there is an -approximation algorithm for DVP that probes with . For every edge , we remove from and add to (unless it is already in ) at no additional probing cost. The resulting set is feasible since and we have . Let . We have . Notice that implies and therefore , so . Now take a subset of size uniformly at random. For every , we have , so and therefore in expectation. The computation of with maximum density can be derandomized in time via the method of conditional expectations, see [16].
Proof of (1). Let and assume that there is a polynomial-time algorithm that outputs, for any DVP instance (without loss of generality with , for every ), a feasible solution with , where is an optimal solution of the instance.
Consider any DkS instance with which contains a -clique , i.e., , taking large enough such that . We have . Applying the assumed algorithm on the reduction , and using the bounds above, for large enough, we get a set with
which is a contradiction to i) in Proposition 6. The last inequality follows from
Proof of (2). Consider any functions and , assume without loss of generality that is monotonic increasing. Assume there is an algorithm with running time , that outputs, for any DVP instance (without loss of generality with , for every ) a feasible solution with , where is the optimal solution of the instance .
Consider any DkS instance which contains a -clique , i.e., , taking large enough to have . Applying the assumed algorithm on the reduction , we get a set with
using the monotonicity of and the bound . We have , so assuming the SPCH, we contradict ii) in Proposition 6.
The approximation algorithm
As assumed in Section 1, the only condition for a probing policy to be valid is that at any time an edge is probed, it must lie in the transitive reduction of the remaining graph and be unprobed. We give stronger static criteria to assess whether a subset or a specific edge can be extracted by a valid policy or not.
Claim 7. For any acyclic edge set and any edge , we have .
Proof. Let and . Since there is no --path except in , there is also no --path except in , so .
We call a set obtainable if the elements of can be ordered in a way that and for every . By the following lemma, obtainability is the essential static criterion for a set to be probable.
Lemma 8. For any valid probing policy, the set of successfully probed edges is always obtainable. Conversely, for any obtainable set , assuming and for every , there is a valid probing policy that successfully probes every edge in with non-zero probability.
Proof. The first part is clear from Claim 7 since any failed probed edge is never removed from . Consider now an obtainable set with for every sorted appropriately. Consider the policy that probes the elements of in the given order and halts as soon as the next candidate is not in the transitive reduction of the remaining graph or once all elements of have been probed. Since only probes edges in and by assumption, the budget never runs out before probing all edges in . In the event , probes every element of successfully. Since the random variables are independent, we have and the claim follows.
Lemma 9. For any acyclic edge set and any set , is obtainable if and only if there is no --path in for every edge .
Proof. We argue by induction in . The case is precisely the definition of . Assume now . If is obtainable and is the last element that was added to , is obtainable by assumption and there is no --path in for any by induction. Since , there is also no --path in , so .
Assume now that there is no --path in for every . Let be the edge in such that the --path in is the longest among all edges in . Let . For any , cannot be in any --path since we could construct a --path longer than the --path, so there is no --path in , meaning that is obtainable by induction. By the same argument, , so is obtainable.
With this criterion, we can draw a similarity between obtainability and the Min-Cut problem. We recall that for any directed graph with , an edge set is an --cut if there is a vertex set such that , where denotes the set of all edges from to .
Proposition 10. Let be an acyclic edge set and let . Any obtainable set with contains a --cut and any --cut is obtainable.
Proof. Let with be obtainable. By Lemma 9, there are no --paths in . Let --path in . Clearly, is a --cut since and and .
Let be an --cut with such that . Assume that is not obtainable, meaning by Lemma 9 there is an edge and an --path with no edge in . Since , we have but . Let be the last vertex in such that the subpath of from to lies entirely in . The vertex exists since and since . Therefore the successor of in exists and , in particular , which is a contradiction.
It follows immediately from Proposition 10 that an inclusion-minimal obtainable set containing is an inclusion-minimal --cut and vice versa. In particular, computing an optimal minimum-cost obtainable set including is equivalent to computing a minimum --cut on the same graph with capacities , which is achievable in time , see [18].
For the analysis of a policy, we first need to assure that some probabilistic notions are well-defined, especially for an optimal policy. While we allow policies to sample other random variables than , we ensure that this is not necessary for optimality. For any policy and any , let refer to the event that probes and let .
Lemma 11. For every DVP instance , there exists an optimal policy that only depends on the variables and such that the events and are independent for every .
Proof. For a DVP instance , let denote a stage of a probing process where is the set of unprobed edges, of failed probed edges and the leftover budget. Let be the set of probable edges and let be the optimal expected profit. As argued in [7], is computable with the Bellman recursion if and
otherwise. Therefore, we can select to be a policy that, at every stage , picks an edge that maximizes (1), breaking ties deterministically, meaning that depends only on .
For a stage , let be the event that the policy attains the stage . By induction in the number of probes, for every stage , we have either or . In both cases, for every , and are independent. If and are two stages where picks , we have since an edge is never picked twice. Since the event is the event that such a stage is attained, and are independent.
It follows that the expected profit of any policy can be formally reformulated as .
An adaptive policy for uniform probabilities. If a DVP instance has exactly one edge with , an optimal policy for that instance is coincidentally a policy which has the highest chance of probing . By Lemma 11, we can assume that this policy only depends on . For any policy , we write and call -optimal if , i.e., if has the highest chance of probing among all feasible policies.
Intuitively, for any (globally) optimal policy , if we know the edge with highest expected profit among all edges in and we know an -optimal policy , will extract at least as much (expected) profit from as but potentially nothing from the other edges; therefore, uniformly sampling a single edge and running an -optimal policy is an -approximation (in expectation) of an optimal policy. We now derive a simple -optimal policy for any edge in a DVP instance in the case of uniform costs and probabilities.
Lemma 12. Let and let be a DVP instance with and for every . Consider an edge . A policy which, at any step, probes an edge on a minimum --cut (consisting of unprobed edges only), is -optimal, regardless of the choice of the cut and the edge.
Proof. Without loss of generality, we assume since otherwise, probing any edges (as long as any edge is probable) is trivially an optimal policy.
We again denote a stage of the probing process where is the set of unprobed edges, the set of failed probed edges and the leftover budget as , or if we omit the budget. If we probe at the stage , if the probe succeeds, we are at stage , and at otherwise. At stage , let be the size of a minimum admissible --cut. We say that an --cut is admissible if it which contains only edges in ; We set if no admissible --cut exists, i.e., if contains an --path.3
At any stage , let be in a minimum admissible --cut . is an admissible --cut at , so . However, if is an admissible --cut at , is a cut at , so . We have since any admissible --cut at is an admissible --cut at .
At , let not lie on any admissible minimum --cut. Any minimum admissible --cut (without ) at is also a minimum admissible --cut at and vice versa, so . Let be a minimum admissible --cut at the stage . Since disconnects and in , disconnects and in as well. However, since lies on no minimum admissible --cut at the stage , has no minimum cardinality at stage , so we have . Since any admissible --cut (without ) at is an admissible --cut in , we have , so we get .
Let be the success probability of an optimal policy at that stage. By Proposition 10, the algorithms succeed if we managed to disconnect and , so we have if and only if . As shown above, can only decrease by 1 at each probe, we have if . For any , let be the success probability of an optimal policy at the next stage, assuming is picked at the current stage. Therefore, . In particular, a policy is optimal if, at any stage , it probes an arbitrary edge in .
By induction in , we show that at any stage with , any edge on any minimum admissible --cut is in ; the lemma follows immediately. If , we have , and the only way to reduce is to pick the edge on the (unique) admissible single-edge --cut. Assume now .
At a stage , let be the edge chosen by an optimal policy. If belongs to a minimum admissible --cut, the claim follows directly by induction; otherwise, let be any minimum admissible --cut. Since is obtainable by Proposition 10, there exists some edge . As argued above, is a minimum admissible --cut at the stages and , so and by induction. We get
meaning . Since the choice of and was arbitrary, the proof is complete.
Proof of Theorem 3. Let be a random variable which is uniformly distributed over and independent of . We consider the policy which first samples an edge from , then runs the -optimal policy of Lemma 12. Since , and the events , and are independent for every , we get expected profit
Any sampled -optimal policy makes up to probes (since we assumed ) and updates the transitive reduction and the minimum cut at each iteration in time and respectively, yielding a total time of at most .
A policy for general instances. The first step of the algorithm is, for every , to compute a minimum-cost obtainable set with . Recall that we also assume for every since we can assign cost to any edge with since an optimal policy would never probe an edge with success probability 0.
Every edge is treated as an object with size and profit , and the goal is to pick objects with maximum profit but bounded cumulative size, like a Knapsack instance. We assign to every a cost efficiency ratio .
We order the edges in in decreasing cost efficiency ratio but exclude the edges with , thus having with for every . Let if and otherwise be the integer with . Let also be the edge with maximum profit, i.e., .
From this point on, the algorithm is greedy. We set if and otherwise. Then, we probe any probeable edge in in arbitrary order until no edge in can be probed, i.e., all unprobed edges in are not in the transitive reduction of the resulting graph. Proof of Theorem 4. Let denote the policy described above. In the case , notice that for any , in the event , is successfully probed; in particular, we have . By the same argument, we have when .
Let be an optimal (adaptive) probing policy as in Lemma 11 and let for every . We have . Since is feasible, the cumulative cost of the edges probed by is never above , i.e., . This must thus hold in expectation as well, so . Consider the linear program
For every , notice that is a feasible fractional solution with respect to the LP (2) since . Also, , so and . Together, we get .
One fractional optimum of (2) is for , and for , with sorted as above since (2) has the form of the canonical LP relaxation of the 0-1 Knapsack problem [15]. In particular, we have .
Assume now that , the other case is symmetric. By construction, for any , is probed if , so is probed and succeeds with probability at most . By the linearity of expectation, the total expected profit is
Computing for every can be achieved in time since it consists of computing a Min-Cut instance for every edge. Then, during the probing process, can be updated in time at each probe, and the choice of the probe in is arbitrary, the total running time is bounded by .
The algorithm for total orders
We give an FPT algorithm parameterized in the budget for instances that form a tournament, as defined in § 1. For simplicity, we order such that for any , we have if and only if . In this setting, the following lemma follows directly from Lemma 9.
Lemma 13. Let be obtainable. For every , we have .
Proof. By Lemma 9, for , for any , the --path cannot be in , so or . In particular, , and the claim follows.
The main observation is that for any obtainable set with , we can divide into up to disjoint blocks of consecutive vertices such that every edge in lies in exactly one of those blocks. We define the -block to be the edge set of the induced subgraph of on the vertex set .
Lemma 14. Let be obtainable with . There is a family of up to disjoint blocks such that for each block and . Furthermore, for every block , is obtainable.
Proof. Consider the graph with defined as follows: For every , we have whenever and .
Let be a connected component of of size , and let and . By Lemma 13, we have for every , so by induction. For , we have either or . In particular, if is another connected component of , we have or , so the blocks and are disjoint. For any in the connected component of , any --path on lies in meaning that contains an --path if and only if contains an --path. By Lemma 9, this means that every connected component of is obtainable. Trivially has up to connected components.
Therefore, if is the set of connected components of , we can choose as the family of blocks which satisfies the properties of the claim.
We now describe the algorithm of Theorem 5.
Proof of Theorem 5. Let refer to an optimal solution of the DVP instance restricted on the block and budget . Clearly, is an optimal solution for the entire instance. If , there are at most many candidates for since has edges and there are there are at most obtainable sets in .
We show now that for every and , can be selected via the recursion
First, notice that is always obtainable by Lemma 14. Trivially, we have since the block is empty. For , if there is no edge in , we have . Otherwise, there is a family of boxes with the properties in Lemma 14. In particular, since there is an edge in , there is one block in with . Let . By induction and maximality of ,
so all the inequalities are tight and (3) is correct. For every , , there are at most choices of the last block , and can be found by enumeration in time . Since we need to compute values of , we end up with a total running time .
References
- [1]Alfred V. Aho, Michael R Garey, and Jeffrey D. Ullman. The transitive reduction of a directed graph. SIAM Journal on Computing, 1(2):131–137, 1972.DOI
- [3]Jørgen Bang-Jensen and Gregory Z Gutin. Digraphs: theory, algorithms and applications. Springer Science & Business Media, 2008.
- [4]Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized algorithms. Springer, 2015.DOI
- [5]Martin Dyer, Leslie Ann Goldberg, Catherine Greenhill, and Mark Jerrum. The relative complexity of approximate counting problems. Algorithmica, 38(3):471–500, 2004.DOI
- [7]Benedikt Finnah, Jochen Gönsch, and Alena Otto. Overcoming poor data quality: Optimizing validation of precedence relation data. European Journal of Operational Research, 322(3):740–752, 2025.DOI
- [9]Daniel Golovin and Andreas Krause. Adaptive submodularity: Theory and applications in active learning and stochastic optimization. Journal of Artificial Intelligence Research, 42:427–486, 2011.arxiv.org/abs/1003.3967
- [10]Gramoz Goranci, Adam Karczmarz, Ali Momeni, and Nikos Parotsidis. Fully dynamic algorithms for transitive reduction. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025), pages 92:1–92:20. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2025.arxiv.org/abs/2504.18161
- [11]Anupam Gupta and Viswanath Nagarajan. A stochastic probing problem with applications. In International conference on integer programming and combinatorial optimization, pages 205–216. Springer, 2013.
- [13]Pasin Manurangsi. Almost-polynomial ratio almost-ETH-hardness of approximating densest k-subgraph. Electronic Colloquium on Computational Complexity (ECCC), TR16(195), 2026.
- [14]Pasin Manurangsi, Aviad Rubinstein, and Tselil Schramm. The strongish planted clique hypothesis and its consequences. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), pages 10–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2021.arxiv.org/abs/2011.05555
- [15]Silvano Martello and Paolo Toth. Knapsack problems: algorithms and computer implementations. John Wiley & Sons, Inc., 1990.DOI
- [16]Michael Mitzenmacher and Eli Upfal. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge University Press, 2017.
- [17]Christian Otto and Alena Otto. Multiple-source learning precedence graph concept for the automotive industry. European Journal of Operational Research, 234(1):253–265, 2014.DOI
- [18]James B Orlin. Max flows in O(nm) time, or better. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 765–774, 2013.DOI
- [20]Sahil Singla. The price of information in combinatorial optimization. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, page 2523–2532. Society for Industrial and Applied Mathematics, 2018.arxiv.org/abs/1711.00405
- [22]Lihui Wang, Shadi Keshavarzmanesh, Hsi-Yung Feng, and Ralph O Buchal. Assembly process planning and its future in collaborative manufacturing: a review. The International Journal of Advanced Manufacturing Technology, 41(1):132–144, 2009.DOI