0
$\begingroup$

This is a problem 1.6 from the book Algorithm Design by Kleinberg/Tardos:

There's a company that manages ships that do various tasks when in port. There're $n$ ships, $n$ ports, $m$ days in a month such that $m>n$.

At any given day there can't be two ships from the company in the same port. $(*)$

The company wants to perform maintenance on all the ships this month, via the following scheme: they want to truncate each ship’s schedule: for each ship $S_i$, there will be some day when it arrives in its scheduled port and simply remains there for the rest of the month (for maintenance). This means that $S_i$ will not visit the remaining ports on its schedule (if any) that month, but this is okay. So the truncation of $S_i$’s schedule will simply consist of its original schedule up to a certain specified day on which it is in a port $P$; the remainder of the truncated schedule simply has it remain in port $P$.

Now the company’s question to you is the following: Given the schedule for each ship, find a truncation of each so that condition $(*)$ continues to hold: no two ships are ever in the same port on the same day. Show that such a set of truncations can always be found, and give an algorithm to find them.

enter image description here

As far as I understand from the example the ship must visit at least one port before it's on maintenance (although this condition is not mentioned in the book). I also assume that each ship is supposed to visit all ports. Then because there're more days than ports and ships we could simply create an array with the all the ports and then upon each encounter of a port we'd check if it's already been visited by another ship: if not then we leave the ship for maintenance at the port; if it's already been visited then we keep going forward until we encounter a previously unvisited port.

This is solution is too simple and it's not using Gale Shapley matching algorithm which I think is expected to be used in the book.

$\endgroup$
2
$\begingroup$

we could simply create an array with the all the ports and then upon each encounter of a port we'd check if it's already been visited by another ship: if not then we leave the ship for maintenance at the port; if it's already been visited then we keep going forward until we encounter a previously unvisited port.

The following is a counterexample to your algorithm:

Ship 1: Port 1, at sea, Port 2, at sea, Port 3, at sea

Ship 2: at sea, Port 1, at sea, Port 2, at sea, Port 3

Ship 3: Port 2, at sea, Port 3, at sea, Port 1, at sea

This has the solution where Ship 1 stays at Port 3, Ship 2 stays at port 2, and Ship 3 stays at Port 1.

But your algorithm does the following:

  • Day 1:

    • Ship 1 arrives at Port 1. Port 1 hasn't been visited so it stays for maintenance.
    • Ship 3 arrives at Port 2. Port 2 hasn't been visited so it stays for maintenance.
  • Day 2:

    • Ship 2 arrives at Port 1 where Ship 1 is already staying, which isn't allowed (and you're not allowed to not have Ship 2 not arrive at Port 1 given the rules described in the end of the problem's 3rd paragraph).

If we add to your algorithm your unjustified assumption that ships can't stay for maintenance at the first port they visit, then your algorithm does the following:

  • Day 1:

    • Ship 1 arrives at Port 1. It's not allowed to stay at the first port it visits.
    • Ship 3 arrives at Port 2. It's not allowed to stay at the first port it visits.
  • Day 2:

    • Ship 2 arrives at Port 1. It's not allowed to stay at the first port it visits.
  • Day 3:

    • Ship 1 arrives at Port 2. Port 2 hasn't been matched yet so it stays there.
    • Ship 3 arrives at Port 3. Port 3 hasn't been matched yet so it stays there.
  • Day 4: Ship 2 arrives at Port 2 where Ship 1 is already staying.

As for the question of how to solve this using stable matchings, here's a hint: you're trying to find a matching between ships and ports (where they stay for maintenance), such that the following is impossible:

  • Ship A is matched to Port A
  • Ship B is matched to Port B
  • Ship A arrives at Port B before it arrives at Port A (it's not yet on maintenance when it gets to Port B)
  • Ship A arrives at Port B after Ship B does (so Ship B is already staying there for maintenance)

How can you translate that into preferences for ship-port pairs so you can apply Gale Shapley matching?

$\endgroup$
  • $\begingroup$ I could use the timetable of when ships visit ports as preference lists. $\endgroup$ – Yos Nov 1 '17 at 15:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.