As part of Analysis of Algorithms assignment Fun with Graph Algorithms my professor gave below question
Cameron Miskell and Abu Kaisar Mohammad Masum are
operating two independent courier services in the lovely Metropolitan area of Melbourne,
which also includes Palm Bay, Titusville, and Viera. Over time they have found that their
customers have become scattered throughout the city, and are complaining about longer
delivery times to deliver their packages. Cameron and Abu Kaiser therefore decide that the
best thing to do is not to compete with each other, but to form a cartel. They have shared
their customer information with each other, and would like to split the entire set of customers
into two. There are n total customers, and ti, j is the time it takes to travel from customer i to j.
You may assume that this matrix is complete, and there is a time of travel between
every pair of customers. Cameron and Abu Kaiser would like to split the customers into
two disjoint sets A and B
( so every customer is in either set A or B,but not both) such
that the longest time l to travel between any pair of customers within their respective sets is
minimized. Please design an algorithm to compute l and the two sets of customers A and B
given the ti,j ’s
( between all customers i and j)1 as input.