【摘 要】
：
Given n items with different sizes si and profits pi, m knapsacks with different capacities cj and a restricted bipartite graph G =(S ∪ T, E), where each v
论文部分内容阅读
Given n items with different sizes si and profits pi, m knapsacks with different capacities cj and a restricted bipartite graph G =(S ∪ T, E), where each vertex ui in G presents an item i, and the two items i and j may be packed into same knapsack only if the two vertices ui and uj are adjacent in G, and for 1 ≤ k ≤ m, the profit of each knapsack bk is defined as the total profit of the items packed into the knapsack bk, we study two variants of the multiple knapsack problem with restricted bipartite graph (MKPBG) as follows: (i) the objective is to maximize the total profit of items packed in these m knapsacks (Max-Sum MKPBG, for short);(ii) the objective is to maximize the minimum value of m profits among these m knapsacks (Max-Min MKPBG, for short).
其他文献
There are two kinds of perfect t-deletion-correcting codes of length k over an alphabet of size v, those where the coordinates may be equal and those where
In this talk I report some results on the graphs with a unique perfect matching.One of them is a strengthening of Kotzigs theorem, which says that if a conn
Let Tn(d) be the set of all trees with n vertices, diameter d and perfect matchings.We will show that the Laplacian energy of any tree in Tn(d), where d =4,
Depicting the automorphism group of any graph is the worlds problem, so it is necessary to depict special graphs.The article determined the automorphism gro
Let Gσbe a weighted oriented graph with skew adjacency matrix S(Gσ).For an n × n real skew symmetric matrix S, the weighted oriented graph as-sociated to
For a graph G and two positive integers j and k, an m-L(j, k)-edge-labeling of G is an assignment on the edges to the set {0, 1, 2,..., m}, such that adjace
如果一个图存在定向满足其最大出度△+不超过最大度△的一半，则通过估计图的半边路径(semi-edge walk)的个数，得到了该图的无符号拉普拉斯谱半径的一个新上界.进而根据D.Go
Based on the generalized Schensted algorithm due to White (Adv.Math.(1983)), in this report we present a one-to-one correspondence between oscillating m-rim
An adjacent vertex distinguishing total coloring of a graph G , or avd-total coloring in short, is a proper total coloring of G such that any pair of adjace
Tutte conjectured that every 4-edge-connected graph admits a nowhere-zero 3-flow.In this paper, we show that this conjecture is true for Cayley graphs on ge