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


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
Place of PublicationPiscataway, NJ
PublisherIEEE, Institute of Electrical and Electronics Engineers
Number of pages4
ISBN (Electronic)9781728186993
Publication statusPublished - Sept 2020
Event2nd International Conference on Transdisciplinary AI, TransAI 2020 - Virtual, Irvine, United States
Duration: 21 Sept 202023 Sept 2020

Publication series

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


Conference2nd International Conference on Transdisciplinary AI, TransAI 2020
Country/TerritoryUnited States
CityVirtual, Irvine


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

Cite this