Name
Title | ||
|---|---|---|
Approximation algorithms for constructing required subgraphs using stock pieces of fixed length |
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'$$
. For the CRS-SPFL problem
$$Q^{\prime }$$
, these edges in such a required subgraph
$$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'$$
, 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'$$
. We obtain the following three main results. (1) Given an
$$\alpha $$
-approximation algorithm to solve the MCEWS problem, where
$$\alpha \ge 1$$
(for the case
$$\alpha =1$$
, the MCEWS problem Q is solved optimally by a polynomial-time exact algorithm), we design a
$$2\alpha $$
-approximation algorithm and another asymptotic
$$\frac{7\alpha }{4}$$
-approximation algorithm to solve the CRS-SPFL problem
$$Q^{\prime }$$
, respectively; (2) When Q is the minimum spanning tree problem, we provide a
$$\frac{3}{2}$$
-approximation algorithm and an AFPTAS to solve the problem
$$Q^{\prime }$$
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}$$
-approximation algorithm and an AFPTAS to solve the problem
$$Q^{\prime }$$
of constructing a single-source shortest paths tree using stock pieces of fixed length L, respectively. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1007/s10878-020-00543-x | Journal of Combinatorial Optimization |
Keywords | DocType | Volume |
Subgraph constructions, Stock pieces of length L
, Bin packing, Approximation algorithms, AFPTAS | Journal | 44 |
Issue | ISSN | Citations |
3 | 1382-6905 | 0 |
PageRank | References | Authors |
0.34 | 8 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Junran Lichen | 1 | 2 | 2.77 |
| Jianping Li | 2 | 455 | 76.28 |
| Ko-wei Lih | 3 | 529 | 58.80 |
| Xingxing Yu | 4 | 0 | 0.34 |