  There are numerous applications which require the ability to take certain
actions (e.g. distribute money, medicines, people etc.) over a geographic
region. A disaster relief organization must allocate people and supplies to
parts of a region after a disaster. A public health organization must allocate
limited vaccine to people across a region. In both cases, the organization is
trying to optimize something (e.g. minimize expected number of people with a
disease). We introduce "geospatial optimization problems" (GOPs) where an
organization has limited resources and budget to take actions in a geographic
area. The actions result in one or more properties changing for one or more
locations. There are also certain constraints on the combinations of actions
that can be taken. We study two types of GOPs - goal-based and
benefit-maximizing (GBGOP and BMGOP respectively). A GBGOP ensures that certain
properties must be true at specified locations after the actions are taken
while a BMGOP optimizes a linear benefit function. We show both problems to be
NP-hard (with membership in NP for the associated decision problems).
Additionally, we prove limits on approximation for both problems. We present
integer programs for both GOPs that provide exact solutions. We also correctly
reduce the number of variables in for the GBGOP integer constraints. For BMGOP,
we present the BMGOP-Compute algorithm that runs in PTIME and provides a
reasonable approximation guarantee in most cases.
