About | Contact Us | Register | Login
ProceedingsSeriesJournalsSearchEAI
Wireless Internet. 15th EAI International Conference, WiCON 2022, Virtual Event, November 2022, Proceedings

Research Article

Deep-Steiner: Learning to Solve the Euclidean Steiner Tree Problem

Cite
BibTeX Plain Text
  • @INPROCEEDINGS{10.1007/978-3-031-27041-3_16,
        author={Siqi Wang and Yifan Wang and Guangmo Tong},
        title={Deep-Steiner: Learning to Solve the Euclidean Steiner Tree Problem},
        proceedings={Wireless Internet. 15th EAI International Conference, WiCON 2022, Virtual Event, November 2022, Proceedings},
        proceedings_a={WICON},
        year={2023},
        month={2},
        keywords={Reinforcement learning Combinatorial optimization The steiner tree problem},
        doi={10.1007/978-3-031-27041-3_16}
    }
    
  • Siqi Wang
    Yifan Wang
    Guangmo Tong
    Year: 2023
    Deep-Steiner: Learning to Solve the Euclidean Steiner Tree Problem
    WICON
    Springer
    DOI: 10.1007/978-3-031-27041-3_16
Siqi Wang1,*, Yifan Wang1, Guangmo Tong1
  • 1: University of Delaware, Newark
*Contact email: wsqbit@udel.edu

Abstract

The Euclidean Steiner tree problem seeks the min-cost network to connect a collection of target locations, and it underlies many applications of wireless networks. In this paper, we present a study on solving the Euclidean Steiner tree problem using reinforcement learning enhanced by graph representation learning. Different from the commonly studied connectivity problems like travelling salesman problem or vehicle routing problem where the search space is finite, the Euclidean Steiner tree problem requires to search over the entire Euclidean space, thereby making the existing methods not applicable. In this paper, we design discretization methods by leveraging the unique characteristics of the Steiner tree, and propose new training schemes for handling the dynamic Steiner points emerging during the incremental construction. Our design is examined through a sanity check using experiments on a collection of datasets, with encouraging results demonstrating the utility of our method as an alternative to classic combinatorial methods.

Keywords
Reinforcement learning Combinatorial optimization The steiner tree problem
Published
2023-02-18
Appears in
SpringerLink
http://dx.doi.org/10.1007/978-3-031-27041-3_16
Copyright © 2022–2025 ICST
EBSCOProQuestDBLPDOAJPortico
EAI Logo

About EAI

  • Who We Are
  • Leadership
  • Research Areas
  • Partners
  • Media Center

Community

  • Membership
  • Conference
  • Recognition
  • Sponsor Us

Publish with EAI

  • Publishing
  • Journals
  • Proceedings
  • Books
  • EUDL