Minimum Spillage Sequencing
研究实时卫星信号数据处理中的最小溢出排序问题，通过最坏情况、平均情况分析和计算测试，证明该NP难问题可有效求解，并给出一个紧的上界和O(n log n)的安全启发式算法。
The minimum spillage sequencing problem, which arises in real-time satellite signal data processing, requires a set of numbers to be arranged so as to minimize the “overflow” of the partial sums above an upper bound. We subject several heuristics to worst-case analysis, average-case analysis, and computational testing. The results demonstrate that the problem, though NP-hard, can be handled effectively. One of the highlights of the analysis is a tight upper bound on the fraction of overflow when the problem is solved to optimality, together with an O(n log n) “safe” heuristic which never exceeds this bound.