AN O(n) ALGORITHM FOR THE MULTIPLE-CHOICE
AN O(n) ALGORITHM FOR THE MULTIPLE-CHOICE
复制标题
一种 O(n) 多项选择算法
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
M. Dyer
中科院分区：
文献类型：
--
作者：
M. Dyer
其中，%aq，b是给定的常量。这个问题已经被Zemel[9]、Gliver和Klingman[5]、Ibaraki等人考虑过。[6]以及辛哈和佐尔特纳[8]。它的主要应用是求解相应的整数规划，其中所有的XQ必须是零或一。茨城等人。Goverer和Klingman给出的算法运行时间为O(Nlogn)，其中n==n~是变量的总数。Zemel将这个界减少到O(nlogn.。。)式中Nmax=max~i<；_k n~。他还证明了他的算法在各种输入分布下的预期时间为O(N)。这里的目的是证明这个问题存在O(N)个最坏情况算法。在通常的常数范围内，这种方法显然是最优的。该方法与作者提出的二变量线性规划的O(N)算法密切相关
where the % aq, b are given constants. This problem has been considered by Zemel [9], Glover and Klingman [5], Ibaraki et al. [6] and Sinha and Zoltners [8]. Its principal application is to the solution of the corresponding integer program, where all xq must be zero or one. Ibaraki et al. and Glover and Klingman give algorithms which run in O(n log n) time where n = ~ = ~ n~ is the total number of variables. Zemel reduced this bound to O(n log n .. . . ) where nmax=max~i<_k n~. He also showed that his algorithm would have O(n) expected time under various input distributions. The object here is to show that an O(n) worst-case algorithm exists for this problem. Such a method is obviously optimal to within the usual constant factor. The method is closely related to an O(n) algorithm for two-variable linear-programming developed by the author