Bipartite Complete Matching Vertex Interdiction Problem: Application to Robust Nurse Assignment

Abstract : In this paper, we consider the Robust Nurse Assignment Problem. This consists in finding the maximum number of absences of qualified nurses still permitting an optimal treatment of patients, leading us to the notion of critical jobs. We introduce the Bipartite Complete Matching Vertex Interdiction Problem as the graph formulation of this problem. We show that it can be solved in polynomial time thanks to the integer polytope of an associated sub-problem. Then, we study the polytope associated with the Bipartite Complete Matching Vertex Interdiction Problem. We also extend the well-known Hall theorem to this problem.
Type de document :
Communication dans un congrès
Kacem, I and Laroche, P and Roka, Z. 2014 INTERNATIONAL CONFERENCE ON CONTROL, DECISION AND INFORMATION TECHNOLOGIES (CODIT), Nov 2014, Metz, France. pp.182-187, 2014
Liste complète des métadonnées

https://hal.univ-lorraine.fr/hal-01267623
Contributeur : Catherine Angevelle <>
Soumis le : jeudi 4 février 2016 - 16:10:07
Dernière modification le : mercredi 22 novembre 2017 - 10:56:26

Identifiants

  • HAL Id : hal-01267623, version 1

Collections

Citation

Pierre Laroche, Franc Marchetti, Sebastien Martin, Zsuzsanna Roka. Bipartite Complete Matching Vertex Interdiction Problem: Application to Robust Nurse Assignment. Kacem, I and Laroche, P and Roka, Z. 2014 INTERNATIONAL CONFERENCE ON CONTROL, DECISION AND INFORMATION TECHNOLOGIES (CODIT), Nov 2014, Metz, France. pp.182-187, 2014. 〈hal-01267623〉

Partager

Métriques

Consultations de la notice

23