Scholarlink

<p>We tackle the challenge of augmenting the edge lengths of a tree so that a given vertex becomes the absolute center of the tree with the minimized total cost. Each augmentation cost is specified within an interval, and the minmax regret approach is applied to find a reasonable solution. This problem is known as the minmax regret inverse center problem on trees with augmentation of edge lengths. By relaxing the bounds of the edge lengths, we demonstrate a linear time algorithm that solves the problem on unweighted trees with deterministic costs. Concerning the minmax regret version, we first decompose the master problem into <i>m</i> subproblems with <i>m</i> being the number of leaves in the tree. Each subproblem is then solved in linear time using a convex program, resulting in the total complexity of <i>O</i>(<i>nm</i>) time with <i>n</i> being the number of vertices in the tree. Finally, we can solve the corresponding problem on weighted trees in <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(O(n^2)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mn>2</mn> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> time by leveraging similar properties.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Minmax Regret Inverse Single Facility Center Problem on Trees with Unbounded Augmentation of Edge Lengths

  • 期刊论文

  • 发表日期：

    2026年5月5日

查看全文
  • Nguyen Thanh Toan,
  • Tran Thu Le,
  • Kien Trung Nguyen,
  • Nguyen Thanh Hung

摘要

We tackle the challenge of augmenting the edge lengths of a tree so that a given vertex becomes the absolute center of the tree with the minimized total cost. Each augmentation cost is specified within an interval, and the minmax regret approach is applied to find a reasonable solution. This problem is known as the minmax regret inverse center problem on trees with augmentation of edge lengths. By relaxing the bounds of the edge lengths, we demonstrate a linear time algorithm that solves the problem on unweighted trees with deterministic costs. Concerning the minmax regret version, we first decompose the master problem into m subproblems with m being the number of leaves in the tree. Each subproblem is then solved in linear time using a convex program, resulting in the total complexity of O(nm) time with n being the number of vertices in the tree. Finally, we can solve the corresponding problem on weighted trees in \(O(n^2)\) O ( n 2 ) time by leveraging similar properties.