  Network Function Virtualization (NFV) has the potential to significantly
reduce the capital and operating expenses, shorten product release cycle, and
improve service agility. In this paper, we focus on minimizing the total number
of Virtual Network Function (VNF) instances to provide a specific service
(possibly at different locations) to all the flows in a network. Certain
network security and analytics applications may allow fractional processing of
a flow at different nodes (corresponding to datacenters), giving an opportunity
for greater optimization of resources. Through a reduction from the set cover
problem, we show that this problem is NP-hard and cannot even be approximated
within a factor of (1 - o(1)) ln(m) (where m is the number of flows) unless
P=NP. Then, we design two simple greedy algorithms and prove that they achieve
an approximation ratio of (1 - o(1)) ln(m) + 2, which is asymptotically
optimal. For special cases where each node hosts multiple VNF instances (which
is typically true in practice), we also show that our greedy algorithms have a
constant approximation ratio. Further, for tree topologies we develop an
optimal greedy algorithm by exploiting the inherent topological structure.
Finally, we conduct extensive numerical experiments to evaluate the performance
of our proposed algorithms in various scenarios.
