We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A General Framework for Approximating Min Sum Ordering Problems.
- Authors
Happach, Felix; Hellerstein, Lisa; Lidbetter, Thomas
- Abstract
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 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. Summary of Contribution: This paper provides a general framework for min sum ordering problems. Within the realm of theoretical computer science, these problems include min sum set cover and its generalizations, as well as problems in Boolean function evaluation. On the operations research side, they include problems in search theory and scheduling. We present and analyze a very general algorithm for these problems, unifying several previous results on various min sum ordering problems and resulting in new constant factor guarantees for others.
- Subjects
POLYNOMIAL time algorithms; BOOLEAN functions; SEARCH theory; OPERATIONS research; DYSFUNCTIONAL families; APPROXIMATION algorithms; COMPUTER science
- Publication
INFORMS Journal on Computing, 2022, Vol 34, Issue 3, p1437
- ISSN
1091-9856
- Publication type
Article
- DOI
10.1287/ijoc.2021.1124