Analysis of Complex Networks

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 v ∈ V we need to assign a unique provider (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 g_i,v of serving client v by provider i. Theobjectiveistofind the assignment : V→ C that minimizes the function

where g_i() isthecostofusingclient i in the assignment ;it is equal to g⁰_i if –¹ (i)≠ ∅, and ...