In this note, the author proves that the inverse problem of submodular function on digraphs with l∞ objective function can be solved by strongly polynomial algorithm. The result shows that most inverse network optimi...In this note, the author proves that the inverse problem of submodular function on digraphs with l∞ objective function can be solved by strongly polynomial algorithm. The result shows that most inverse network optimization problems with l∞ objective function can be solved in the polynomial time.展开更多
For a pair of nodes s, t in an undirected graph G = (V, A) and a given level U of allowable delay, we would like to modify the network by node-based or edge-based upgrading strategies to make the delay between s and t...For a pair of nodes s, t in an undirected graph G = (V, A) and a given level U of allowable delay, we would like to modify the network by node-based or edge-based upgrading strategies to make the delay between s and t not greater than U. In this paper, we present some NP-hard results for the delay improvement problems.展开更多
文摘In this note, the author proves that the inverse problem of submodular function on digraphs with l∞ objective function can be solved by strongly polynomial algorithm. The result shows that most inverse network optimization problems with l∞ objective function can be solved in the polynomial time.
文摘For a pair of nodes s, t in an undirected graph G = (V, A) and a given level U of allowable delay, we would like to modify the network by node-based or edge-based upgrading strategies to make the delay between s and t not greater than U. In this paper, we present some NP-hard results for the delay improvement problems.
