Erratum: Multitasking Capacity: Hardness Results and Improved Constructions
Noga Alon, Jonathan D. Cohen, Thomas L. Griffiths, Pasin Manurangsi, Daniel Reichman, Igor Shinkar, Tal Wagner · SIAM Journal on Discrete Mathematics · 2024
Abstract. We correct an error in the appendix of [N. Alon et al., SIAM J. Discrete Math., 34 (2020), pp. 885–903] and prove that it is NP-hard to approximate the size of a maximum induced matching of a bipartite graph within any constant factor.