National and Kapodistrian University of Athens
Approximating Minkowski Decomposition and 2D Subset Sum
Abstract
dc:descriptionΘεωρούμε 2 NP-complete προβλήματα: την Διασπαση Minkowski όπου, δοσμένου ενός πολυγώνου, ψάχνουμε 2 πολύγωνα των οποίων το άθροισμα Minkowski δίνει το αρχικό, και το Δισδιάστατο Άθροισμα Υποσυνόλου όπου μας δίνονται ενα σύνολο διανυσμάτων S στον χώρο και ένας στόχος t και ψάχνουμε ένα υποσύνολο του S που να αθροίζει στο t. Τα δύο πρόβληματα αυτά συνδέονται με πολυώνυμα μέσω των Newton πολυτόπων ενός πολυωνύμου και σχετίζονται με την παραγοντοποίηση πολυωνύμων. Στην παρούσα εργασία λύνουμε τα προβλήματα με προσεγγιστικούς αλγορίθμους σε πολυωνυμικό χρόνο και παρουσιάζουμε ένα αποτέλεσμα για την δυσκολία προσέγγισης του Δισδιάστατου Υποσυνόλου για γενική διάσταση.
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Τζόβας Χαρίλαος
Rights
- Language dc:language
- English
Identifiers
dc:identifier.*- Identifier
- uoadl:1320897