Optimal linear separation of the safe and unsafe subspaces of sequential resource allocation systems as a set-covering problem: Algorithmic procedures and geometric insights

摘要

A recent line of work has posed the design of the maximally permissive deadlock avoidance policy for a particular class of sequential resource allocation systems as a linear classification problem. It has also identified a connection between the classifier design problem addressed by it and the classical set-covering problem that has been studied in operations research and computer science. This paper seeks to explore and formalize further this connection, in an effort to (i) develop novel insights regarding the geometric and combinatorial structure of the classifier design problem mentioned above; (ii) set an analytical base for the development of additional customized and computationally (more) efficient algorithms for its solution; and (iii) identify necessary and sufficient conditions, and the corresponding computational tests, for the effective application and the extension of the representational results in the aforementioned work to broader classes of resource allocation systems.