Faster algorithms for \(k\)-subset sum and variations

DOI10.1007/s10878-022-00928-0OpenAlexW4311064408MaRDI QIDQ2105266

Antonis Antonopoulos, Stavros Petsalakis, Aris Pagourtzis, Manolis Vasilakis

Publication date: 8 December 2022

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2112.04244

zbMATH Keywords

FFTsubset sumcolor codingpseudopolynomial algorithmsmultiple subset summultiple knapsack\(k\)-subset sum

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the equal-subset-sum problem
• On the complexity of the parity argument and other inefficient proofs of existence
• A 3/4-approximation algorithm for multiple subset sum
• A PTAS for the multiple subset sum problem with different knapsack capacities
• Efficient approximation algorithms for the subset-sums equality problem.
• An exact approach for the balanced \(k\)-way partitioning problem with weight constraints and its application to sports team realignment
• Mathematical models and decomposition methods for the multiple knapsack problem
• A faster FPTAS for the subset-sums ratio problem
• Approximating subset sum ratio via subset sum computations
• Simple FPTAS for the subset-sums ratio problem
• Finding witnesses by peeling
• Asymptotic Analysis of an Algorithm for Balanced Parallel Processor Scheduling
• A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum
• Optimal Multi-Way Number Partitioning
• Linear Time Algorithms for Knapsack Problems with Bounded Weights
• Faster Pseudopolynomial Time Algorithms for Subset Sum
• Reducibility among Combinatorial Problems
• Top-𝑘-convolution and the quest for near-linear output-sensitive subset sum
• Fundamentals of Computation Theory
• LATIN 2004: Theoretical Informatics
• SETH-based Lower Bounds for Subset Sum and Bicriteria Path
• Faster algorithms for \(k\)-\textsc{Subset Sum} and variations

This page was built for publication: Faster algorithms for \(k\)-subset sum and variations