Back to search

National and Kapodistrian University of Athens

Μελέτη και επίλυση πολυωνυμικών συστημάτων με χρήση αλγεβρικών και συνδυαστικών μεθόδων

Abstract

dc:description

The contribution of the thesis is threefold. We worked on Problems in the areas of algebraic algorithms, computational geometry and algebraic combinatorics. The first Problem is computing the discriminant, when the system’s dimension varies. Thus solving polynomial equations and systems by exploiting the structure and sparseness of them have been studied. Specifically, closed formulas for the degree of the sparse (mixed) discriminant and the sparse resultant of polynomial equations have been studied, as well as relationships between them. Closed formulas when one of the polynomials factors in the context of the theory of sparse elimination using the Newton polytope have been proposed. The main purpose is to facilitate the computation of the sparse (or mixed) discriminant of a well-constrained polynomial system and to generalize the formula that connects the mixed discriminant with the sparse resultant. The results of this work are presented in Chapter 4 and 6 of the thesis and have been published in [39] and [29] . In Chapter 5 we are given a system of n ⩾ 2 homogeneous polynomials in n variables which is equivariant with respect to the symmetric group of n symbols. We then prove that its resultant can be decomposed into a product of several resultants that are given in terms of some divided differences. As an application, we obtain a decomposition formula for the discriminant of a multivariate homogeneous symmetric polynomial. The results of this work have been published in [14].The second Problem is computing the Minkowski decomposition of a polytope and the third one was the problem of Multidimensional Subset Sum (kD-SS) in arbitrary dimension.Firstly, we present an algorithm for computing all Minkowski Decompositions (MinkDecomp) of a given convex, integral d-dimensional polytope, using the cone of combinatorially equivalent polytopes. An implementation is given in sage. The results of this work are presented in Chapter 7 of the thesis and have been published in [36] .Secondly, 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, a multiset S of k-dimensional vectors is given, along with a target vector t, and one must decide whether there exists a subset of S that sums up to t. We prove, through a gap-preserving reduction from Set Cover that, for general dimension k, the corresponding optimization problem kD-SS-opt is not in APX, although the classic 1D-SS-opt has a PTAS. Our approach relates kD-SS with the well studied Closest Vector Problem. On the positive side, we present a O(n3/ϵ2) approximation algorithm for 2D-SS-opt, where n is the cardinality of the multiset and ϵ > 0 bounds the additive error in terms of some property of the input. We state two variations of this algorithm, which are more suitable for implementation. Employing a reduction of the optimization version of MinkDecomp to 2D-SS-opt we approximate the former: For an input polygon Q and parameter ϵ > 0, we compute summand polygons A and B, where Q′ = A + B is such that some geometric function differs on Q and Q′ by O(ϵD), where D is the diameter of Q, or the Hausdorff distance between Q and Q′ is also in O(ϵD). We conclude with experimental results based on our implementations. The results of this work are presented in Chapter 8 of the thesis and have been published in [41],[40].Finally, in Chapter 9 we provide extensions and open problems.

Degree

thesis:*
Grantor dc:publisher
National and Kapodistrian University of Athens
Year dc:date
2017

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Karasoulou, Anna
  • Καρασούλου, Άννα

Subjects

dc:subject × 16

Rights

dc:rights
Statement dc:rights
  • BY_NC_ND
Language dc:language
gre

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/45663

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Karasoulou, Anna; Καρασούλου, Άννα. Μελέτη και επίλυση πολυωνυμικών συστημάτων με χρήση αλγεβρικών και συνδυαστικών μεθόδων. National and Kapodistrian University of Athens, 2017. http://hdl.handle.net/10442/hedi/45663