单位无穷范数下边权有界的最小支撑树逆最优值问题 |
| |
引用本文: | 张斌武,关秀翠.单位无穷范数下边权有界的最小支撑树逆最优值问题[J].运筹学学报,2022,26(3):44-56. |
| |
作者姓名: | 张斌武 关秀翠 |
| |
作者单位: | 1. 河海大学理学院, 江苏南京 2100982. 东南大学数学学院, 江苏南京 210096 |
| |
基金项目: | 国家自然科学基金(11471073) |
| |
摘 要: | 研究了单位$l_{\infty}$范数下边权有界的最小支撑树逆最优值问题。给定一个边赋权无向连通网络$G=(V, E, w)$, 支撑树$T^0$, 下界向量$\bm{l}$, 上界向量$\bm{u}$及数值$K$, 寻求一个新的边权向量$\bm{\bar{w}}$满足上下界约束$\bm{l}\le\bar{\bm w}\le {\bm u}$, 且$T^0$是在向量$\bm{\bar{w}}$下权值为$K$的一个最小支撑树, 目标是在单位$l_{\infty}$范数下使得修改成本$\|\bar{\bm w}-{\bm w}\|$最小。本文给出了该问题的数学模型, 分析了其最优性条件, 设计了求解该问题的时间复杂度为$O(|V||E|)$的强多项式时间算法。
|
关 键 词: | 最小支撑树 $l_{\infty}$ 范数 逆最优值问题 强多项式时间算法 |
收稿时间: | 2021-11-23 |
The bounded inverse optimal value problem on minimum spanning tree under unit infinity norm |
| |
Institution: | 1. College of Science, Hohai University, Nanjing 210098, Jiangsu, China2. School of Mathematics, Southeast University, Nanjing 210096, Jiangsu, China |
| |
Abstract: | We consider the bounded inverse optimal value problem on minimum spanning tree under unit $l_{\infty}$ norm. Given an edge weighted connected undirected network $G=(V, E, w)$, a spanning tree $T^0$, a lower bound vector $\bm{l}$, an upper bound vector $\bm{u}$ and a value $K$, we aim to obtain a new weight vector $\bm{\bar{w}}$ satisfying the lower and upper bounds such that $T^0$ is a minimum spanning tree under the vector $\bm{\bar{w}}$ with weight $K$. The objective is to minimize the modification cost under unit $l_{\infty}$ norm. We present a mathematical model of the problem. After analyzing optimality conditions of the problem, we develop an $O(|V||E|)$ strongly polynomial time algorithm. |
| |
Keywords: | minimum spanning tree $l_\infty$ norm inverse optimal value problem strongly polynomial time algorithm |
|
| 点击此处可从《运筹学学报》浏览原始摘要信息 |
| 点击此处可从《运筹学学报》下载免费的PDF全文 |
|