Optimal unlabeled set partitioning with application to risk-based quarantine policies
研究如何将一组物品划分为无标签子集以优化加性目标，提出一种将集合划分问题转化为多项式时间可解网络流问题的方法，并应用于COVID-19数据下的最优隔离政策，显示比传统措施在控制传播和减少经济影响方面更优。
We consider the problem of partitioning a set of items into unlabeled subsets so as to optimize an additive objective, i.e., the objective function value of a partition is equal to the sum of the contribution of each subset. Under an arbitrary objective function, this family of problems is known to be an NP-complete combinatorial optimization problem. We study this problem under a broad family of objective functions characterized by elementary symmetric polynomials, which are “building blocks” to symmetric functions. By analyzing a continuous relaxation of the problem, we identify conditions that enable the use of a reformulation technique in which the set partitioning problem is cast as a more tractable network flow problem solvable in polynomial-time. We show that a number of results from the literature arise as special cases of our proposed framework, highlighting its generality. We demonstrate the usefulness of the developed methodology through a novel and timely application of quarantining heterogeneous populations in an optimal manner. Our case study on real COVID-19 data reveals significant benefits over conventional measures in terms of both spread mitigation and economic impact, underscoring the importance of data-driven policies.