The traveling salesman, Steiner trees, and bubbles

Be forewarned: Of course no solution here, but rather a train of thought I want to jot down…if not for your consideration, then for me to pick up later. Also, this post mentions soap film, not bubbles. But who doesn’t like bubbles? Same generally can’t be said for soap film.

The Traveling Salesmen Problem is a hard problem. In fact, it’s NP-hard. Here’s a description (thanks, Wikipedia!):

The Traveling Salesman Problem describes a salesman who must travel between N cities. The order in which he does so is something he does not care about, as long as he visits each one during his trip, and finishes where he was at first. Each city is connected to other close by cities, or nodes, by airplanes, or by road or railway. Each of those links between the cities has one or more weights (or the cost) attached. The cost describes how “difficult” it is to traverse this edge on the graph, and may be given, for example, by the cost of an airplane ticket or train ticket, or perhaps by the length of the edge, or time required to complete the traversal. The salesman wants to keep both the travel costs, as well as the distance he travels as low as possible.

The salesmen needs to find a single loop to hit every city, and our objective is to find the least cost to make that loop. Let’s assume that cost is the distance: the salesman wants to get home as fast as possible.

OK, put that on ice for a moment and switch gears.

Another problem that also involves graphs is the Steiner Tree Problem, which is a little different. While you can still consider many cities as with the above problem, in this case we’re talking about road planning. How do you connect all the cities with the minimum distance of road pavement? In more general terms, what is the minimum length of edges that include all fixed points in the graph?

I was first introduced to Steiner Trees via this wonderful video by the good folks at Numberphile:

What astounded me is that we can “use nature” by exploiting an inherent property: get to the lowest energy state possible. Whether its water rolling down a hill to find bottom, or lightening finding the optimum path to reach ground, nature generally looks for the easiest path to get to the lowest possible energy state. In this particular scenario, the soap film expends as little energy as possible to maintain itself. The area of the film for a segment varies with the total length between the pegs. Nature wants to minimize its film area, so in doing so it also finds the minimum length solution for us. (The end of the video showed a local minimum, which by adding some energy, yielded the global minimum. Clever!)

The ultimate supercomputer

No calculations, no algorithms, no processing. Intrinsically, nature behaves like an infinitely-scaled parallel processor, evaluating all possible paths simultaneously in an attempt to find the lowest possible energy state that maintains itself. In my mind, this behavior is analogous to quantum computers where all states are evaluated simultaneously (for the purists, greatly simplified).

Via this exercise in the physical world, nature solved a mathematical problem by finding the shortest distance between a set of points. Can nature also similarly identify the shortest loop through a set of points for our friend, the traveling salesman?

Comparing the problems

The Traveling Salesman problem has the following properties (where I equate the edge cost to the distance between cities):

  1. Requirement to create a loop (in contrast to Steiner Trees, which have no such requirement), and therefore a traversal order is implied.
  2. Each city has precisely two edges connected to it (where Steiner Trees have at least one).
  3. All available paths and their associated distances between cities are fixed (whereas the paths between nodes in Steiner Trees are undefined from the start, and the paths with associated distances are solved for).
  4. The number of cities cannot be changed (whereas Steiner Trees can increase the number of nodes by adding Steiner Points if it reduces the total distance).

As I see it, the primary difference is that Steiner Trees solve for the minimum total distance to connect all nodes, versus the Traveling Salesman problem must solve for the minimum loop distance by identifying a traversal order.

Another way to contrast is that Steiner Trees are unordered because a traversal order isn’t part of the solution, and the Traveling Salesmen problem is ordered because you must find the right loop through all nodes.

Naturally…

Is there a natural phenomena, similar to the soap film exercise that would provide a solution to a given Traveling Salesmen problem?

I’ve been pondering this for the past few days, and I think the problem’s complexity lies in the ordering. Unlike Steiner Trees where nature “solves” for minimum distance by finding the lowest energy at an instant, here it would need to solve for the minimum distance over every ordered permutation of nodes. That implies iterations and time dependency, which reminds us of why this is NP-hard.

If we find a natural phenomena where things are traversed in a specific order which happens to be the optimal distance, we have a chance. At the moment, nothing comes to mind.

Being a SXSWedu Mentor

I had the privilege of being a mentor at SXSWedu 2016, and it was a valuable, rewarding experience in which I cannot wait to participate again.

The nuts and bolts

On my SXSWedu mentor profile, I listed a few topics which I could competently talk about:

  • Software development: Web, mobile, open-source, custom, CMS, LMS, etc.
  • Online community strategy
  • Agile development and product strategy

