English

运筹学学报 ›› 2022, Vol. 26 ›› Issue (3): 44-56.doi: 10.15960/j.cnki.issn.1007-6093.2022.03.004

• • 上一篇    下一篇

单位无穷范数下边权有界的最小支撑树逆最优值问题

张斌武1,*(), 关秀翠2   

  1. 1. 河海大学理学院, 江苏南京 210098
    2. 东南大学数学学院, 江苏南京 210096
  • 收稿日期:2021-11-23 出版日期:2022-09-15 发布日期:2022-09-07
  • 通讯作者: 张斌武 E-mail:19941312@hhu.edu.cn
  • 作者简介:张斌武, E-mail: 19941312@hhu.edu.cn
  • 基金资助:
    国家自然科学基金(11471073)

The bounded inverse optimal value problem on minimum spanning tree under unit infinity norm

Binwu ZHANG1,*(), Xiucui GUAN2   

  1. 1. College of Science, Hohai University, Nanjing 210098, Jiangsu, China
    2. School of Mathematics, Southeast University, Nanjing 210096, Jiangsu, China
  • Received:2021-11-23 Online:2022-09-15 Published:2022-09-07
  • Contact: Binwu ZHANG E-mail:19941312@hhu.edu.cn

RichHTML

44

PDF

506

摘要：

研究了单位$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}$ 范数, 逆最优值问题, 强多项式时间算法

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.

Key words: minimum spanning tree, $l_\infty$ norm, inverse optimal value problem, strongly polynomial time algorithm

中图分类号: