Approximation algorithms for constructing required subgraphs using stock pieces of fixed length

Junran Lichen (), Jianping Li (), Ko-Wei Lih () and Xingxing Yu ()
Additional contact information
Junran Lichen: Yunnan University
Jianping Li: Yunnan University
Ko-Wei Lih: Academia Sinica
Xingxing Yu: Georgia Institute of Technology

Journal of Combinatorial Optimization, 2022, vol. 44, issue 3, No 20, 1774-1795

Abstract: Abstract In this paper, we address the problem of constructing required subgraphs using stock pieces of fixed length (CRS-SPFL, for short), which is a new variant of the minimum-cost edge-weighted subgraph (MCEWS, for short) problem. Concretely, for the MCEWS problem Q, it is asked to choose a minimum-cost subset of edges from a given graph G such that these edges can form a required subgraph $$G'$$ G ′ . For the CRS-SPFL problem $$Q^{\prime }$$ Q ′ , these edges in such a required subgraph $$G'$$ G ′ are further asked to be constructed by plus using some stock pieces of fixed length L. The new objective, however, is to minimize the total cost to construct such a required subgraph $$G'$$ G ′ , where the total cost is sum of the cost to purchase stock pieces of fixed length L and the cost to construct all edges in such a subgraph $$G'$$ G ′ . We obtain the following three main results. (1) Given an $$\alpha $$ α -approximation algorithm to solve the MCEWS problem, where $$\alpha \ge 1$$ α ≥ 1 (for the case $$\alpha =1$$ α = 1 , the MCEWS problem Q is solved optimally by a polynomial-time exact algorithm), we design a $$2\alpha $$ 2 α -approximation algorithm and another asymptotic $$\frac{7\alpha }{4}$$ 7 α 4 -approximation algorithm to solve the CRS-SPFL problem $$Q^{\prime }$$ Q ′ , respectively; (2) When Q is the minimum spanning tree problem, we provide a $$\frac{3}{2}$$ 3 2 -approximation algorithm and an AFPTAS to solve the problem $$Q^{\prime }$$ Q ′ of constructing a spanning tree using stock pieces of fixed length L, respectively; (3) When Q is the single-source shortest paths tree problem, we present a $$\frac{3}{2}$$ 3 2 -approximation algorithm and an AFPTAS to solve the problem $$Q^{\prime }$$ Q ′ of constructing a single-source shortest paths tree using stock pieces of fixed length L, respectively.

Keywords: Subgraph constructions; Stock pieces of length L; Bin packing; Approximation algorithms; AFPTAS (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00543-x 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:jcomop:v:44:y:2022:i:3:d:10.1007_s10878-020-00543-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-020-00543-x

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

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