The Minimax-regret spanning tree problem(最小最大后悔支撑树问题)

The Minimax-regret spanning tree problem(最小最大后悔支撑树问题)

本文建立了最小最大后悔支撑树问题的模型.利用划分问题，证明了该问题是NP-C的.然后利用两个已有的算法，给出了上下界估计.最后对一种特殊情况，给出了一个启发式算法，并证明了其性能比是紧的.

Bibliographic Details
Main Authors:	LIBang-yi(李帮义), YAOEn-yu(姚恩瑜)
Format:	Article
Language:	zho
Published:	Zhejiang University Press 2001-05-01
Series:	Zhejiang Daxue xuebao. Lixue ban
Subjects:	后悔值 np-c 算法
Online Access:	https://doi.org/zjup/1008-9497.2001.28.3.237-242

Similar Items

Study on the Problem of Constrained Minimum Spanning Tree(约束最小生成树问题研究)
by: CHENGuang-ting(陈光亭), et al.
Published: (1999-01-01)

Network flow problem with carrier(带运输工具的网络流问题)
by: LEITing(雷挺), et al.
Published: (2007-05-01)

The Flow Shop problem with a server(带服务器的Flow Shop问题)
by: SUChun-jie(苏纯洁), et al.
Published: (2000-07-01)

Dynamic minimum cost path problem with curfews(带有宵禁限制的动态最短费用路问题)
by: HECai-xiang(何彩香), et al.
Published: (2008-07-01)

平行光束反射式光纤位移传感器双值问题研究
by: 李丽君, et al.
Published: (2010-01-01)

Two-point boundary value problems of a class of singular fourth-order ordinary differential equations(一类奇异4阶常微分方程的两点边值问题)
by: YAOQing-liu(姚庆六)
Published: (2010-09-01)

Existence of single and multiple positive solutions of singular boundary value problem(一类奇异边值问题正解的存在性及多解性)
by: YANDongming(闫东明)
Published: (2017-05-01)

New lower bounds for the minimum eigenvalue of the Hadamard product of nonsingular M-matrices(非奇异M-矩阵Hadamard积的最小特征值的新下界)
by: ZHAOJianxing(赵建兴), et al.
Published: (2017-09-01)

Existence and multiplicity of positive solutions to nonlinear fourth-order three-point boundary value problems(非线性四阶三点边值问题的正解存在性与多解性)
by: YAOQing-liu(姚庆六)
Published: (2008-07-01)

Characteristics detection and generation of ternary sequences(三值序列的特征检测及其产生)
by: WUXun-wei(吴训威), et al.
Published: (2001-07-01)

New method of solving assignment problem—target value submatrix method(指派问题新解法——目标值子矩阵法)
by: ZHAOHong-gang(赵洪刚), et al.
Published: (2010-09-01)

Symmetric positive solutions for the second-order three-point boundary value problems(二阶三点边值问题的对称正解)
by: ZHAORuhui(赵如慧), et al.
Published: (2018-09-01)

40 Gbit/s光纤通信系统的光放和色散管理研究
by: 王会义, et al.
Published: (2014-01-01)

Nonstationary Stochastic Bandits: UCB Policies and Minimax Regret
by: Lai Wei, et al.
Published: (2024-01-01)

An extended method of fundamental solutions for inverse boundary value problems associated with one-dimensional nonhomogenous heat conduction(广义基本解方法求解一维非齐次热传导方程的反边界值问题)
by: DONGChao-feng(董超峰), et al.
Published: (2009-11-01)

Study of Real-time Multivalued Logic Control System on Binary Computer(基于二值计算机的实时多值逻辑控制系统的研究)
by: WUGui-chu(吴桂初), et al.
Published: (1999-11-01)

关于有固定工件和序约束的单机最小化最大流程排序问题的注记(A short note on the approximability of the single machine scheduling problem to minimize makespan with fixed jobs and precedence constraints)
by: YANGAi-feng(杨爱峰), et al.
Published: (2008-11-01)

