Faster algorithms for \(k\)-\textsc{Subset Sum} and variations

DOI10.1007/978-3-030-97099-4_3OpenAlexW4214930793MaRDI QIDQ6113909

Manolis Vasilakis, Stavros Petsalakis, Aris Pagourtzis, Antonis Antonopoulos

Publication date: 10 August 2023

Published in: Frontiers of Algorithmics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-97099-4_3

zbMATH Keywords

FFTcolor codingpseudopolynomial algorithmsmultiple knapsack\textsc{Subset Sum}multiple \textsc{Subset Sum}

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)

Related Items (1)

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

Cites Work

• 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.
• Mathematical models and decomposition methods for the multiple knapsack problem
• A faster FPTAS for the subset-sums ratio problem
• Simple FPTAS for the subset-sums ratio problem
• Finding witnesses by peeling
• A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum
• Linear Time Algorithms for Knapsack Problems with Bounded Weights
• Faster Pseudopolynomial Time Algorithms for Subset Sum
• Top-𝑘-convolution and the quest for near-linear output-sensitive subset sum
• Fundamentals of Computation Theory
• LATIN 2004: Theoretical Informatics
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Faster algorithms for \(k\)-\textsc{Subset Sum} and variations