Capacitated Set Cover Problem

Abstract

We study a variant of the classical set cover problem motivated by conference scheduling, in which each item (e.g., a paper) must be covered exactly once by an eligible agent (e.g., an author) under individual capacity constraints. Formally, given a universe of items and a collection of subsets (each corresponding to items an agent can cover), the goal is to assign each item to exactly one subset, such that no subset covers more than 𝑚 m items and the total number of subsets used is minimized. We refer to this as the Capacitated Set Cover Problem with Exact Coverage. We present a formal integer linear programming formulation for the problem and discuss its relationship to known combinatorial optimization problems.

Reza Rahimi Azghan

Grad Research Associate

I am a Ph.D. student at Arizona State University. I work as a Graduate Research Associate at Embedded Machine Intelligence Lab (EMIL) under the supervision of Dr. Hassan Ghasemzadeh.