The existence and uniqueness of positive eigenfunctions of some elliptic eigenvalue systems in Rn(Rn上椭圆型特征值问题正特征函数的存在性和惟一性)
by: XUERu-ying(薛儒英)
Published: (2001-01-01)

New method of simplification of ternary function with multiple outputs based on ternary K-map(基于三值K图的多输出三值函数化简的新方法)
by: ZHENGDan-dan(郑丹丹), et al.
Published: (2008-01-01)

Cubic uniform B-spline curves interpolation with normal constrains(带法向约束的3次均匀B样条曲线插值)
by: HUQiaoli(胡巧莉), et al.
Published: (2014-11-01)

Minimax regret optimisation for robust planning in uncertain Markov decision processes
by: Rigter, M, et al.
Published: (2021)

Perturbation Algorithm for a Minimax Regret Minimum Spanning Tree Problem
by: Mariusz Makuchowski
Published: (2014-01-01)

Semi-online multiprocessor scheduling with the longest given processing time(已知工件最大加工时间的平行机排序问题)
by: WUYong(吴用), et al.
Published: (2008-01-01)

西安地区中青年急性卒中患者肾小球滤过率估计值与1年死亡的关系研究
by: 张瑜瑜，刘仲仲，逯青丽，王静，刘佩，侯丽娜，张娜，蔺雪梅，王芳，吴松笛
Published: (2022-01-01)

基于小波SVD的光纤光栅振动系统消噪算法
by: 李靖, et al.
Published: (2010-01-01)

Existence of positive solutions for second order discrete periodic boundary value problems with sign-changing Green′s function(格林函数变号时二阶离散周期边值问题正解的存在性)
by: HUWenfeng(胡文丰), et al.
Published: (2022-11-01)

新一代业务运营支撑系统
by: 白双宝, et al.
Published: (2003-01-01)

Preliminary Test Estimation in the Rayleigh Distribution Using Minimax Regret Significance Levels
by: Baklizi, Ayman
Published: (2004)

Linguistic Multiple-Attribute Decision Making Based on Regret Theory and Minimax-DEA
by: Jinyi Hu
Published: (2023-10-01)

Booster method for singularly perturbed two-point boundary value problems(解一类奇异摄动两点边界值问题的Booster方法)
by: JINZhong-qiu(金中秋“), et al.
Published: (2005-05-01)

Properties of the set of the limit points of eigenvalues on graphs(图的特征值极限点集合的一些性质)
by: CHENYan(陈晏)
Published: (2002-07-01)

Behavior sequence and technique of generation based on multiple-valued logic(行为序列及基于多值逻辑的产生技术)
by: LUYang-jian(卢仰坚), et al.
Published: (2001-01-01)

Convergence of second derivative of a family of barycentric Hermite rational interpolants(一类重心权Hermite有理插值的二阶导数收敛性)
by: KANGNing(康宁), et al.
Published: (2022-05-01)

一种改进的小波阈值去噪方法
by: 张振凤, et al.
Published: (2018-01-01)

通信光缆线路中故障点的定位与检测
by: 廖敏敏, et al.
Published: (2015-01-01)

A finite difference scheme uniform in ε for singularly perturbed problems(关于ε一致的奇异摄动问题的差分格式及其收敛速度)
by: LIANGKe-wei(梁克维), et al.
Published: (2000-09-01)

当匹配数很小时具有最小拉普拉斯谱半径的树(Trees with small matching number and minimum Laplacian spectral radius)
by: LINXi-qin(林西芹), et al.
Published: (2013-09-01)

A boundary-type meshless method for the Robin inverse problem(一种求解Robin反问题的边界型无网格方法)
by: DONGChao-feng(董超峰)
Published: (2013-01-01)

Minimax Regret filter for uncertainty Single-Input Single-Output systems: simulation study
by: José Perea-Arango, et al.
Published: (2024-04-01)

An analytical method for solving Cauchy singular integral equations of the second kind with applications to fracture and contact analyses(断裂或接触力学问题中第二类柯西奇异积分方程的一种解析方法)
by: JINXiaoqing(金晓清), et al.
Published: (2017-09-01)