Zaválnij, Bogdán (2024) Solving Hard Combinatorial Problems in Parallel Using Lift-and-Project Preconditioning. In: 2024 IEEE High Performance Extreme Computing Virtual Conference, 2024.09.23-2024.09.27, Waltham (MA).
|
Text
hpec2024.pdf - Published Version Download (182kB) | Preview |
Abstract
—The original Lift and Project method was a useful tool for solving some ILP problems. Encouraged by this idea we propose a new method for preconditioning graphs for the k-clique problem. After a blow-up phase some standard preconditioning applied, then the results projected back to the original graph. Because the blow-up may produce a graph too big we deal with a series of smaller blown-up graphs that can be processed independently and thus parallelly. Numerical experiments back up the usefulness of this approach.
| Item Type: | Conference or Workshop Item (Paper) |
|---|---|
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika Q Science / természettudomány > QA Mathematics / matematika > QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 15 Jul 2025 09:33 |
| Last Modified: | 15 Jul 2025 09:33 |
| URI: | https://real.mtak.hu/id/eprint/221098 |
Actions (login required)
 |
Edit Item |
