带核箱覆盖问题的在线算法

经典的箱覆盖问题是组合优化中一个著名的问题，并且得到了广泛的研究．本文主要讨论带核元的箱覆盖问题的复杂性和在线条件下的算法．指出了带核的箱覆盖问题是强ＮＰ－ｈａｒｄ的．给出了在不同的在线条件下可行算法渐近比的上界，指出仅在条件三下才存在渐近比好于０的在线算法，并给出了在此条件下一个渐近比为１／２的最好的在线算法。