Suppose that you are to allocate a number of automatic teller machines (ATMs) in

Question

Suppose that you are to allocate a number of automatic teller machines (ATMs) in a given region so as to satisfy a number of constraints. Households or workplaces may be clustered so that typically one ATM is assigned per cluster. The clustering, however, may be constrained by two factors: (1) obstacle objects (i.e., there are bridges, rivers, and highways that can affect ATM accessibility), and (2) additional user-specified constraints such as that each ATM should serve at least 10,000 households. How can a clustering algorithm such as k-means be modified for quality clustering under both constraints?

Explanation / Answer

K means can be modified in the following way. We can treat the regions divided by obstacle objects as different components and run Kmeans individually on each one of them

To ensure that one ATM caters to at least 10000 households we can put a check on the formed clusters if they contain more than 10000 nodes. And estabilish an ATM in that cluster only if there exist more than 10000 nodes. DBSCAN algorithm for clustering applies a similar approach to ensure a minimum number of points in a cluster.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.