1
$\begingroup$

I'm working on Algorithm Design (Kleinberg-Tardos) Chapter 1 exercise 7:

Some of your friends are working for CluNet, a builder of large communication networks, and they are looking at algorithms for switching in a particular type of input/output crossbar. Here is the setup. There are n input wires and n output wires, each directed from a source to a terminus. Each input wire meets each output wire in exactly one distinct point, at a special piece of hardware called a junction box. Points on the wire are naturally ordered in the direction from source to terminus; for two distinct points x and y on the same wire, we say that x is upstream from y if x is closer to the source than y, and otherwise we say x is downstream from y. The order in which one input wire meets the output wires is not necessarily the same as the order in which another input wire meets the output wires. (And similarly for the orders in which output wires meet input wires.) Figure 1.8 gives an example of such a collection of input and output wires. Now, here’s the switching component of this situation. Each input wire is carrying a distinct data stream, and this data stream must be switched onto one of the output wires. If the stream of Input i is switched onto Output j, at junction box B, then this stream passes through all junction boxes upstream from B on Input i, then through B, then through all junction boxes downstream from B on Output j. It does not matter which input data stream gets switched onto which output wire, but each input data stream must be switched onto a different output wire. Furthermore—and this is the tricky constraint—no two data streams can pass through the same junction box following the switching operation. Finally, here’s the problem. Show that for any specified pattern in which the input wires and output wires meet each other (each pair meeting exactly once), a valid switching of the data streams can always be found—one in which each input data stream is switched onto a different output, and no two of the resulting streams pass through the same junction box. Additionally, give an algorithm to find such a valid switching.

figure 1.8

This is the algorithm I've came up with so far:

  1. Input wires prefer output wires in the order the signal meets each output wire from source to terminus.
  2. Output wires prefer the source input wires of downstream junctions to source input wires of upstream junctions.
  3. Let M be the matchings after applying the G-S algorithm using the input wires, output wires, and associated preferences
  4. Return the set M of input-to-output wire matchings

I'm having trouble proofing or disproving this algorithm correctly solves the problem. My goal is to show that if 2 data streams meet at the same junction then it leads to an instability in the matchings. I started by assuming the data streams meet on some arbitrary output wire and a downstream junction exists, but I haven't made any progress past that in showing an instability. The 2 source input wires will prefer this arbitrary output wire over their terminus wire, but there is always a place on this arbirary wire to place a junction such that the arbirary output wire prefers it over the other two junctions - then no instability can exist.

$\endgroup$

1 Answer 1

3
$\begingroup$

Your algorithm is clean and correct.

Here is an easy proof.

Let $\text{junction}(x,y)$ stand for the junction between input $x$ and output wire $y$. Let $\text{stream}(x,y)$ stand for the stream from input wire $x$ to output wire $y$, which must be switched at $\text{junction}(x,y)$.

The book has proved the Gale-Shapley algorithm must produce a stable and perfect matching. As an application, your algorithm must produce a stable and perfect matching between the input wires and output wires.

Suppose, for the sake of contradiction, an execution of your algorithm produces a matching $M$ that includes $\text{stream}(i,o)$ and $\text{stream}(i',o')$ that meet at some junction $J$. Since $\text{stream}(i,o)$ passes $J$, $J$ is either on the same input wire or the same output wire as $\text{stream}(i,o)$. Similarly, $J$ is either on the same input wire or the same output wire as $\text{stream}(i',o')$. Since input wires are disjoint to each other, $J$ cannot be on $i$ and $i'$ both. Similar, $J$ cannot be on $o$ and $o'$ both. So, $J$ must be either $\text{junction}(i,o')$ or $\text{junction}(i',o).$

  • Suppose $J$ is $\text{junction}(i,o')$.

    • Since $\text{stream}(i,o)$ passes $J$, $J$ is upstream to $\text{junction}(i,o)$ on input wire $i$, i.e, $i$ prefers $o'$ to $o$.
    • Since $\text{stream}(i',o')$ passes $J$, $J$ is downstream to $\text{junction}(i',o')$ on output wire $o'$, i.e, $o'$ prefers $i$ to $i'$.

    So $(i, o')$ is an instability with respect to $M$.

  • Otherwise, $J$ must be $\text{junction}(i',o)$. Symmetrically, we will get that $(i', o)$ is an instability with respect to $M$.

However, $M$ is a stable matching. We have arrived at a contradiction. $\quad\checkmark$

$\endgroup$
1
  • 1
    $\begingroup$ Awesome, I arrived at pretty much the same solution but I held off posting it as an answer. $\endgroup$
    – Brady Dean
    Apr 24, 2021 at 13:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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