mpla.math.uoa.gr
Font size: Αα Αα Αα hide gadgets
You are here: Theses » MSc » Tzovas Harilaos

MSc thesis of Tzovas Harilaos

Approximating Minkowski Decomposition and 2D Subset Sum

Supervisor: Ioannis Emiris

We consider the approximation of two NP-hard problems: Minkowski Decom- position (MinkDecomp) of lattice polygons in the plane and the closely related problem of Multidimensional Subset Sum (kD-SS) in arbitrary dimension. In kD- SS we are given an input set S of k-dimensional vectors, a target vector t and we ask if there exists a subset of S that sums to t. We prove, through a gap-preserving reduction, that, for general dimension k, kD-SS does not have a PTAS although the classic 1D-SS does. On the positive side, we present an O(n3/ε2) approximation al- gorithm for 2D-SS, where n is the cardinality of the set and ε bounds the difference of some measure of the input polygon and the sum of the output polygons. Ap- plying this algorithm, and a transformation from MinkDecomp to 2D-SS, we can approximate MinkDecomp. For an input polygon Q and parameter ε, we return two summands A and B such that A + B = Q′ with Q′ being bounded in relation to Q in terms of volume, perimeter, or number of internal lattice points and an ad- ditive error linear in ε and up to quadratic in the diameter of Q. A similar function bounds the Hausdorff distance between Q and Q′. We offer experimental results based on our implementation which is openly provided via Github.

Defended: June 6, 2016.

Scientific committee

Download

Download thesis.

Reporter

Web standards: XHTML1.0, CSS3.
© 1996 – 2018 MPLA: Graduate program in Logic, Algorithms and Computation.
Contact the webmaster.