Semi-Exact Exponential-Time Algorithms: An Experimental Study

Mohamed Mahmoud Abd El-Wahab, Faisal N. Abu-Khzam, Kai Wang, Peter Shaw

Research output: Chapter in Book/Report/Conference proceedingConference Paper published in Proceedingspeer-review

Abstract

The last decade witnessed an increased interest in exact and parameterized exponential-time algorithms for NP - hard problems. The hardness of polynomial-time approximation of many intractable problems motivated the work on fixed-parameter approximation where polynomial-time is relaxed into FPT -time as long as improved approximation is obtained, most often requiring constant ratio bounds. In this paper we move a step further by investigating the practicality of exponential time approximation (versus FPT-time) as long as obtained solutions are within an additive parameter. The running time of such algorithm would be reduced by some function (factor) of the same parameter. The objective is to obtain a cost-effective trade-off between reduced running time and quality of approximation while providing provably near optimal solutions. We present experimental studies of two problems: Dominating Set and Vertex Cover. Our experiments show that semi-exact algorithms are indeed very promising.

Original languageEnglish
Title of host publicationProceedings - 2020 2nd International Conference on Transdisciplinary AI, TransAI 2020
PublisherIEEE, Institute of Electrical and Electronics Engineers
Pages96-99
Number of pages4
ISBN (Electronic)9781728186993
DOIs
Publication statusPublished - Sep 2020
Event2nd International Conference on Transdisciplinary AI, TransAI 2020 - Virtual, Irvine, United States
Duration: 21 Sep 202023 Sep 2020

Publication series

NameProceedings - 2020 2nd International Conference on Transdisciplinary AI, TransAI 2020

Conference

Conference2nd International Conference on Transdisciplinary AI, TransAI 2020
CountryUnited States
CityVirtual, Irvine
Period21/09/2023/09/20

Fingerprint

Dive into the research topics of 'Semi-Exact Exponential-Time Algorithms: An Experimental Study'. Together they form a unique fingerprint.

Cite this