Because SXSWedu did such a great job of collecting a roster of exceptional mentors, I wondered if anyone would sign up to meet with me. So a few days before the conference, I wrote a SXSWedu staff member to inquire, and to my surprise a few people signed up to meet! I emailed them individually to say hello, and ask what they wanted to talk about so I could do some pre-thinking. A couple responded, which later made our short conversations that much more focused.

SXSWedu assigned me to a one hour time slot on Monday beginning at 5:00 PM. When I arrived (30 minutes early, as requested), I sat at a two-seat rounder table. When the first person arrived, a SXSWedu volunteer brought him to my table for our 10 minute chat (which flew by!) To keep everything on schedule, a volunteer indicated when we had 2 minutes left, and when we finished she brought out the next person waiting. Rinse and repeat for the next hour.

In retrospect

The conversations I had with each person were quick, but genuine. Every person asked a question related to the topics listed on my profile, so nothing hit me out of left field. In retrospect I truly feel I relayed at least one nugget of helpful information to every mentee. And while that alone instilled a sense of accomplishment, it turns out this experience morphed into an excellent networking opportunity. In fact, in a couple instances the other person and I decided to meet again after our 10-minute session to continue our conversation, which also led to ongoing email conversation. The mentor experience is an excellent opportunity to build relationships, and at such a large conference I love the chance to purposefully do so while helping others.

Information Theory and Projections

I am an amateur aficionado of information theory from a purely conceptual standpoint. For instance, for many years I’ve had an interest in both data encryption and data compression, which as it turns out go together like peas and carrots.

Prior to plaintext data being encrypted, applying a compression algorithm to reduce the amount of redundancy can make the ciphertext more difficult to crack by increasing the unicity distance. Early on, an easy way to remove redundancy was to remove vowels from the plaintext prior to encryption. The plaintext was still readable and its meaning was conveyed, and therefore no information was lost. In other words, the vowels were redundant, and removing redundancy strengthened the encryption.

Periodically on Reddit I stumble upon stunning art pieces that the community found interesting enough to vote up. Tonight one of them was a collection of shadow art. Clearly the artists are wonderfully talented, and yet I cannot help but see beyond the art itself to be intrigued by the underlying mechanism in which the original message (plaintext) was hidden and revealed.

Every piece appears to be random bends in wire, trash haphazardly clumped together, or blocks or boxes strewn about. At first glance we would attempt to visually decode – to discover the pattern within those objects and comprehend the artist’s message. In fact, we might lead ourselves down an entirely different path of interpretation (e.g. assuming the heaped trash is conveying a statement about our society). However, only until a source of light illuminates the piece from precisely the correct X,Y,Z coordinate do we discover the plaintext is deciphered before our eyes as a two-dimensional projection from three-dimensional space.

Redundancy helps

In many of these art pieces, there is a high degree of redundant information that actually works to strengthen the encryption. For example, in art piece where trash was heaped together, the labels and wording on the trash items obfuscate the artist’s message by leading you down a path of inspecting the trash itself.

Another art piece with letters and numbers glued to the wall might cause the viewer to try to assemble words to understand the message. In fact, if the letters actually assembled words, they could lead the viewer to conclude she successfully deciphered the message when in fact she has not.

Decoding through a dimensional projection

Arguably the ultimate redundancy is the dimensionality of the art piece. The fact that each piece is created in three dimensions entices the viewer to inspect the piece (or individual components thereof) for meaning without considering the plaintext message exists outside of the piece itself. The key that will decipher the art piece to yield the plaintext is the X,Y,Z coordinate of light source with respect to the art piece’s location.

What I find interesting is that general mechanisms of conveying secret information tend to:

  1. Encrypt the plaintext message into something generally unreadable by anyone but the intended recipient (via some key), and/or

  2. Hide the unencrypted message in plain sight, relying on surrounding noise to distract everyone but the intended recipient who understands where to find the message and meaning amongst the noise.

For shadow art, I cannot easily lump it into either category because the piece does not contain the message as plaintext nor ciphertext. Only by projecting it down a dimension with a unique key (x,y,z) can it be deciphered. It’s more closely related to an encryption, but without an algorithm required to decode. Just shine the light from the right spot, and there’s your message. It’s as if the art piece itself has the encryption and decryption algorithm built-in, so applying the key yields the message immediatly.

So what now?

Like many people, I think in analogies. I see how this art obfuscates a message that can only be revealed in a dimension below its own. I feel like there’s an analogous type of encryption that could be applied to textual messages. As I said, I’m an amateur, but I’ll continue to contemplate it.