Optimal unlabeled set partitioning with application to risk-based quarantine policies

Jiayi Lin, Hrayer Aprahamian and Hadi El-Amine

IISE Transactions, 2024, vol. 56, issue 2, 143-155

Abstract: 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.

Date: 2024
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://hdl.handle.net/10.1080/24725854.2023.2192250 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:uiiexx:v:56:y:2024:i:2:p:143-155

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/uiie20

DOI: 10.1080/24725854.2023.2192250

Access Statistics for this article

IISE Transactions is currently edited by Jianjun Shi

More articles in IISE Transactions from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().