论文标题
近似最小总和排序问题的一般框架
A General Framework for Approximating Min Sum Ordering Problems
论文作者
论文摘要
我们认为必须选择有限集的订购（或更确切地说是一系列子集）的大型问题，必须选择有限的集合来最大程度地减少一些加权成本。该家族包括最小总和集盖（MSSC），几个调度和搜索问题以及布尔功能评估问题的变化。我们定义了一个新问题，称为最小值排序问题（MSOP），该问题使用成本和在有限集的子集上定义的所有这些问题概括了所有这些问题。假设有多项式时间$α$α$ - approximatimation算法，即找到一个子集的重量与成本的比率最大，我们表明，在最小的假设下，有一个多项式时间$4α$ -Approximation算法MSOP的算法。这种近似结果概括了用于文献中几个不同问题的证明技术。我们将其应用于获得许多新的近似结果。
We consider a large family of problems in which an ordering (or, more precisely, a chain of subsets) of a finite set must be chosen to minimize some weighted sum of costs. This family includes variations of Min Sum Set Cover (MSSC), several scheduling and search problems, and problems in Boolean function evaluation. We define a new problem, called the Min Sum Ordering Problem (MSOP) which generalizes all these problems using a cost and a weight function defined on subsets of a finite set. Assuming a polynomial time $α$-approximation algorithm for the problem of finding a subset whose ratio of weight to cost is maximal, we show that under very minimal assumptions, there is a polynomial time $4 α$-approximation algorithm for MSOP. This approximation result generalizes a proof technique used for several distinct problems in the literature. We apply this to obtain a number of new approximation results.
