A General Framework for Approximating Min Sum Ordering Problems
share
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 α-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 our approximation result to obtain a number of new approximation results.
READ FULL TEXT