Identifying Code and Set Cover Problem - 06/05/2009

Hasti Ahlehagh

This presentation summarizes the paper on the reduction between the identifying code and the set cover problem. The main goal is to provide good polynomial time approximations to the identifying code problem and address the theoretical limit of this approximation. The analysis includes an extension to the robust identifying code problem that can be shown to be equivalent to the set multicover problem.