Parallel representation of local elimination algorithm for accelerating the solving sparse discrete optimization problems

Lemtyuzhnikova D.V.
 pdf (238K)  / List of references

The decomposition algorithms provide approaches to deal with NP-hardness in solving discrete optimization problems (DOPs). In this article one of the promising ways to exploit sparse matrices — local elimination algorithm in parallel interpretation (LEAP) are demonstrated. That is a graph-based structural decomposition algorithm, which allows to compute a solution in stages such that each of them uses results from previous stages. At the same time LEAP heavily depends on elimination ordering which actually provides solving stages. Also paper considers tree- and block-parallel for LEAP and required realization process of it comparison of a several heuristics for obtaining a better elimination order and shows how is related graph structure, elimination ordering and solving time.

Keywords: discrete optimization, volunteer computing, local elimination algorithm, parallel computing, sparse problems, elimination tree
Citation in English: Lemtyuzhnikova D.V. Parallel representation of local elimination algorithm for accelerating the solving sparse discrete optimization problems // Computer Research and Modeling, 2015, vol. 7, no. 3, pp. 699-705
Citation in English: Lemtyuzhnikova D.V. Parallel representation of local elimination algorithm for accelerating the solving sparse discrete optimization problems // Computer Research and Modeling, 2015, vol. 7, no. 3, pp. 699-705
DOI: 10.20537/2076-7633-2015-7-3-699-705
URL: http://crm-en.ics.org.ru/journal/article/2326/
Creative Commons License This work is licensed under a Creative Commons Attribution-NoDerivs 3.0 Unported License.
Views (last year): 1.

Indexed in Scopus

Full-text version of the journal is also available on the web site of the scientific electronic library eLIBRARY.RU

The journal is included in the Russian Science Citation Index

The journal is included in the RSCI

International Interdisciplinary Conference "Mathematics. Computing. Education"

Copyright © 2009–2024 Institute of Computer Science