## 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*^{0}_{i} if –^{1} (*i*)≠ ∅, and ...