Exact versus Approximate: the Effective Use of two Algorithmic Paradigms in some Applied Combinatorial Problems

Project Description: We study the effectiveness of two algorithmic paradigms in solving computationally intractable problems: (i) giving exact solutions with reasonable super-polynomial running times, and (ii) giving approximate solutions in polynomial running time, but with some guarantee on the quality of the returned solution compared to an optimum solution. In particular, we employ fixed-parameter tractability (FPT) methods to improve exact and approximate solutions to a number of problems including domination problems in graphs/networks.

PIs: Faisal N. Abu-Khzam and Cristina Bazgan

Funding: bilateral research cooperation CEDRE between France and Lebanon (grant number 30885TM).

Publications:

F. N. Abu-Khzam, C. Bazgan, M. Chopin and H. Fernau. Approximation Algorithms Inspired by Kernelization Methods, in Proceedings of the 25th International Symposium on Algorithms and Computation (ISAAC 2014),
Lecture Notes in Computer Science (LNCS 8889), Jeonju, Korea, December 15-17, 2014, pages 479-490.

F. N. Abu-Khzam, C. Bazgan, J. El-Haddad and F. Sikora. On the Complexity of QoS-aware Service Selection Problem, in Proceedings of the 13th International Conference on Service Oriented Computing (ICSOC 2015), Goa, India, November 2015.

F. N. Abu-Khzam, C. Bazgan, M. Chopin and H. Fernau. Data Reductions and Combinatorial Bounds for Improved Approximation Algorithms, Journal of Computer and System Sciences. volume 82, pages 503-520, 2016.