Displaying 21 – 40 of 96

Showing per page

A new curve fitting based rating prediction algorithm for recommender systems

Yilmaz Ar, Şahin Emrah Amrahov, Nizami A. Gasilov, Sevgi Yigit-Sert (2022)

Kybernetika

The most algorithms for Recommender Systems (RSs) are based on a Collaborative Filtering (CF) approach, in particular on the Probabilistic Matrix Factorization (PMF) method. It is known that the PMF method is quite successful for the rating prediction. In this study, we consider the problem of rating prediction in RSs. We propose a new algorithm which is also in the CF framework; however, it is completely different from the PMF-based algorithms. There are studies in the literature that can increase...

A new practical linear space algorithm for the longest common subsequence problem

Heiko Goeman, Michael Clausen (2002)

Kybernetika

This paper deals with a new practical method for solving the longest common subsequence (LCS) problem. Given two strings of lengths m and n , n m , on an alphabet of size s , we first present an algorithm which determines the length p of an LCS in O ( n s + min { m p , p ( n - p ) } ) time and O ( n s ) space. This result has been achieved before [ric94,ric95], but our algorithm is significantly faster than previous methods. We also provide a second algorithm which generates an LCS in O ( n s + min { m p , m log m + p ( n - p ) } ) time while preserving the linear space bound, thus solving...

A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation

Marcia R. Cerioli, Luerbio Faria, Talita O. Ferreira, Fábio Protti (2011)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

A unit disk graph is the intersection graph of a family of unit disks in the plane. If the disks do not overlap, it is also a unit coin graph or penny graph. It is known that finding a maximum independent set in a unit disk graph is a NP-hard problem. In this work we extend this result to penny graphs. Furthermore, we prove that finding a minimum clique partition in a penny graph is also NP-hard, and present two linear-time approximation algorithms for the computation of clique partitions: a 3-approximation...

A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation

Marcia R. Cerioli, Luerbio Faria, Talita O. Ferreira, Fábio Protti (2011)

RAIRO - Theoretical Informatics and Applications

A unit disk graph is the intersection graph of a family of unit disks in the plane. If the disks do not overlap, it is also a unit coin graph or penny graph. It is known that finding a maximum independent set in a unit disk graph is a NP-hard problem. In this work we extend this result to penny graphs. Furthermore, we prove that finding a minimum clique partition in a penny graph is also NP-hard, and present two linear-time approximation algorithms for the computation of clique partitions: a 3-approximation...

A note on the computational complexity of hierarchical overlapping clustering

Mirko Křivánek (1985)

Aplikace matematiky

In this paper the computational complexity of the problem of the approximation of a given dissimilarity measure on a finite set X by a k -ultrametric on X and by a Robinson dissimilarity measure on X is investigared. It is shown that the underlying decision problems are NP-complete.

Currently displaying 21 – 40 of 96