Approximating multidimensional subset sum and Minkowski decomposition of polygons

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

zbMATH Keywords

implementationapproximation algorithmsexperimental resultsMinkowski decompositionmultidimensional subset sum

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Related Items (2)

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

This page was built for publication: Approximating multidimensional subset sum and Minkowski decomposition of polygons