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.展开更多
In this paper, we consider a network communication delay improvement problem,which is to upgrade nodes in a network with minimum cost such that the communication delay betweenany two nodes of the network is below a pr...In this paper, we consider a network communication delay improvement problem,which is to upgrade nodes in a network with minimum cost such that the communication delay betweenany two nodes of the network is below a pre-specific level. In the upgrading model, the improvementby upgrading one node is a continuous variable, and the cost incurred by such an upgrading is alinear function of the improvement. We show that achieving an approximation ratio βln(|V|) for theproblem is NP-hard for some constant β > 0 even if the underlying network is a bipartite graph. Butif the underlying network is restricted as a tree, we show that it can be solved in a stronglypolynomial time.展开更多
文摘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.
基金This research is supported by National Key Researchand Development Programof China(No.2002CB312004)and the National Outstanding Youth Fund.
文摘In this paper, we consider a network communication delay improvement problem,which is to upgrade nodes in a network with minimum cost such that the communication delay betweenany two nodes of the network is below a pre-specific level. In the upgrading model, the improvementby upgrading one node is a continuous variable, and the cost incurred by such an upgrading is alinear function of the improvement. We show that achieving an approximation ratio βln(|V|) for theproblem is NP-hard for some constant β > 0 even if the underlying network is a bipartite graph. Butif the underlying network is restricted as a tree, we show that it can be solved in a stronglypolynomial time.
