Title
Towards the Succinct Representation of m Out of n
Date Issued
01 January 2018
Access level
metadata only access
Resource Type
conference paper
Author(s)
Waseda University
Publisher(s)
Springer Verlag
Abstract
Combinations of n objects taken m at the time are ubiquitous in a wide range of combinatorial problems. In this paper, we introduce a novel approach to generate combinations from given integer numbers by using a gradient-based algorithm through plural number of CPU and GPU processors. The time complexity is bounded by O(m2) when using a single processor, and bounded by O(mlog m) when using at most O(m/ log m) processors. Relevant computational experiments confirmed the practical efficiency within computationally allowable limits. Our approach offers the building blocks to represent combinations with succinct encoding and complexity being independent of n, which is meritorious when n is very large, or when n is time-varying.
Start page
16
End page
26
Volume
11226 LNCS
Language
English
OCDE Knowledge area
Ingeniería de sistemas y comunicaciones Hardware, Arquitectura de computadoras
Scopus EID
2-s2.0-85055672556
ISSN of the container
03029743
ISBN of the container
9783030027377
Conference
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Sources of information: Directorio de Producción Científica Scopus