Bipartite Complete Matching Vertex Interdiction Problem: Application to Robust Nurse Assignment - Université de Lorraine Access content directly
Conference Papers Year : 2014

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.
No file

Dates and versions

hal-01267623 , version 1 (04-02-2016)

Identifiers

  • HAL Id : hal-01267623 , version 1

Cite

Pierre Laroche, Franc Marchetti, Sebastien Martin, Zsuzsanna Roka. Bipartite Complete Matching Vertex Interdiction Problem: Application to Robust Nurse Assignment. 2014 INTERNATIONAL CONFERENCE ON CONTROL, DECISION AND INFORMATION TECHNOLOGIES (CODIT), Nov 2014, Metz, France. pp.182-187. ⟨hal-01267623⟩
33 View
0 Download

Share

Gmail Facebook X LinkedIn More