A General Framework for Approximating Min Sum Ordering Problems
A General Framework for Approximating Min Sum Ordering Problems
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, several scheduling and search problems, and problems in Boolean …