• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

Inverse max + sum spanning tree problem under Hamming distance by modifying the sum-cost vector

Guan X., He X., Pardalos P. M., Zhang B.

The inverse max ++ sum spanning tree (MSST) problem is considered by modifying the sum-cost vector under the Hamming Distance. On an undirected network G(VEwc), a weight w(e) and a cost c(e) are prescribed for each edge eEe∈E. The MSST problem is to find a spanning tree TT∗ which makes the combined weight maxeTw(e)+eTc(e)maxe∈Tw(e)+∑e∈Tc(e) as small as possible. It can be solved in O(mlogn)O(mlog⁡n) time, where m:=|E|m:=|E| and n:=|V|n:=|V|. Whereas, in an inverse MSST problem, a given spanning tree T0T0 of G is not an optimal MSST. The sum-cost vector c is to be modified to c¯c¯ so that T0T0 becomes an optimal MSST of the new network G(V,E,w,c¯)G(V,E,w,c¯) and the cost c¯cc¯−c can be minimized under Hamming Distance. First, we present a mathematical model for the inverse MSST problem and a method to check the feasibility. Then, under the weighted bottleneck-type Hamming distance, we design a binary search algorithm whose time complexity is O(mlog2n)O(mlog2n). Next, under the unit sum-type Hamming distance, which is also called l0l0 norm, we show that the inverse MSST problem (denoted by IMSST00) is NPNP−hard. Assuming NPDTIME(mpolylogm)NP⊈DTIME(mpolylog⁡m), the problem IMSST00 is not approximable within a factor of 2log1εm2log1−ε⁡m, for any ε>0ε>0. Finally, We consider the augmented problem of IMSST00 (denoted by AIMSST00), whose objective function is to multiply the l0l0 norm β0‖β‖0 by a sufficiently large number M plus the l1l1 norm β1‖β‖1. We show that the augmented problem and the l1l1 norm problem have the same Lagrange dual problems. Therefore, the l1l1 norm problem is the best convex relaxation (in terms of Lagrangian duality) of the augmented problem AIMSST00, which has the same optimal solution as that of the inverse problem IMSST00.