{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:1320897"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:1320897","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Approximating Minkowski Decomposition and 2D Subset Sum","abstract":"Θεωρούμε 2 NP-complete προβλήματα: την Διασπαση Minkowski όπου, δοσμένου ενός πολυγώνου, ψάχνουμε 2 πολύγωνα των οποίων το άθροισμα Minkowski δίνει το αρχικό, και το Δισδιάστατο Άθροισμα Υποσυνόλου όπου μας δίνονται ενα σύνολο διανυσμάτων S στον χώρο και ένας στόχος t και ψάχνουμε ένα υποσύνολο του S που να αθροίζει στο t. Τα δύο πρόβληματα αυτά συνδέονται με πολυώνυμα μέσω των Newton πολυτόπων ενός πολυωνύμου και σχετίζονται με την παραγοντοποίηση πολυωνύμων. Στην παρούσα εργασία λύνουμε τα προβλήματα με προσεγγιστικούς αλγορίθμους σε πολυωνυμικό χρόνο και παρουσιάζουμε ένα αποτέλεσμα για την δυσκολία προσέγγισης του Δισδιάστατου Υποσυνόλου για γενική διάσταση.","abstract_html":"Θεωρούμε 2 NP-complete προβλήματα: την Διασπαση Minkowski όπου, δοσμένου ενός πολυγώνου, ψάχνουμε 2 πολύγωνα των οποίων το άθροισμα Minkowski δίνει το αρχικό, και το Δισδιάστατο Άθροισμα Υποσυνόλου όπου μας δίνονται ενα σύνολο διανυσμάτων S στον χώρο και ένας στόχος t και ψάχνουμε ένα υποσύνολο του S που να αθροίζει στο t. Τα δύο πρόβληματα αυτά συνδέονται με πολυώνυμα μέσω των Newton πολυτόπων ενός πολυωνύμου και σχετίζονται με την παραγοντοποίηση πολυωνύμων. Στην παρούσα εργασία λύνουμε τα προβλήματα με προσεγγιστικούς αλγορίθμους σε πολυωνυμικό χρόνο και παρουσιάζουμε ένα αποτέλεσμα για την δυσκολία προσέγγισης του Δισδιάστατου Υποσυνόλου για γενική διάσταση.","abstract_has_math":false,"creators":["Τζόβας Χαρίλαος"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2016,"date_issued":"2016","date_published":"2016","updated_at":"2026-11-19T05:26:32Z","subjects":[],"languages":["English"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1320897"],"render_values":[{"text":"uoadl:1320897","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1320897","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1320897","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Alib.uoa.gr%3Auoadl%3A1320897","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Τζόβας Χαρίλαος"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2016"]},{"key":"dc:type","label":"Dc Type","values":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1320897","https://pergamos.lib.uoa.gr/uoa/dl/object/1320897"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Θεωρούμε 2 NP-complete προβλήματα: την Διασπαση Minkowski όπου, δοσμένου ενός πολυγώνου, ψάχνουμε 2 πολύγωνα των οποίων το άθροισμα Minkowski δίνει το αρχικό, και το Δισδιάστατο Άθροισμα Υποσυνόλου όπου μας δίνονται ενα σύνολο διανυσμάτων S στον χώρο και ένας στόχος t και ψάχνουμε ένα υποσύνολο του S που να αθροίζει στο t. Τα δύο πρόβληματα αυτά συνδέονται με πολυώνυμα μέσω των Newton πολυτόπων ενός πολυωνύμου και σχετίζονται με την παραγοντοποίηση πολυωνύμων. Στην παρούσα εργασία λύνουμε τα προβλήματα με προσεγγιστικούς αλγορίθμους σε πολυωνυμικό χρόνο και παρουσιάζουμε ένα αποτέλεσμα για την δυσκολία προσέγγισης του Δισδιάστατου Υποσυνόλου για γενική διάσταση.","We consider the approximation of two NP-hard problems: Minkowski Decomposition (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(n^3/e^2) approximation algorithm for 2D-SS, where n is the cardinality of the set and e bounds the difference of some measure of the input polygon and the sum of the output polygons. Applying this algorithm, and a transformation from MinkDecomp to 2D-SS, we can approximate MinkDecomp. For an input polygon Q and parameter e, 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 additive error linear in e 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."]},{"key":"dc:title","label":"Title","values":["Approximating Minkowski Decomposition and 2D Subset Sum"]}]}],"canonical_facts":{"dc:creator":["Τζόβας Χαρίλαος"],"dc:date":["2016"],"dc:description":["Θεωρούμε 2 NP-complete προβλήματα: την Διασπαση Minkowski όπου, δοσμένου ενός πολυγώνου, ψάχνουμε 2 πολύγωνα των οποίων το άθροισμα Minkowski δίνει το αρχικό, και το Δισδιάστατο Άθροισμα Υποσυνόλου όπου μας δίνονται ενα σύνολο διανυσμάτων S στον χώρο και ένας στόχος t και ψάχνουμε ένα υποσύνολο του S που να αθροίζει στο t. Τα δύο πρόβληματα αυτά συνδέονται με πολυώνυμα μέσω των Newton πολυτόπων ενός πολυωνύμου και σχετίζονται με την παραγοντοποίηση πολυωνύμων. Στην παρούσα εργασία λύνουμε τα προβλήματα με προσεγγιστικούς αλγορίθμους σε πολυωνυμικό χρόνο και παρουσιάζουμε ένα αποτέλεσμα για την δυσκολία προσέγγισης του Δισδιάστατου Υποσυνόλου για γενική διάσταση.","We consider the approximation of two NP-hard problems: Minkowski Decomposition (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(n^3/e^2) approximation algorithm for 2D-SS, where n is the cardinality of the set and e bounds the difference of some measure of the input polygon and the sum of the output polygons. Applying this algorithm, and a transformation from MinkDecomp to 2D-SS, we can approximate MinkDecomp. For an input polygon Q and parameter e, 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 additive error linear in e 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."],"dc:identifier":["uoadl:1320897","https://pergamos.lib.uoa.gr/uoa/dl/object/1320897"],"dc:language":["English"],"dc:title":["Approximating Minkowski Decomposition and 2D Subset Sum"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T05:26:32Z"}