Sunday, August 08, 2021

[aueilmwa] maximizing subset TSP

given a graph and a number K, select K nodes in the graph so that the the shortest path visiting those K nodes is as long as possible.  the path may go through other nodes along the way.

the traveling salesman problem (TSP) is typically formulated as visiting all the nodes in a graph.  we have introduced the additional combinatorial complexity of first selecting the subset of K nodes, making this a minimax problem.

variant: require that the path start at a given node.  variant: circuit.

inspired by Zelda BOTW: where should 900 Koroks be placed to maximize difficulty for speedrunners?  probably many extremal points, though we have not defined what an "extremal" node is in a graph.

No comments :