Approximation algorithms for variable-sized materials constructing tree-form structures in undirected graph

Kehong Wang

doi:10.1117/12.2673307

14 April 2023 Approximation algorithms for variable-sized materials constructing tree-form structures in undirected graph

Kehong Wang

Author Affiliations +

Proceedings Volume 12613, International Conference on Computer Vision, Application, and Algorithm (CVAA 2022); 1261313 (2023) https://doi.org/10.1117/12.2673307
Event: International Conference on Computer Vision, Application, and Algorithm (CVAA 2022), 2022, Chongqing, China

Abstract

It is known that one-dimensional variable-sized bin packing problem and network optimization problem are classical combinatorial optimization problems. Inspired by this, we consider a new problem of variable-sized materials constructing some tree-form structures in undirected graph, where all edges spliced in such a tree-form structure are assembled from some pieces of m types of materials. More precisely, that is defined as follows: given a weighted graph G = (V, E; w; b), a tree-form structure S and some pieces of m types of materials, where w : E → R⁺ is a length function , b : E → R⁺ is a cost function , we will attempt to construct a subgraph G' from G , having the structure S , such that each edge in G' is further constructed by given m types of materials , the new objective is to minimize the total cost to construct subgraph G' , where the total cost is sum of the cost to purchase materials and the cost to construct all edges in such a subgraph G'. For this new problem, we obtained the following two main results. (1) When the structure S is a spanning tree, we design a two- approximation algorithm to solve the problem of variable-sized materials constructing spanning tree. (2) When the structure S is a single-source shortest paths tree, we design a two- approximation algorithm to solve the problem of variable-sized materials constructing single-source shortest paths tree.

Citation Download Citation

Kehong Wang "Approximation algorithms for variable-sized materials constructing tree-form structures in undirected graph", Proc. SPIE 12613, International Conference on Computer Vision, Application, and Algorithm (CVAA 2022), 1261313 (14 April 2023); https://doi.org/10.1117/12.2673307

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available