Approximating subset sum ratio via subset sum computations

DOI10.1007/978-3-031-06678-8_6MaRDI QIDQ2169941zbMATH OpenOpenAlexFDO

Authors Giannis Alonistiotis, Antonis Antonopoulos, Nikolaos Melissinos, Aris Pagourtzis, Stavros Petsalakis, Manolis Vasilakis

Publication date 30 August 2022

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

zbMATH Keywords

\textsc{subset sum ratio}\textsc{subset sum}approximation schemecombinatorial optimizationknapsack problems

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Cites work

• A faster FPTAS for the subset-sums ratio problem
• A near-linear pseudopolynomial time algorithm for subset sum
• A subquadratic approximation scheme for partition
• An efficient fully polynomial approximation scheme for the Subset-Sum problem.
• Approximation schemes for subset sum ratio problems
• Composing equipotent teams.
• Computing Partitions with Applications to the Knapsack Problem
• Dense subset sum may be the hardest
• Efficient approximation algorithms for the subset-sums equality problem.
• Equal-subset-sum faster than the meet-in-the-middle
• Faster Pseudopolynomial Time Algorithms for Subset Sum
• scientific article; zbMATH DE number 3126094 (Why is no real title available?)
• LATIN 2004: Theoretical Informatics
• Linear Time Algorithms for Knapsack Problems with Bounded Weights
• On problems equivalent to \((\min,+)\)-convolution
• On the complexity of the parity argument and other inefficient proofs of existence
• On the complexity of variations of equal sum subsets
• On the equal-subset-sum problem
• Reducibility among combinatorial problems
• SETH-based lower bounds for subset sum and bicriteria path
• Simple FPTAS for the subset-sums ratio problem
• Subset sum in the absence of concentration
• Top-𝑘-convolution and the quest for near-linear output-sensitive subset sum

Cited in

(3)

• Faster algorithms for \(k\)-subset sum and variations
• Consistent subsets: computationally feasible methods to compute the Houtman-Maks-index
• Approximating subset sum ratio via partition computations

Describes a project that uses

Uses Software

• Knapsack

This page was built for publication: Approximating subset sum ratio via subset sum computations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2169941)