TY - JOUR

T1 - A General Framework for Approximating Min Sum Ordering Problems

AU - Happach, Felix

AU - Hellerstein, Lisa

AU - Lidbetter, Thomas

N1 - Funding Information:
History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: This work was supported by Bundesministerium für Bildung und Forschung, the National Science Foundation [Grants IIS-1909335 and IIS-1909446], and the Alexander von Humboldt-Stiftung.
Publisher Copyright:
© 2022 INFORMS Inst.for Operations Res.and the Management Sciences. All rights reserved.

PY - 2022/5

Y1 - 2022/5

N2 - We consider a large family of problems inwhich 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.

AB - We consider a large family of problems inwhich 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.

KW - approximation algorithms

KW - Boolean function evaluation

KW - min sum set cover

KW - scheduling

KW - search theory

UR - http://www.scopus.com/inward/record.url?scp=85134434693&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85134434693&partnerID=8YFLogxK

U2 - 10.1287/ijoc.2021.1124

DO - 10.1287/ijoc.2021.1124

M3 - Article

AN - SCOPUS:85134434693

VL - 34

SP - 1437

EP - 1452

JO - INFORMS Journal on Computing

JF - INFORMS Journal on Computing

SN - 1091-9856

IS - 3

ER -