betweenness – Optimization Online

Betweenness Central Nodes Under Uncertainty: An Absorbing Markov Chain Approach

Published: 2026/05/13

Applications - OR and Management Sciences, Applications - Science and Engineering, Robust Optimization betweenness, Data-Driven Robust Optimization, group betweenness centrality, markov chain, markov chain approximation, markov chain monte carlo, markov chain sample average approximation, stochastic network design

We propose a betweenness centrality measure and algorithms for stochastic networks, where edges can fail and weights vary across realizations, making the most central node random. Our approach models the sequence of reported central nodes as an absorbing Markov chain and measures node importance by the share of pre-absorption time spent at each node. This … Read more

Semidefinite Relaxations of Ordering Problems

Published: 2010/08/03, Updated: 2011/01/19

Philipp Hungerländer

Franz Rendl

Combinatorial Optimization betweenness, crossing minimization, linear arrangement, linear ordering, ordering problems, quadratic ordering, semidefinite programming, srflp

Ordering problems assign weights to each ordering and ask to find an ordering of maximum weight. We consider problems where the cost function is either linear or quadratic. In the first case, there is a given profit if the element u is before v in the ordering. In the second case, the profit depends on … Read more