Dense Subset Sum may be the hardest

Per Austrin, Petteri Kaski, Mikko Koivisto, Jesper Nederlof

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference article in proceedingsScientificvertaisarvioitu

12 Sitaatiot (Scopus)
123 Lataukset (Pure)

Abstrakti

The Subset Sum problem asks whether a given set of n positive integers contains a subset of elements that sum up to a given target t. It is an outstanding open question whether the O(2n/2)-time algorithm for Subset Sum by Horowitz and Sahni [J. ACM 1974] can be beaten in the worst-case setting by a "truly faster", O(2(0.5-δ)n)-time algorithm, with some constant δ > 0. Continuing an earlier work [STACS 2015], we study Subset Sum parameterized by the maximum bin size β, defined as the largest number of subsets of the n input integers that yield the same sum. For every ∈ > 0 we give a truly faster algorithm for instances with β ≤ 2(0.5-∈)n, as well as instances with β ≥ 20.661n. Consequently, we also obtain a characterization in terms of the popular density parameter n/log2 t: if all instances of density at least 1.003 admit a truly faster algorithm, then so does every instance. This goes against the current intuition that instances of density 1 are the hardest, and therefore is a step toward answering the open question in the affirmative. Our results stem from a novel combinatorial analysis of mixings of earlier algorithms for Subset Sum and a study of an extremal question in additive combinatorics connected to the problem of Uniquely Decodable Code Pairs in information theory.

AlkuperäiskieliEnglanti
OtsikkoLeibniz International Proceedings in Informatics
AlaotsikkoLIPIcs
ToimittajatNicolas Ollinger, Heribert Vollmer
KustantajaSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Sivut1-12
Vuosikerta47
ISBN (painettu)9783959770019
DOI - pysyväislinkit
TilaJulkaistu - 1 helmik. 2016
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisussa
TapahtumaSymposium on Theoretical Aspects of Computer Science - University of Orleans, Orleans, Ranska
Kesto: 17 helmik. 201620 helmik. 2016
Konferenssinumero: 33
http://www.univ-orleans.fr/lifo/events/STACS2016/

Conference

ConferenceSymposium on Theoretical Aspects of Computer Science
LyhennettäSTACS
Maa/AlueRanska
KaupunkiOrleans
Ajanjakso17/02/201620/02/2016
www-osoite

Sormenjälki

Sukella tutkimusaiheisiin 'Dense Subset Sum may be the hardest'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä