Approximating subset sum ratio via subset sum computations

DOI10.1007/978-3-031-06678-8_6OpenAlexW4285259423MaRDI QIDQ2169941

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

Publication date: 30 August 2022

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

zbMATH Keywords

combinatorial optimizationapproximation schemeknapsack problems\textsc{subset sum ratio}\textsc{subset sum}

Mathematics Subject Classification ID

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

Related Items (1)

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

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
• An efficient fully polynomial approximation scheme for the Subset-Sum problem.
• Efficient approximation algorithms for the subset-sums equality problem.
• A faster FPTAS for the subset-sums ratio problem
• Approximation schemes for subset sum ratio problems
• Simple FPTAS for the subset-sums ratio problem
• Computing Partitions with Applications to the Knapsack Problem
• A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum
• Dense Subset Sum may be the hardest
• On Problems Equivalent to (min,+)-Convolution
• 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
• SETH-Based Lower Bounds for Subset Sum and Bicriteria Path
• A Subquadratic Approximation Scheme for Partition
• Fundamentals of Computation Theory
• LATIN 2004: Theoretical Informatics

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