Interview Scheduling Algo with Sub-optimal solutions

Question

I want to do something similar to Appointment scheduling algorithm (N people with N free-busy slots, constraint-satisfaction). But my additional requirement is that I should be able to give 2nd optimal solution, 3rd optimal solution and so on. Is it possible to achieve this without hitting the performance badly?

Answer 1

There isn't a lot of research (to my knowledge) into finding the solutions, in order, from the most optimal, as most of the time we just care about finding an as efficient as possible solution. So, on the assumption that a better solution might not come to light, I'll give this solution.

To find the most efficient solution, use the accepted answer in the linked question. Copied here for convenience:

Find a maximum matching in a bipartite graph (one set of vertices is the set of people and the other on the set of slots, there is an edge between a person and a slot if the person is available for this slot).

This problem can be solved with the Hopcroft-Karp algorithm.

Complexity O(n5/2) in the worst case, better if the graph is sparse.

Now, in turn, try to remove each edge of the output from the input graph and run the algorithm again.

One of these runs should give you the second-most optimal.

Now, in turn, try to remove each edge of the output from the graph that gave you the second-most optimal and run the algorithm again.

Now the third-most optimal should be among the generated sets.

Now similarly try to remove the edges of the graph of the third-most optimal.

And so on.

Complexity:

O(n5/2) in the worst case for the optimal solution.

O(n7/2) (O(n.n5/2)) in the worst case for each next solution to be generated.

Example:

Say you have edges a,b,c,d,e,f,g.

Let's say the maximum match is a,b,c.

Now you remove a from the input graph and get b,c,d,e,f,g.
Let's say the maximum match of this graph is c,d,e.

Now you remove b from the input graph and get a,c,d,e,f,g.
Let's say the maximum match of this graph is a,d,e.

Now you remove c from the input graph and get a,b,d,e,f,g.
Let's say the maximum match of this graph is a,b,g.

Now either c,d,e, a,d,e or a,b,g will be the second-most optimal (let's say it's a,b,g).

Now try to remove a, b, then g from a,b,d,e,f,g and get the maximum match of each of those 3 graph.

One of these 5 sets (the 6 generated sets excluding the second-most optimal one) should be the third optimal one.

And so on.

Proof:

I'll have to think about that a bit more...

Note:

For example, let's say we have edges a,b,c,d,e with a maximum match of a,b,c.

We remove a and get c,d,e as the maximum match.

We remove b and get c,d,e as the maximum match.

Note that these two are identical, so you shouldn't one as the second-most optimal and another as the third-most optimal.

Although you should keep both around - you need to check the graphs generated from removing c, d and e from both b,c,d,e and a,c,d,e.

Since you will need to check all the edges removed from both when c,d,e is the next-most optimal, this may negatively affect running time a bit.