2024-04-02

Minimax Path Problem

The paper Steinhaus Filtration and Stable Paths in the Mapper seeks to find the path between vertices $s$ and $t$ of the 1-skeleton with minimal maximum Steinhaus distance. This is an example of a minimax path problem.

The minimax path between $s$ and $t$ can be found by finding a path on the minimum spanning tree.

Minimum Spanning Tree

Given a graph $G=(V,E)$, a minimum spanning tree is subgraph $G^{\prime }=(V,E^{\prime })$ that connects each vertex without any cycles and minimum possible total edge weight.

One greedy algorithm (making the locally optimal choice at each stage) to compute the minimum spanning tree of a graph is Prim’s algorithm.

1: Associate each vertex v of a graph a number C[v] (cheapest cost of a connection to v) and an edge E[v] (edge providing cheapest connection). Initialize all values of C[v] to +∞ and E[v] to a special value indicating no edge.
2: Initialize a forest F and a set Q of vertices not yet included in F.
3: while Q is nonempty:
4:    Find and remove a vertex v from Q with minimum C[V]
5:    Add v to F
6:    for each edges vw where w is in Q and the weight of vw is less than C[w]:
7:      Set C[w] to the cost of edge vw
8:      Set E[w] to point to edge vw
9:    endfor
10: endwhile

Pareto Frontier

A Pareto efficient situation is one where no action or allocation available improves one individual better off without worsening another individual. The Pareto frontier is the set of Pareto efficient situations. The idea is to restrict ones attention to a set of efficient choices rather than considering all possible choices.