Projects / Programmes source: ARIS

Approximation algorithms on clusters: high-performance computing on cheap workstations

Research activity

Code Science Field Subfield
2.07.01  Engineering sciences and technologies  Computer science and informatics  Computer structures, systems and networks - software 

Code Science Field
T170  Technological sciences  Electronics 
algorithm, complexity, NP-completeness, approximation algorithm, parallel computing, cluster, partitioning problem
Evaluation (rules)
source: COBISS
Researchers (5)
no. Code Name and surname Research area Role Period No. of publicationsNo. of publications
1.  10581  PhD Polonca Blaznik  Computer science and informatics  Researcher  1998 - 1999  23 
2.  08724  PhD Aleksandar Jurišić  Mathematics  Researcher  1997 - 1999  209 
3.  10824  PhD Barbara Koroušić Seljak  Computer science and informatics  Researcher  1999  335 
4.  04646  PhD Borut Robič  Computer science and informatics  Head  1997 - 1999  292 
5.  03430  PhD Janez Žerovnik  Mathematics  Researcher  1997 - 1999  805 
Organisations (2)
no. Code Research organisation City Registration number No. of publicationsNo. of publications
1.  0101  Institute of Mathematics, Physics and Mechanics  Ljubljana  5055598000  19,658 
2.  0106  Jožef Stefan Institute  Ljubljana  5051606000  90,038 
Many practical and important optimization problems turned out to be NP-complete. This implies that – unless P is not NP-- these problems are computationally intractable for problem instances of any significant size. In such cases one can sacrifice optimality and starts looking for approximate solutions that are computable in polynomial time (with respect to the problem size). However, an approximation algorithm, though polynomial with respect to the problem size, may exhibit superpolinomial (e.g. exponential) time complexity with respect to the required accuracy of the approximate solutions. Informally, this means that improving the accuracy of the solution quickly becomes a very costly task in terms of computational time. Thus, accuracy improvement for such problems is practically infeasible and can be carried further on (up to a certain point) only by means of a high-performance computing system. Alternatively, a more cost effective solution is to use a cluster, that is, a set of relatively cheap interconnected workstations. In our project, we will form a cluster and then determine the extent to which approximation algorithms for some practical problems (e.g. partitioning problems) are capable of exploiting cluster computing.
Views history