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:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Final Year Project |
| Language: | English |
| Published: |
Nanyang Technological University
2021
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/148476 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Nanyang Technological University |
| Language: | English |
| Summary: | 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. |
|---|