Research Article
Approximation Algorithms for the Balanced Optimization Splicing Problem in Undirected Graph
@INPROCEEDINGS{10.1007/978-3-030-72792-5_24, author={Yongsong Wen}, title={Approximation Algorithms for the Balanced Optimization Splicing Problem in Undirected Graph}, proceedings={Simulation Tools and Techniques. 12th EAI International Conference, SIMUtools 2020, Guiyang, China, August 28-29, 2020, Proceedings, Part I}, proceedings_a={SIMUTOOLS}, year={2021}, month={4}, keywords={Balanced optimization Balanced spanning tree Approximation algorithms}, doi={10.1007/978-3-030-72792-5_24} }- Yongsong Wen
Year: 2021
Approximation Algorithms for the Balanced Optimization Splicing Problem in Undirected Graph
SIMUTOOLS
Springer
DOI: 10.1007/978-3-030-72792-5_24
Abstract
One-dimensional bin packing problem and balanced optimization problem are two classical problems in combinatorial optimization, inspired by this, we research a balanced optimization splicing problem: given a weight connectedG(V,E;w), a balanced spanning tree structure(\mathcal {A})and a specific material of fixed length(\ell ), where(w:E\rightarrow Q^+)(or(w:E\rightarrow Z^+)), each edge in the graphGis allowed to be greater than or equal to(\ell ), we will use this specific material to splice a subgraphTfrom graphGwith balanced spanning tree structure(\mathcal {A}), and these edges spliced in such required structures are supposed to be cut from some pieces of a specific material of fixed length(\ell ), the objective is to minimize the amount of special material used when splicing all the edges of the subgraphTwith the given material. In this paper, we consider three kinds of balanced spanning tree structures for this problem and design three approximation algorithms.
