单位无穷范数下边权有界的最小支撑树逆最优值问题
The bounded inverse optimal value problem on minimum spanning tree under unit infinity norm作者机构：河海大学理学院江苏南京210098 东南大学数学学院江苏南京210096
出 版 物：《运筹学学报》 (Operations Research Transactions)
年 卷 期：2022年第26卷第3期
页 面：44-56页
核心收录：
学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学]
主 题：最小支撑树 l_(∞)范数 逆最优值问题 强多项式时间算法
摘 要：研究了单位l范数下边权有界的最小支撑树逆最优值问题。给定一个边赋权无向连通网络G=(V,E,w),支撑树T^(0),下界向量l,上界向量u及数值K,寻求一个新的边权向量w满足上下界约束l≤w≤u,且T^(0)是在向量w下权值为K的一个最小支撑树,目标是在单位l范数下使得修改成本‖w-w‖最小。本文给出了该问题的数学模型,分析了其最优性条件,设计了求解该问题的时间复杂度为O(|V||E|)的强多项式时间算法。
维普期刊数据库
同方期刊数据库