PROBLEM LINK:
Author: Snigdha Chandan
Tester: Hiroto Sekido
Editorialist: Kevin Atienza
DIFFICULTY:
Challenge
PREREQUISITES:
Heuristics, facility location problem, simulated annealing, steiner tree
PROBLEM:
Roughly speaking, given an N\times N grid with individuals K in it and each having a number called its “interaction index”, you are to move some (maybe none, or all) individuals so that all K form a single connected component (where edge- and corner-adjacent individuals are considered adjacent). The goal is to minimize the value 1000A + 10B, where A is roughly the weighted sum of distances the individuals are moved, and B is the “average” difference between interaction indices of all adjacent clients. (The exact formula for A and B are given in the problem statement)
EXPLANATION:
This problem was inspired by the “mobile facility location problem”, which is a variant of the classical facility location problem. In the mobile facility location problem, each facility and client is assigned to a start location in a metric graph and the goal is to find a destination node for each client and facility such that every client is sent to a node which is the destination of some facility. The objective is to minimize the total distance clients and facilities travel.
In this problem (“social cluster”), we can consider all the individuals on the grid as clients and our objective is to form a connected cluster while minimizing the total travelling distance of all the clients. Here, instead of summing up the distances travelled by individual clients, we will sum up the weighted distances (the weight is the interaction index). Here we are also minimizing an additional parameter: the average difference between interaction indices of all the adjacent clients with a particular client.
It is an NP-hard problem, so it’s really difficult to come up with the exact optimal solution. Therefore we will try to approximate the optimal solution. We will discuss some of the heuristics below. Take note that we are minimizing the following score: \text{Score} = 1000A + 10B, where A and B are two parameters defined in the problem statement. Roughly speaking, A represents the cost incurred by moving individuals. The longer the distance, the higher the cost, but it’s less costlier to move individuals with higher interaction indices. On the other hand, B represents the “average” difference between interaction indices of all adjacent clients.
First of all, we can forget about B and try to focus on parameter A, i.e. we will try to construct a connected cluster of by moving some of the clients. (After all, A is (exactly) one hundred times more important than B.)
We can use “simulated annealing” approach as a heuristic in order to construct the connected component. We can also consider it as a special case of classical K-median problem.
We can also create a metric Steiner tree consisting of all the clients at maximal position as terminal nodes and all the clients at non-maximal positions as Steiner nodes. Already a very simple 2-approximation algorithm exists for computing the metric Steiner tree.
Once we are somehow successfully done with constructing the cluster, we can focus on rearranging the positions of the clients while still maintaining the connectivity of the cluster in order to minimize B as well as to minimize the overall score.
We have to handle this situation very carefully as some arrangement may minimize B but may result in increasing A.
There are a lot of approaches for this problem, and some are more effective than others. Feel free to discuss your approaches below 