Back to search

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

Chain of custody

source
Harvested from
National and Kapodistrian University of Athens
Base URL
pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Τζόβας Χαρίλαος. Approximating Minkowski Decomposition and 2D Subset Sum. 2016. https://pergamos.lib.uoa.gr/uoa/dl/object/1320897