Author name cluster

Fatos Xhafa

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

KER Journal 2015 Journal Article

Intelligent computing in large-scale systems

Joanna Kołodziej
Horacio González-Vélez
Fatos Xhafa
Leonard Barolli

Abstract Intelligent computing in large-scale systems provides systematic methodologies and tools for building complex inferential systems, which are able to adapt, mine data sets, evolve, and act in a nimble manner within major distributed environments with diverse architectures featuring multiple cores, accelerators, and high-speed networks. We believe that the papers presented in this special issue ought to serve as a reference for students, researchers, and industry practitioners interested in the evolving, interdisciplinary area of intelligent computing in large-scale systems. We very much hope that readers will find in this compendium new inspiration and ideas to enhance their own research.

Details DOI

TCS Journal 2005 Journal Article

The approximability of non-Boolean satisfiability problems and restricted integer programming

Maria Serna
Luca Trevisan
Fatos Xhafa

In this paper we present improved approximation algorithms for two classes of maximization problems defined in Barland et al. (J. Comput. System Sci. 57(2) (1998) 144). Our factors of approximation substantially improve the previous known results and are close to the best possible. On the other hand, we show that the approximation results in the framework of Barland et al. hold also in the parallel setting, and thus we have a new common framework for both computational settings. We prove almost tight non-approximability results, thus solving a main open question of Barland et al. We obtain the results through the constraint satisfaction problem over multi-valued domains, for which we develop approximation algorithms and show non-approximability results. Our parallel approximation algorithms are based on linear programming and random rounding; they are better than previously known sequential algorithms. The non-approximability results are based on new recent progress in the fields of probabilistically checkable proofs and multi-prover one-round proof systems.

Details DOI

TCS Journal 2001 Journal Article

On the parallel approximability of a subclass of quadratic programming

Maria Serna
Fatos Xhafa

In this paper we deal with the parallel approximability of a special class of quadratic programming (QP), called smooth quadratic programming. This subclass of QP is obtained by imposing restrictions on the coefficients of QP instance, namely the smoothness and positiveness restrictions. The smoothness condition restricts the magnitudes of the coefficients of the instance while the positiveness condition requires that (part of) the coefficients of the instance be non-negative. Interestingly, even with these restrictions several combinatorial optimization problems are captured by this class. We show that there is a parallel additive approximation procedure to instances of smooth QP. The additive procedure translates into an NC approximation scheme (NCAS) when the optimal value of the instance is Ω(n2), where n is the number of variables of the instance. In particular, the procedure yields an NCAS for positive instances of smooth QP. The additive approximation procedure is obtained by reducing the instance of QP to an instance of positive linear programming, finding in NC an approximate fractional solution to the obtained program, and then rounding the fractional solution to an integer approximate solution for the original problem. Next, we extend the result to instances of bounded degree Smooth Integer Programming. Finally, we consider several combinatorial problems that are modeled by smooth QP (or smooth integer programs) and show that the techniques presented here can be used to obtain NC Approximation Schemes for “dense” instances of such problems.

Details DOI