The Library
A polynomial-time solution for the maximum subsets problem
Tools
Challita, Khalil, Bou Abdo, Jacques, Farhat, Hikmat and Makary, Mireille (2022) A polynomial-time solution for the maximum subsets problem. IAENG International Journal of Computer Science, 49 (4). pp. 1162-1168. ISSN 1819-656X.
An open access version can be found in:
Official URL: http://www.iaeng.org/IJCS/issues_v49/issue_4/IJCS_...
Abstract
The main purpose of this paper is to determine a non-trivial tractable class of the maximum (k,m)-subsets problem. More specifically, we show that we can solve this problem in polynomial time for m = 1. Depending on the value of k with respect to n, we prove that in the best-case scenario our algorithm runs in O(√n) time. On the other hand, an upper bound for solving it is given by O(n4/k3). Furthermore, for the case where n = k2, we design and implement an algorithm in Python that yields a solution in O(n5/2)
Item Type: | Journal Article | ||||||
---|---|---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Journal or Publication Title: | IAENG International Journal of Computer Science | ||||||
Publisher: | International Association of Engineers | ||||||
ISSN: | 1819-656X | ||||||
Official Date: | 1 December 2022 | ||||||
Dates: |
|
||||||
Volume: | 49 | ||||||
Number: | 4 | ||||||
Page Range: | pp. 1162-1168 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||
Copyright Holders: | © Copyright International Association of Engineers | ||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |