En dos artículos, publicados en 1989, Balas y Ng dan una metodología para construir facetas del politopo de recubrimiento con coeficientes en {0, 1, 2}. Siguiendo esta metodología, en el presente artículo decimos cómo se contruyen facetas de dicho politopo con coeficientes en {0, 1, 2, 3}.

The problem of minimizing the maximum edge congestion in a multicast communication network generalizes the well-known $NP$-hard multicommodity flow problem. We give the presently best theoretical approximation results as well as efficient implementations. In particular we show that for a network with $m$ edges and $k$ multicast requests, an $r(1+\epsilon )(rtextOPT+exp(1)lnm)$-approximation can be computed in $O(km{\epsilon }^{-2}lnklnm)$ time, where $\beta$ bounds the time for computing an $r$-approximate minimum Steiner tree. Moreover, we present a new fast heuristic that...

The problem of minimizing the maximum edge congestion in a multicast communication network generalizes the well-known NP-hard multicommodity flow problem. We give the presently best theoretical approximation results as well as efficient implementations. In particular we show that for a network with m edges and k multicast requests, an r(1 + ε)(rOPT + exp(1)lnm)-approximation can be computed in O(kmε-2lnklnm) time, where β bounds the time for computing an r-approximate minimum Steiner tree. Moreover,...

Fuzzy rule based termination criteria are introduced in two conventional and exact algorithms solving Knapsack Problems. As a consequence two new solution algorithms are obtained. These algorithms are heuristic ones with a high performance. The efficiency of the algorithms obtained is illustrated by solving some numerical examples.