Title: Min-Max Relations for Packing and Covering
Abstract: We consider a family M of subsets of a finite set E. A “cover” is a subset of E that intersects every member of the family M. A “packing” is a set of members of M no two of which intersect. Clearly, the cardinality of a packing is at most that of a cover. We study conditions under which the maximum cardinality of a packing equals the minimum cardinality of a cover. We present recent results obtained jointly with Ahmad Abdi and Dabeen Lee.
Bio: Gerard Cornuejols is professor of Operations Research at Carnegie Mellon University. His research interests are in integer programming and combinatorial optimization. He received the Lanchester Prize twice (1978 and 2015), the Fulkerson Prize (2000), the Dantzig Prize (2009) and the von Neumann Theory Prize (2011).