Mathematics
Recent Submissions
-
Ivanović, Marija (Beograd , 2022)[more][less]
Abstract: This dissertation focuses on the Roman domination problem and its two modifications. Improvements and relaxations of two integer linear programming for- mulations for the Roman domination problem from the literature are introduced, proved to be equivalent to the existing ones despite of the variables relaxation and usage of fewer number of constraints and compared by standard optimization solvers, CPLEX and Gurobi. Improved formulations can be equally used as original ones, but, as it can be seen from numerical results, for some instances, they can be more useful. Given the fact that old and new formulations can not be used for some large size instances, and that algorithms for solving Roman domination problem are mostly defined for some particular graph classes, the aim of this research was to find a new algorithm that can be used for solving Roman domination problem on all graph classes and all graph sizes. Although the Roman domination problem belongs to the class NP, presented algorithm is able to find solution value equal to optimal solution value on very large number of instances in less then a second. For the first modification of the Roman domination problem, named Restrained Roman domination problem, a new mixed integer linear programming formulation is intro- duced and, to the best of the author’s knowledge, this formulation is the first in the literature. For the second modification of the Roman domination problem, the Weak Roman domination problem, an improved integer linear programming formu- lation is presented. Improved formulation is also proved to be correct, equivalent to the existing formulation from the literature and compared using standard op- timization solvers, CPLEX and Gurobi. Numerical results showed the advantage of the improved formulation on almost all tested instances. Additionally, an im- proved linear-time algorithm for solving the Weak Roman domination problem on block graphs is introduced and, similarly to the Roman domination problem, a new algorithm, based on the variable neighborhood search method is presented. With the new variable neighborhood search based algorithm we aimed to find solution of the Weak Roman domination problem equal to the optimal on very large number of tested instances. For instances for which some solution value is found but not proved to be an optimal, presented algorithm provided the new lower-bounds. Even more, for some instances, where optimization solvers were not able to prove optimality or to find any solution, new solutions are found. URI: http://hdl.handle.net/123456789/5431 Files in this item: 1
MarijaIvanovic_ ... a_saPotpisanimIzjavama.pdf ( 1.958Mb ) -
Jovanović Spasojević, Tanja (Beograd , 2022)[more][less]
Abstract: In this thesis, subjects of consideration are the embeddings theorems of weighted Bergman spaces in Lp-spaces, as well as embeddings theorems of harmonic mixed norm spaces. The first part of the thesis generalizes the theorems of embeddings Bergman spaces into Lp(μ)-spaces, where μ is a Borel measure on a given domain. They have been earlier studied on domains such as unit ball and upper half-space. Generalization refers to bounded domains Ω ⊂ Rn with C1 boundary. This embedding will be valid to any p > 0, whenever the measure of the spaces Lp satisfies the Carledon condition. Reverse the direction will be valid only in case if p > 1 + α+2 n−2 . The second part of the dissertation also generalizes the embeddings theorems of mixed norm spaces of harmonic functions on a unit ball, where the generalization is applied to the domain Ω ⊂ Rn with C1 boundary. However, in addition we are obtaining another important result relating to the limitation of the maximum operators in the mixed norm on the general domain for the class of QNS functions. URI: http://hdl.handle.net/123456789/5378 Files in this item: 1
Jovanovic_Spasojevic_Tanja.pdf ( 1.643Mb ) -
Stakić, Đorđe (Beograd , 2022)[more][less]
Abstract: Intermodal transport involves traffic with more than one type of trans port. Its presence in practice has become very significant. Bearing in mind that these are mostly long distances, optimization has become important in this area. By default, three standard types of containers of different sizes are used for the transport. In accordance with the given criteria adequate mathematical models have been developed. Based on the model, the exact solver CPLEX was programmed, which succeeds to find the optimal solutions for lesser values of the input parameters. For a number of models, solutions have been implemented in the C programming language. The input data for smaller instances was taken from the practice. To test instances of larger size, the input data is randomly generated from the selected domain. In the first part of this work the main focus is the search for the optimal route in transportation, according to the given criteria, which includes ocean and mainland transport. The problem becomes more complex by increasing the number of shipping companies, the number of side ports, as well as the number of modes of transport on land. In the second part of the paper, additional problems related to the optimization of intermodal transport are considered. More attention is paid to the individual packages by considering the mass and volume of the package, and sub sequently the limits of mass and volume of the containers. One of solved problems is related to the deployment of a large pack in several containers, then the selection of optimal allocation in accordance with the set criteria. The second solved problem is from the aggregate container transport and it is related to the deployment of a large number of packages into containers, taking the constraints of mass and volume into consideration. Here we also seek an optimal allocation in accordance with the set criteria, eg. the total minimum price. The problem thus considered to belong to the heterogeneous and homogeneous vector bin packing. The numerous com puter implementations of exact and approximate methods for the different models are made. Variant methods of Variable Neighborhood Search (VNS) and GRASP (Greedy Randomized Adaptive Search Procedures) have been designed to optimize the aggregate container transport. These approximation methods were compared with each other as well as with solutions obtained by exact solver CPLEX. URI: http://hdl.handle.net/123456789/5377 Files in this item: 1
DjordjeStakicDisertacija.pdf ( 1.629Mb ) -
Lazarević, Ivan (Beograd , 2022)[more][less]
Abstract: In this doctoral thesis we obtained some results in graph theory and its applica tions. In the rst chapter, we give the review of basic notions and theorems of combinatorial theory of graphs, spectral theory of graphs, random graphs and distribution of their eigenvalues. The most detailed consideration is given to adjacency matrix and properties of its spectrum. In particular, in this dissertation we study Energy of graphs and generalizations of it. Energy of graph is the sum of absolute values of eigenvalues of a graph. Schatten norms of graphs represent p-th degree norm of singular values of graph, and the special cases of this norm for p = 1 corresponds to the Energy of graph. In chapter three of this dissertation we are given the most original scienti c contribution. We prove the conjecture of Nikiforov about Schatten norms of graphs when p > 2. First we prove that conjecture is true for some special classes of graph (for trees and strongly regular graph with maximal energy). After that, we prove the conjecture in the general case. Auxiliary theorem obtained in the proof of this conjecture is also an original result which gives a sharp upper bound of sum of quadratic of the largest k singular values of graph. A corollary of this theorem which gives an upper bound for sum of squares of the biggest two singular values of graph can be useful in further research. In the subsection 3.3 we give an original theorem about asymptotic properties of spectrum and thus energy of complement graph for a large values of n. In the subsection 3.4 we calculate a mean of p-th degree of singular values and upper bound of geometric mean of almost all graphs. The last chapter shows relation between combinatorial theory of graphs with universal universal algebra and mathematical logic. The central part of this chapter is original and shorter proof of an important theorem which solves a dichotomy conjecture for CSP problem on undirected graphs. URI: http://hdl.handle.net/123456789/5371 Files in this item: 1
Ivan_teza20042022.pdf ( 1.428Mb ) -
Telebaković Onić, Sonja (Beograd , 2022)[more][less]
Abstract: n this dissertation the connection between Frobenius algebras and topological quantum field theories (TQFTs) is investigated. It is well-known that each 2-dimensional TQFT (2-TQFT) corresponds to a commutative Frobenius algebra and conversely, i.e., that the category whose objects are 2-TQFTs is equivalent to the category of commutative Frobe- nius algebras. Every 2-TQFT is completely determined by the image of 1-dimensional sphere S1 and by its values on the generators of the category of 2-dimensional oriented cobordisms. Relations that hold for these cobordisms correspond precisely to the axioms of a commutative Frobenius algebra. Following the pattern of the Frobenius structure assigned to the sphere S1 in this way, we examine the Frobenius structure of spheres in all other dimensions. For every d ≥ 2, the sphere Sd−1 is a commutative Frobenius object in the category of d-dimensional cobordisms. We prove that there is no distinction between spheres Sd−1, for d ≥ 2, because they are all free of additional equations formulated in the language of multiplication, unit, comultiplication and counit. The only exception is the sphere S0 which is a symmetric Frobenius object but not commutative. The sphere S0 is mapped to a matrix Frobenius algebra by the Brauerian representation, which is an example of a faithful 1-TQFT functor. We obtain the faithfulness result for all 1-TQFTs, mapping the 0-dimensional manifold, consisting of one point to a vector space of dimension at least 2. Finally, we show that the commutative Frobenius algebra QZ5 ⊗ Z(QS3), defined as the ten- sor product of the group algebra and the centre of the group algebra, corresponds to the faithful 2-TQFT. It means that 2-dimensional cobordisms are equivalent if and only if the corresponding linear maps are equal. URI: http://hdl.handle.net/123456789/5353 Files in this item: 1
stoDisertacijaOnic.pdf ( 9.095Mb )