The Throughput of Sequential Testing
The Throughput of Sequential Testing
复制标题
顺序测试的吞吐量
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
M. Kodialam
中科院分区：
文献类型：
--
作者：
M. Kodialam
本文讨论了在顺序测试系统中确定最大可达到吞吐量的问题。系统的输入是n位二进制串。在系统中有n个测试，并且如果串受到测试j，则该测试确定该串中的位j是0还是1。测试系统的目标是检查每个传入串中的比特之和是否为零。执行每次测试所花费的平均时间和比特j为1的概率是已知的。本文的目的是确定该系统可以处理的最大输入速率。首先将确定最大吞吐量的问题表示为具有附加结构的多面体上的二次规划问题。利用多面体的特殊结构，给出了求解最大吞吐量问题的O(N2)算法。
This paper addresses the problem of determining the maximum achievable throughput in a sequential testing system. The input to the system are n bit binary strings. There are n tests in the system, and if a string is subjected to test j then the test determines if bit j in that string is zero or one. The objective of the test system is to check if the sum of the bits in each incoming string is zero or not. The mean time taken to perform each test and the probability that bit j is one are known. The objective of this paper is to determine the maximum input rate that can be processed by this system. The problem of determining the maximum throughput is first formulated as a a quadratic programming problem over a polymatroid with some additional structure. The special structure of the polymatroid polyhedron is exploited to derive an O(n2) algorithm to solve the maximum throughput problem.