Locating Restricted Facilities on Binary Maps

Abstract

In this paper we consider several facility location problems with applications to cost and social welfare optimization, when the area map is encoded as a binary (0,1) mxn matrix. We present algorithmic solutions for all the problems. Some cases are too particular to be used in practical situations, but they are at least a starting point for more generic solutions.

The algorithmic techniques presented in this paper were used by the first author in the implementation of solutions to various algorithmic contest tasks (see the attached zip archive for some examples)