A General Framework for Approximating Min Sum Ordering Problems

Felix Happach, Lisa Hellerstein, Thomas Lidbetter

    Research output: Contribution to journalArticlepeer-review


    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.

    Original languageEnglish (US)
    Pages (from-to)1437-1452
    Number of pages16
    JournalINFORMS Journal on Computing
    Issue number3
    StatePublished - May 2022


    • Boolean function evaluation
    • approximation algorithms
    • min sum set cover
    • scheduling
    • search theory

    ASJC Scopus subject areas

    • Software
    • Information Systems
    • Computer Science Applications
    • Management Science and Operations Research


    Dive into the research topics of 'A General Framework for Approximating Min Sum Ordering Problems'. Together they form a unique fingerprint.

    Cite this