Efficient implementations of the BP heuristic for the shortest linear program (SLP) problem
In this article, we propose efficient implementations for the BP heuristic (the essential algorithm for the SLP problem). We first revisit the basic Paar algorithm. Next, we go through the details of the BP algorithm and discuss the bottleneck. We then propose two efficient approaches for efficient...
Saved in:
| 主要作者: | |
|---|---|
| 其他作者: | |
| 格式: | Final Year Project |
| 語言: | English |
| 出版: |
Nanyang Technological University
2021
|
| 主題: | |
| 在線閱讀: | https://hdl.handle.net/10356/148476 |
| 標簽: |
添加標簽
沒有標簽, 成為第一個標記此記錄!
|
| 機構: | Nanyang Technological University |
| 語言: | English |
| id |
sg-ntu-dr.10356-148476 |
|---|---|
| record_format |
dspace |
| spelling |
sg-ntu-dr.10356-1484762023-02-28T23:12:18Z Efficient implementations of the BP heuristic for the shortest linear program (SLP) problem Liu, Shuqing Thomas Peyrin School of Physical and Mathematical Sciences thomas.peyrin@ntu.edu.sg Science::Mathematics::Discrete mathematics::Algorithms In this article, we propose efficient implementations for the BP heuristic (the essential algorithm for the SLP problem). We first revisit the basic Paar algorithm. Next, we go through the details of the BP algorithm and discuss the bottleneck. We then propose two efficient approaches for efficient BP implementation: the SIMD approach and the binary search approach. Notably, our binary search approach outperforms the current implementation in [KLSW17] by more than 40 times on random 20 by 20 matrices. Bachelor of Science in Mathematical Sciences 2021-05-04T04:09:27Z 2021-05-04T04:09:27Z 2021 Final Year Project (FYP) Liu, S. (2021). Efficient implementations of the BP heuristic for the shortest linear program (SLP) problem. Final Year Project (FYP), Nanyang Technological University, Singapore. https://hdl.handle.net/10356/148476 https://hdl.handle.net/10356/148476 en application/pdf Nanyang Technological University |
| institution |
Nanyang Technological University |
| building |
NTU Library |
| continent |
Asia |
| country |
Singapore Singapore |
| content_provider |
NTU Library |
| collection |
DR-NTU |
| language |
English |
| topic |
Science::Mathematics::Discrete mathematics::Algorithms |
| spellingShingle |
Science::Mathematics::Discrete mathematics::Algorithms Liu, Shuqing Efficient implementations of the BP heuristic for the shortest linear program (SLP) problem |
| description |
In this article, we propose efficient implementations for the BP heuristic (the essential algorithm for the SLP problem). We first revisit the basic Paar algorithm. Next, we go through the details of the BP algorithm and discuss the bottleneck. We then propose two efficient approaches for efficient BP implementation: the SIMD approach and the binary search approach. Notably, our binary search approach outperforms the current implementation in [KLSW17] by more than 40 times on random 20 by 20 matrices. |
| author2 |
Thomas Peyrin |
| author_facet |
Thomas Peyrin Liu, Shuqing |
| format |
Final Year Project |
| author |
Liu, Shuqing |
| author_sort |
Liu, Shuqing |
| title |
Efficient implementations of the BP heuristic for the shortest linear program (SLP) problem |
| title_short |
Efficient implementations of the BP heuristic for the shortest linear program (SLP) problem |
| title_full |
Efficient implementations of the BP heuristic for the shortest linear program (SLP) problem |
| title_fullStr |
Efficient implementations of the BP heuristic for the shortest linear program (SLP) problem |
| title_full_unstemmed |
Efficient implementations of the BP heuristic for the shortest linear program (SLP) problem |
| title_sort |
efficient implementations of the bp heuristic for the shortest linear program (slp) problem |
| publisher |
Nanyang Technological University |
| publishDate |
2021 |
| url |
https://hdl.handle.net/10356/148476 |
| _version_ |
1759853787230502912 |