We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
MINIMUM SPILLAGE SEQUENCING.
- Authors
Tovey, Craig A.; Weiss, Gideon; Wilson, James R.
- Abstract
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.
- Subjects
MATHEMATICAL sequences; HEURISTIC; OPERATIONS research; MANAGEMENT science; MATHEMATICAL programming; HEURISTIC programming; INTEGER programming; ALGORITHMS; MATHEMATICAL optimization
- Publication
Management Science, 1988, Vol 34, Issue 3, p306
- ISSN
0025-1909
- Publication type
Article
- DOI
10.1287/mnsc.34.3.306