Font size: Αα Αα Αα hide gadgets
You are here: Theses » MSc » Tzovas Harilaos Anonymously browsing from at 21:21:17, 23-09-2017. login

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 thesis.


Page updates

No recent updates.

Feeds RSS and Atom feeds

all posts RSS
news RSS
announcements RSS
website news RSS
all events RSS
defenses RSS
exams RSS
seminars RSS
graduations RSS
Web standards: XHTML1.0, CSS3.
© 1996 – 2017 MPLA: Graduate program in Logic, Algorithms and Computation.
Contact the webmaster.