Faster algorithms for \(k\)-subset sum and variations
From MaRDI portal
Publication:2105266
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
FFTsubset sumcolor codingpseudopolynomial algorithmsmultiple subset summultiple knapsack\(k\)-subset sum
Uses Software
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
