O'Reilly logo

Analysis of Complex Networks by Frank Emmert-Streib, Matthias Dehmer

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required