Triangle inequality and graphs (min cost matching graph)

Question

My question is more to do with understanding the benefits given to us by triangle inequality theorem, when it comes to any of the graph related problems, especially the ones solved by approximation algorithms. I read in number of articles that the theorem of triangle inequality makes it easier to solve an approximation problem, as compared to the problem that doesnt follow triangle inequality.

I want to understand why is that the case? What optimisations/intelligent shortcuts done by algorithms written for triangle-inequality are not allowed/available for those algorithms that dont follow triangle-inequality?

Specifically looking to understand this in the context of min-cost perfect matching problem.

Answer 1

This is really open-ended, but here are some ideas:

• Triangle equality is consistent with our intuitions about metric spaces, making optimization problems easier to visualize and reason about.
• In particular, in linear programming the triangle equality allows things like Farka's lemma and strong duality to hold (for example, this is one way to prove max flow=min cut if you formulate it as a LP).
• You can also view triangle equality as convexity of the objective function, which is desirable for optimization problems for many reasons.