Approximation schemes for subset-sums ratio problems

DOI10.1016/j.tcs.2022.07.027OpenAlexW4288740168WikidataQ114129063 ScholiaQ114129063MaRDI QIDQ2167894

Nikolaos Melissinos, Aris Pagourtzis, Theofilos Triommatis

Publication date: 1 September 2022

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2022.07.027

zbMATH Keywords

combinatorial optimizationapproximation schemeknapsack problemssubset-sums ratio

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• 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.
• Subset sum problems with digraph constraints
• A faster FPTAS for the subset-sums ratio problem
• Approximation schemes for a class of subset selection problems
• Simple FPTAS for the subset-sums ratio problem
• Algorithms for Scheduling Independent Tasks
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• Computing Partitions with Applications to the Knapsack Problem
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?
• A Subquadratic Approximation Scheme for Partition
• Fundamentals of Computation Theory
• LATIN 2004: Theoretical Informatics

This page was built for publication: Approximation schemes for subset-sums ratio problems