We consider a large family of problems in which an ordering of a finite set must be chosen to minimize some weighted sum of costs. This family includes variations of Min Sum Set Cover  , 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 on subsets of a finite set. Assuming a polynomial time \alpha-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 \alpha-approximation algorithm for MSOP. This approximation result generalizes a proof technique used for several distinct problems in the literature. We apply our approximation result to obtain a number of new approximation results.
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 on subsets of a finite set. Assuming a polynomial time \alpha-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 \alpha-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.
R
of
(or, more precisely, a chain of subsets) of
A
(MSSC)
R
our approximation result
this