Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10331098 | Information Processing Letters | 2015 | 5 Pages |
Abstract
Let X={xi:1â¤iâ¤n}âN+, and hâN+. The h-iterated sumset of X, denoted hX, is the set {x1+x2+â¦+xh:x1,x2,â¦,xhâX}, and the [h]-sumset of X, denoted [h]X, is the set âi=1hiX. A [h]-sumset cover of SâN+ is a set XâN+ such that Sâ[h]X. In this paper, we focus on the case h=2, and study the APX-hard problem of computing a minimum cardinality [2]-sumset cover X of S (i.e. computing a minimum cardinality set XâN+ such that every element of S is either an element of X, or the sum of two - non-necessarily distinct - elements of X). We propose two new algorithmic results. First, we give a fixed-parameter tractable (FPT) algorithm that decides the existence of a [2]-sumset cover of size at most k of a given set S. Our algorithm runs in O(2(3logâ¡kâ1.4)kpoly(k)) time, and thus outperforms the O(5k2(k+3)2k2logâ¡(k)) time FPT result presented in Fagnot et al. (2009) [5]. Second, we show that deciding whether a set S has a smaller [2]-sumset cover than itself is NP-hard.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Laurent Bulteau, Guillaume Fertin, Romeo Rizzi, Stéphane Vialette,