Approximation algorithms for capacitated partial inverse maximum spanning tree problem

Xianyue Li, Zhao Zhang (), Ruowang Yang, Heping Zhang and Ding-Zhu Du ()
Additional contact information
Xianyue Li: Lanzhou University
Zhao Zhang: Zhejiang Normal University
Ruowang Yang: Lanzhou University
Heping Zhang: Lanzhou University
Ding-Zhu Du: University of Texas at Dallas

Journal of Global Optimization, 2020, vol. 77, issue 2, No 6, 319-340

Abstract: Abstract Given an edge weighted graph, and an acyclic edge set, the goal of the partial inverse maximum spanning tree problem is to modify the weight function as little as possible such that there exists a maximum spanning tree with respect to the new weight function containing the given edge set. In this paper, we consider this problem with capacitated constraint under the $$l_{p}$$lp-norm, where p is an integer and $$p \in [1,+\,\infty )$$p∈[1,+∞). Firstly, we characterize the feasible solutions of this problem. Then, we present a $$\root p \of {k}$$kp-approximation algorithm for this problem when the weight function can only be decreased, where k is the number of edges in the given edge set. Finally, when the weight function can be either decreased and increased, we propose an approximation algorithm for the general case and analyse its approximation ratio. Moreover, we remark that these algorithms can be generalized under the weighted $$l_{p}$$lp-norm and the weighted sum Hamming distance.

Keywords: Partial inverse problem; Spanning tree; Approximation algorithm (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10898-019-00852-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:77:y:2020:i:2:d:10.1007_s10898-019-00852-4

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-019-00852-4

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().