Next, we show that the techniques of modular decompositions and clique separators, widely used in the literature for solving the independent set problem on special graph classes, can be applied to the knapsack problem with conflict graphs. (Proceedings of the 25th annual ACM-SIAM symposium on discrete algorithms, SODA, pp 570–581, 2014) we derive a fairly complicated FPTAS for the knapsack problem on weakly chordal conflict graphs. By modifying a recent result of Lokstanov et al. A natural way for representing these constraints is. Reversing this condition, we obtain a forcing constraint stating that at least one of the two items must be included in the knapsack. A conflict constraint states that from a certain pair of items at most one item can be contained in a feasible solution. We study the classical 0–1 knapsack problem with additional restrictions on pairs of items. One FPTAS is based on scaling and rounding of the input, while the other FPTAS is derived via the method of K-approximation sets and functions, introduced by Halman et al. One algorithm is based on approximate computing of logarithms of arc probabilities, and the other two are fully polynomial time approximation schemes (FPTASes).
We further develop approximation algorithms for the optimization versions of the studied problem. We prove that the problem of finding a path which satisfies two bounds, one for each criterion, is NP-complete, even in the acyclic case. The first is to maximize the survival probability along the entire path, which is the product of the arc probabilities, and the second is to minimize the total path length, which is the sum of the arc lengths. We evaluate the quality of a path by two independent criteria.
The first is the survival probability of moving along the arc, and the second is the length of the arc. We study a bi-criteria path problem on a directed multigraph with cycles, where each arc is associated with two parameters.
#Knapsack approximation series#
Our algorithms use multivariate FFT, power series and number-theoretic techniques, introduced by Jin and Wu (SOSA'19) and Kane (2010). We study these problems in the unbounded setting as well. Moreover, we also present a poly$(nt)$ time and $O(\log^2 (nt))$ space deterministic algorithm for the same.
0 kommentar(er)
