Approximating multidimensional subset sum and Minkowski decomposition of polygons
From MaRDI portal
Publication:2364904
DOI10.1007/s11786-017-0297-1zbMath1409.68330OpenAlexW2602945922WikidataQ57908646 ScholiaQ57908646MaRDI QIDQ2364904
Ioannis Z. Emiris, Charilaos Tzovas, Anna Karasoulou
Publication date: 25 July 2017
Published in: Mathematics in Computer Science (Search for Journal in Brave)
Full work available at URL: https://hal.inria.fr/hal-01401896/file/ApprMinkDecomp_mcs_EKT.pdf
implementationapproximation algorithmsexperimental resultsMinkowski decompositionmultidimensional subset sum
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Related Items
Approximating multidimensional subset sum and Minkowski decomposition of polygons, A heuristic technique for decomposing multisets of non-negative integers according to the Minkowski sum
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- There is no EPTAS for two-dimensional knapsack
- On multiplication and factorization of polynomials. II: Irreducibility discussion
- The hardness of approximate optima in lattices, codes, and systems of linear equations
- Integral decomposition of polyhedra and some applications in mixed integer programming
- Approximating CVP to within almost-polynomial factors is NP-hard
- Approximating multidimensional subset sum and Minkowski decomposition of polygons
- Approximate factorization of multivariate polynomials using singular value decomposition
- A Note on Approximation Schemes for Multidimensional Knapsack Problems
- 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 Faster Pseudopolynomial Time Algorithm for Subset Sum
- A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum
- Factoring polynomials via polytopes
- Efficient probabilistically checkable proofs and applications to approximations
- Absolute irreducibility of polynomials via Newton polytopes
- Decomposition of polytopes and polynomials
