Efficient implementations of the BP heuristic for the shortest linear program (SLP) problem

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...

Full description

Saved in:
Bibliographic Details
Main Author: Liu, Shuqing
Other Authors: Thomas Peyrin
Format: Final Year Project
Language:English
Published: Nanyang Technological University 2021
Subjects:
Science::Mathematics::Discrete mathematics::Algorithms
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
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

Similar Items