A Contextual Combinatorial Semi-Bandit Approach to Network Bottleneck Identification

Bottleneck identification is an essential task in network analysis with numerous important applications, such as traffic planning and road network management. For example, in a road network, the road segment with the highest cost is described as a path-specific bottleneck on a path between a source node and a destination node. The cost or weight can be defined according to specific criteria, such as travel time, energy consumption, etc. The aim is to find a path which minimizes the bottleneck among all paths connecting the source and destination nodes. Bottleneck identification can thus be characterized, in a given road network graph, as finding a path with the smallest maximum edge weight among the paths connecting the source node and the destination node, i.e., finding the minimax edge. By negating the edge weights, bottleneck identification can also be viewed as the widest path problem or the maximum capacity path problem [20].