The (online) bin packing problem with LIB constraint is stated as follows: The items arrive one by one, and must be packed into unit capacity bins, but a bigger item cannot be packed into a bin which already contains a smaller item. The number of used bins has to be minimized as usually. We show that the absolute performance bound of algorithm First Fit is not worse than 2+1/6≈2.1666 for the problem, improving the previous best upper bound 2.5. Moreover, if the item sizes do not exceed 1/d, then we improve the previous best result 2+1/d to 2+1/d(d+2), for any d≥2. (Both previously best results are due to Epstein, Nav. Res. Logist. 56(8):780–786, 2009.) Furthermore, we define a problem with the generalized LIB constraint, where some incoming items cannot be packed into the bins of some already packed items. The (in)compatibility of the incoming item with the items already packed becomes known only at the arrival of the actual item, and is given by an undirected graph (and, as usual in case of online graph problems, we can see only that part of the graph what already arrived). We show that 3 is an upper bound for this general problem if some natural transitivity constraint is satisfied. 相似文献
Qualifying the official minimum of “Two no worries and three guarantees” (certainty of food and clothing, guarantees of compulsory education, basic medical care, and housing) is essential to evaluate the targeted poverty alleviation program since 2013 in China. Using the poverty monitoring dataset and the multidimensional poverty indicator system, the uneven dynamics and regional disparity of multidimensional poverty and its driving factors in poverty-stricken areas in China during 2014–2018 are explored in this paper. The incidence rate of multidimensional poverty was reduced by 61.72%, and the poverty reduction rate within the six dimensions ranged from 52.29 to 76.36%. Multidimensional poverty and its six dimensions displayed narrowing regional disparity. Impoverished and moderately poor areas shrank, whereas low-poverty areas expanded. All 22 provinces have become low-poverty areas in 2018. The contribution of each dimension to multidimensional poverty varies for different types at different stages. Income and expenditure contribute the most to poverty status, followed by transportation, housing conditions, education, communication, and medical care and health. The contribution of each indicator among different dimensions varied with different trends from 2014 to2018. This paper helps incorporate the official minimums of “Two no worries and three guarantees” into a more operational evaluation system to promote sustainable policies for governments at all levels by 2020 and beyond, as well as provide valuable references for poverty alleviation in other developing countries worldwide.