Inverse Max + Sum spanning tree problem by modifying the sum-cost vector under weighted <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$$l_\infty $$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <msub> <mi>l</mi> <mi>∞</mi> </msub> </math> </EquationSource> </InlineEquation> Norm
The inverse max + sum spanning tree (IMSST) problem is studied, which is the first inverse problem on optimization problems with combined minmax–minsum objective functions. Given an edge-weighted undirected network <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$$G(V,E,c,w)$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <mi>G</mi> <mo stretchy="false">(</mo> <mi>V</mi> <mo>,</mo> <mi>E</mi> <mo>,</mo> <mi>c</mi> <mo>,</mo> <mi>w</mi> <mo stretchy="false">)</mo> </mrow> </math> </EquationSource> </InlineEquation>, the MSST problem is to find a spanning tree <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$$T$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mi>T</mi> </math> </EquationSource> </InlineEquation> which minimizes the combined weight <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$$\max _{e\in T}w(e)+\sum _{e\in T}c(e)$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <msub> <mo movablelimits="true">max</mo> <mrow> <mi>e</mi> <mo>∈</mo> <mi>T</mi> </mrow> </msub> <mi>w</mi> <mrow> <mo stretchy="false">(</mo> <mi>e</mi> <mo stretchy="false">)</mo> </mrow> <mo>+</mo> <msub> <mo>∑</mo> <mrow> <mi>e</mi> <mo>∈</mo> <mi>T</mi> </mrow> </msub> <mi>c</mi> <mrow> <mo stretchy="false">(</mo> <mi>e</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math> </EquationSource> </InlineEquation>, which can be solved in <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$$O(m\log n)$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mi>m</mi> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math> </EquationSource> </InlineEquation> time, where <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$$m:=|E|$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <mi>m</mi> <mo>:</mo> <mo>=</mo> <mo stretchy="false">|</mo> <mi>E</mi> <mo stretchy="false">|</mo> </mrow> </math> </EquationSource> </InlineEquation> and <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$$n:=|V|$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <mi>n</mi> <mo>:</mo> <mo>=</mo> <mo stretchy="false">|</mo> <mi>V</mi> <mo stretchy="false">|</mo> </mrow> </math> </EquationSource> </InlineEquation>. Whereas, in an IMSST problem, a spanning tree <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$$T_0$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <msub> <mi>T</mi> <mn>0</mn> </msub> </math> </EquationSource> </InlineEquation> of <InlineEquation ID="IEq10"> <EquationSource Format="TEX">$$G$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mi>G</mi> </math> </EquationSource> </InlineEquation> is given, which is not an optimal MSST. A new sum-cost vector <InlineEquation ID="IEq11"> <EquationSource Format="TEX">$$\bar{c}$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mover accent="true"> <mrow> <mi>c</mi> </mrow> <mrow> <mo stretchy="false">¯</mo> </mrow> </mover> </math> </EquationSource> </InlineEquation> is to be identified so that <InlineEquation ID="IEq12"> <EquationSource Format="TEX">$$T_0$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <msub> <mi>T</mi> <mn>0</mn> </msub> </math> </EquationSource> </InlineEquation> becomes an optimal MSST of the network <InlineEquation ID="IEq13"> <EquationSource Format="TEX">$$G(V,E,\bar{c},w)$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <mi>G</mi> <mo stretchy="false">(</mo> <mi>V</mi> <mo>,</mo> <mi>E</mi> <mo>,</mo> <mover accent="true"> <mrow> <mi>c</mi> </mrow> <mrow> <mo stretchy="false">¯</mo> </mrow> </mover> <mo>,</mo> <mi>w</mi> <mo stretchy="false">)</mo> </mrow> </math> </EquationSource> </InlineEquation>, where <InlineEquation ID="IEq14"> <EquationSource Format="TEX">$$0\le c-l\le \bar{c} \le c+u$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <mn>0</mn> <mo>≤</mo> <mi>c</mi> <mo>-</mo> <mi>l</mi> <mo>≤</mo> <mover accent="true"> <mrow> <mi>c</mi> </mrow> <mrow> <mo stretchy="false">¯</mo> </mrow> </mover> <mo>≤</mo> <mi>c</mi> <mo>+</mo> <mi>u</mi> </mrow> </math> </EquationSource> </InlineEquation> and <InlineEquation ID="IEq15"> <EquationSource Format="TEX">$$l,u\ge 0$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <mi>l</mi> <mo>,</mo> <mi>u</mi> <mo>≥</mo> <mn>0</mn> </mrow> </math> </EquationSource> </InlineEquation>. The objective is to minimize the cost <InlineEquation ID="IEq16"> <EquationSource Format="TEX">$$\max _{e\in E}q(e)|\bar{c}(e)-c(e)|$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <msub> <mo movablelimits="true">max</mo> <mrow> <mi>e</mi> <mo>∈</mo> <mi>E</mi> </mrow> </msub> <mi>q</mi> <mrow> <mo stretchy="false">(</mo> <mi>e</mi> <mo stretchy="false">)</mo> </mrow> <mrow> <mo stretchy="false">|</mo> <mover accent="true"> <mrow> <mi>c</mi> </mrow> <mrow> <mo stretchy="false">¯</mo> </mrow> </mover> <mrow> <mo stretchy="false">(</mo> <mi>e</mi> <mo stretchy="false">)</mo> </mrow> <mo>-</mo> <mi>c</mi> <mrow> <mo stretchy="false">(</mo> <mi>e</mi> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">|</mo> </mrow> </mrow> </math> </EquationSource> </InlineEquation> incurred by modifying the sum-cost vector <InlineEquation ID="IEq17"> <EquationSource Format="TEX">$$c$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mi>c</mi> </math> </EquationSource> </InlineEquation> under weighted <InlineEquation ID="IEq18"> <EquationSource Format="TEX">$$l_\infty $$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <msub> <mi>l</mi> <mi>∞</mi> </msub> </math> </EquationSource> </InlineEquation> norm, where <InlineEquation ID="IEq19"> <EquationSource Format="TEX">$$q(e)\ge 1$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <mi>q</mi> <mo stretchy="false">(</mo> <mi>e</mi> <mo stretchy="false">)</mo> <mo>≥</mo> <mn>1</mn> </mrow> </math> </EquationSource> </InlineEquation>. We show that the unbounded IMSST problem is a linear fractional combinatorial optimization (LFCO) problem and develop a discrete type Newton method to solve it. Furthermore, we prove an <InlineEquation ID="IEq20"> <EquationSource Format="TEX">$$O(m)$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mi>m</mi> <mo stretchy="false">)</mo> </mrow> </math> </EquationSource> </InlineEquation> bound on the number of iterations, although most LFCO problems can be solved in <InlineEquation ID="IEq21"> <EquationSource Format="TEX">$$O(m^2 \log m)$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>m</mi> <mn>2</mn> </msup> <mo>log</mo> <mi>m</mi> <mo stretchy="false">)</mo> </mrow> </math> </EquationSource> </InlineEquation> iterations. Therefore, both the unbounded and bounded IMSST problems can be solved by solving <InlineEquation ID="IEq22"> <EquationSource Format="TEX">$$O(m)$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mi>m</mi> <mo stretchy="false">)</mo> </mrow> </math> </EquationSource> </InlineEquation> MSST problems. Computational results show that the algorithms can efficiently solve the problems. Copyright Springer Science+Business Media New York 2015
Year of publication: |
2015
|
---|---|
Authors: | Guan, Xiucui ; Pardalos, Panos ; Zuo, Xia |
Published in: |
Journal of Global Optimization. - Springer. - Vol. 61.2015, 1, p. 165-182
|
Publisher: |
Springer |
Saved in:
Online Resource
Saved in favorites
Similar items by person
-
Inverse 1-median problem on trees under weighted Hamming distance
Guan, Xiucui, (2012)
-
Improving multicut in directed trees by upgrading nodes
Guan, Xiucui, (2007)
-
A class of node based bottleneck improvement problems
Guan, Xiucui, (2006)
- More ...