On the equal-subset-sum problem

DOI10.1016/0020-0190(92)90226-LMaRDI QIDQ1198083zbMATH OpenOpenAlexFDO

Authors Zhongliang Yu, Gerhard J. Woeginger

Publication date 16 January 1993

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(92)90226-l

zbMATH Keywords

approximation algorithmNP-completeness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05)

Recommendations

• Efficient approximation algorithms for the subset-sums equality problem.
• On the complexity of variations of equal sum subsets
• Publication:4219034
• Two linear approximation algorithms for the subset-sum problem
• On the hardness of finding subsets with equal average

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Sets of Integers Whose Subsets Have Distinct Sums

Cited in

(35)

• On vertex-weighted realizations of acyclic and general graphs
• Envy-free revenue approximation for asymmetric buyers with budgets
• Fair draws for group rounds in sport tournaments
• Approximating subset sum ratio via subset sum computations
• On vertex-weighted graph realizations
• Partial digest is hard to solve for erroneous input data
• Subset sum problems with digraph constraints
• Approximation schemes for subset-sums ratio problems
• Polynomially ambiguous probabilistic automata on restricted languages
• Cutting stock with no three parts per pattern: work-in-process and pattern minimization
• Covering a set with arithmetic progressions is NP-complete
• Composing equipotent teams.
• Shifted varieties and discrete neighborhoods around varieties
• On envy-free revenue approximation for combinatorial buyers with budgets
• Polynomially Ambiguous Probabilistic Automata on Restricted Languages
• On the complexity of variations of equal sum subsets
• ABOUT THE CONP-COMPLETE “INJECTIVE KNAPSACK” PROBLEM
• Mixed integer reformulations of integer programs and the affine TU-dimension of a matrix
• Approximability of the subset sum reconfiguration problem
• On the hardness of finding subsets with equal average
• Decision problems for some classes of integer partitions and number multisets
• Approximating subset sum ratio via partition computations
• Motion planning with pulley, rope, and baskets
• The $k$ -Equal Problem
• One-dimensional stock cutting resilient against singular random defects
• scientific article; zbMATH DE number 7525510 (Why is no real title available?)
• Efficient approximation algorithms for the subset-sums equality problem.
• Faster algorithms for \(k\)-subset sum and variations
• Simple FPTAS for the subset-sums ratio problem
• Matrix semigroup freeness problems in \(\mathrm{SL}(2,\mathbb {Z})\)
• Vector ambiguity and freeness problems in \(\mathrm{SL} (2,\mathbb {Z})\)
• scientific article; zbMATH DE number 7456121 (Why is no real title available?)
• Faster algorithms for \(k\)-\textsc{Subset Sum} and variations
• Preprocessing and cut generation techniques for multi-objective binary programming
• Some algorithmic results for [2]-sumset covers

This page was built for publication: On the equal-subset-sum problem

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