The maxinmum jump number M(n, k) over a class of n×n matrices of zerosand ones with constant row and column sum k has been investigated by Brualdi andJung in [1] where they proposed the conjectureM(2k, k + 1) = 3...The maxinmum jump number M(n, k) over a class of n×n matrices of zerosand ones with constant row and column sum k has been investigated by Brualdi andJung in [1] where they proposed the conjectureM(2k, k + 1) = 3l - 1 + [k-1/2]In this note, we give two counter-examples to this conjecture.展开更多
THE one-dimensional bin-packing problem is defined as follows: for a given list L={p<sub>1</sub>, p<sub>2</sub>,…, P<sub>n</sub>}, where 0【p<sub>i</sub>≤1 denotes the...THE one-dimensional bin-packing problem is defined as follows: for a given list L={p<sub>1</sub>, p<sub>2</sub>,…, P<sub>n</sub>}, where 0【p<sub>i</sub>≤1 denotes the item and its size as well, we are to pack all the items in-to bins, each of which has a capacity 1, and the goal is to minimize the number of bins used.The first-fit-decreasing （FFD） algorithm is a famous approximate algorithm for the bin-pack-ing problem. The FFD algorithm first sorts all the list into non-increasing order and then pro-cesses the pieces in that order by placing each item into the first bin into which it fits.展开更多
基金Supported by the Science Foundation of Hainan(10002)
文摘The maxinmum jump number M(n, k) over a class of n×n matrices of zerosand ones with constant row and column sum k has been investigated by Brualdi andJung in [1] where they proposed the conjectureM(2k, k + 1) = 3l - 1 + [k-1/2]In this note, we give two counter-examples to this conjecture.
文摘THE one-dimensional bin-packing problem is defined as follows: for a given list L={p<sub>1</sub>, p<sub>2</sub>,…, P<sub>n</sub>}, where 0【p<sub>i</sub>≤1 denotes the item and its size as well, we are to pack all the items in-to bins, each of which has a capacity 1, and the goal is to minimize the number of bins used.The first-fit-decreasing （FFD） algorithm is a famous approximate algorithm for the bin-pack-ing problem. The FFD algorithm first sorts all the list into non-increasing order and then pro-cesses the pieces in that order by placing each item into the first bin into which it fits.
