Gravitate Grouping Algorithm

Objective

Given an list of tuple point: [ <earliest_time>, <latest_time>, , ] Find all subsets of these points that are feasible for grouping, or furthermore, find the most optimal grouping strategy. A subset of all points are feasible for grouping (Feasible Grouping Subset) if all these conditions are satisfied pairwise:

• Haversine distance between two points is under MAX_DISTANCE (500m for now)
• There is an overlap between [ <earliest_time>, <latest_time> ] of two points

Approaches

Graph Theory (current)

Find k-clique

Pro:

• Easy to implement

Con:

• Results contain many overlapping groups
• Needs additional step to make sure that no one is grouped twice
• Needs additional step to optimize solution (eg. minimize ungrouped)

Clustering Algorithm

Use hierarchical clustering to find optimal grouping.

Complexity: O(N^3)

Pro:

• Results are optimal

Con:

• Clustering Algorithm is designed for big-N
• Small grouping size constraints may not be satisfied
• Constraints for a group to be a complete graph cannot be satisfied

Convex Optimization for k-disjoint-clique problem

Convex optimization for the planted k-disjoint-clique problem

Complexity: NP-hard

Con:

• Algorithm is NP-hard

Reduction to Graph Theory Problem

Feasible Grouping Subset is equivalent to Complete Graph (aka. clique). We want to find all cliques with size <= MAX_GROUP_SIZE. This is also known as the k-clique problem. Once we have all cliques, we need to find optimal grouping while making sure that:

• No vertex is grouped twice

Algorithm (experimental and does not satisfy all requirements):

1. Enumerate all cliques as sac
2. Iterate k = MAX_GROUP_SIZE, MAX_GROUP_SIZE - 1, ..., 2, 1

• Iterate all disjoint cliques with size == k and does not contain any node from result_set in sac
• Pop each clique as group in result set

3. return result set

Help

1. [https://cs.stackexchange.com/questions/41946/covering-a-graph-with-non-overlapping-cliques]

Implementation

Libraries:

• Clique - NetworkX