12.3 Some Practical Problems Reducible to the CLC Problem

In fact, the CLC problem, while having an independent theoretical interest, is nothing but a convenient mathematical model for presenting various practical problems arising in real-life situations. A few such situations are presented below as discrete optimization problems originating from different areas of human activity.

12.3.1 The Problem of Connected Service Areas

The CLC problem may have the following interpretation. The set of vertices of graph G is the set of clients consuming some resource or service. (Some vertices may correspond to dummy clients.) To each client vV we need to assign a unique provider images(v) ∈ C from a prespecified list A(v) of admissible providers. At that, the connectivity of the service area for each provider is often required.

This problem is closely related to the optimization Plant Location Problem (PLP, or PL problem) in which, instead of a prespecified set of providers A(v), we define a cost gi,v of serving client v by provider i. Theobjectiveistofind the assignment images : VC that minimizes the function

images

where gi() isthecostofusingclient i in the assignment ;it is equal to g0i if –1 (i)≠ ∅, and ...

Get Analysis of Complex Networks now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.