Approximating subset sum ratio via partition computations

被引：1

作者：

Alonistiotis, Giannis ^{[1
]}

Antonopoulos, Antonis ^{[1
]}

Melissinos, Nikolaos ^{[2
]}

Pagourtzis, Aris ^{[1
,3
]}

Petsalakis, Stavros ^{[1
]}

Vasilakis, Manolis ^{[4
]}

机构：

[1] Natl Tech Univ Athens, Sch Elect & Comp Engn, Zografos 15780, Greece

[2] Czech Tech Univ, Fac Informat Technol, Dept Theoret Comp Sci, Prague, Czech Republic

[3] Athena Res Ctr, Archimedes Unit, Maroussi 15125, Greece

[4] PSL Univ, Univ Paris Dauphine, CNRS, UMR7243,LAMSADE, F-75016 Paris, France

来源：

ACTA INFORMATICA | 2024年 / 61卷 / 02期

关键词：

ALGORITHMS;

D O I：

10.1007/s00236-023-00451-7

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We present a new FPTAS for the Subset Sum Ratio problem, which, given a set of integers, asks for two disjoint subsets such that the ratio of their sums is as close to 1 as possible. Our scheme makes use of exact and approximate algorithms for Partition, and clearly showcases the close relationship between the two algorithmic problems. Depending on the relationship between the size of the input set n and the error margin epsilon , we improve upon the best currently known algorithm of Melissinos and Pagourtzis [COCOON 2018] of complexity O ( n 4 / epsilon ) . In particular, the exponent of n in our proposed scheme may decrease down to 2, depending on the Partition algorithm used.

引用

页码：101 / 113

页数：13

共 33 条

[1] SETH-based Lower Bounds for Subset Sum and Bicriteria Path
Abboud, Amir
Bringmann, Karl
Hermelin, Danny
Shabtay, Dvir
[J]. ACM TRANSACTIONS ON ALGORITHMS, 2022, 18 (01)
[2] Approximating Subset Sum Ratio via Subset Sum Computations
Alonistiotis, Giannis
Antonopoulos, Antonis
Melissinos, Nikolaos
Pagourtzis, Aris
Petsalakis, Stavros
Vasilakis, Manolis
[J]. COMBINATORIAL ALGORITHMS (IWOCA 2022), 2022, 13270 : 73 - 85
[3] Faster algorithms for k-subset sum and variations
Antonopoulos, Antonis
Pagourtzis, Aris
Petsalakis, Stavros
Vasilakis, Manolis
[J]. JOURNAL OF COMBINATORIAL OPTIMIZATION, 2023, 45 (01)
[4] Dense Subset Sum May Be the Hardest
Austrin, Per
Kaski, Petteri
Koivisto, Mikko
Nederlof, Jesper
[J]. 33RD SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2016), 2016, 47
[5] Subset Sum in the Absence of Concentration
Austrin, Per
Kaski, Petteri
Koivisto, Mikko
Nederlof, Jesper
[J]. 32ND INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2015), 2015, 30 : 48 - 61
[6] Efficient approximation algorithms for the SUBSET-SUMS equality problem
Bazgan, C
Santha, M
Tuza, Z
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2002, 64 (02) : 160 - 170
[7] DYNAMIC PROGRAMMING
BELLMAN, R
[J]. SCIENCE, 1966, 153 (3731) : 34 - &
[8] Bringmann K, 2021, Disc Algorithms, P1797
[9] Top-k-Convolution and the Quest for Near-Linear Output-Sensitive Subset Sum
Bringmann, Karl
Nakos, Vasileios
[J]. PROCEEDINGS OF THE 52ND ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (STOC '20), 2020, : 982 - 995
[10] Bringmann K, 2017, PROCEEDINGS OF THE TWENTY-EIGHTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P1073

← 1 2 3 4 →