Domagoj Ševerdija

 

Assistant Professor
Department of Mathematics
Josip Juraj Strossmayer University of Osijek
Trg Ljudevita Gaja 6
Osijek, HR-31000, Croatia¸
phone: +385-31-224-823
fax: +385-31-224-801
email: Ova e-mail adresa je zaštićena od spambota. Potrebno je omogućiti JavaScript da je vidite.
office:  823 (ground floor)

 


Research Interests

Combinatorial Optimization
Computational Geometry
Parallel Computing
Data Processing

Degrees

PhD in Electrical Engineering, ETFOS, University in Osijek, Croatia, 2013. [disertacija]
BS in Mathematics and Computer Science, Department of Mathematics, University of Osijek, Croatia, 2007.

Publications

Journal Publications

  1. S. Jelić, D. Ševerdija, Government Formation Problem, Central European Journal of Operations Research (2017), prihvaćen za objavljivanje
    In addition to the same political and ideological attitudes, members of political parties can be interconnected at private and/or professional levels. They are considered as a part of one large social network. After democratic elections, the total effectiveness and stability of a government may depend on expertness and cooperability of its members. Our main goal is not to give a mechanism for pre-elective government formation, but to propose a model that decides what can be a good subset of candidates for positions in the new government. The decision is based on expertness of candidates and their interconnections in the social network. Inspired by the team formation problem in a social network, we present a Government Formation Problem (GFP). We prove that this problem is NP-hard and give an algorithm based on integer linear programming formulation. In the experimental part, we test our algorithm on simulated data using the GUROBI MILP solver.
  2. D. Matijević, D. Ševerdija, G. Martinović, Efficient Implementations of Guarding 1.5D Terrains, Croatian Operational Research Review 6/1 (2015), 79-89
    In 1.5D Terrain Guarding Problem we are given an $x$-monotone polygonal line defined by $k$ vertices and a set $G$ of points from the terrain, i.e. guards, and a set $N$ of points from the terrain which are to be seen (guarded) by guards. We deal with a weighted version of the guarding problem where guards $G$ have weights and the goal is to find a minimum weight subset of $G$ to cover, and a version of the problem where points from $N$ have demands, and the goal is to find the smallest subset from $G$ such that every point in $N$ is seen by the demanded number of guards. Both problems are NP-hard and have a factor $5$ approximation (cite{journals/alg/Elbassioni08}, cite{journal/Elbassioni12}). We show that if $(1+epsilon)$-approximate solver to the corresponding linear program is a computer, for any $epsilon>0$, an extra $1+epsilon$ factor will appear in the final approximation factor for both problems. We compare our parallel implementation based on GPU and CPU threads with textsc{Gurobi} solver and conclude that our algorithm outperforms Gurobi solver on large and dense inputs typically by one order of magnitude.
  3. K. Elbassioni, D. Matijević, D. Ševerdija, Guarding 1.5D Terrains with Demands, International Journal of Computer Mathematics 89/16 (2012), 2143-2151
    In this paper, we consider the 1.5D terrain guarding problem in which every point on the terrain that is to be covered has an integer demand associated with it. The goal is to find a minimum cardinality set of guards such that each point is guarded by a number of guards satisfying its demand. We present a first constant-factor approximation algorithm for the problem, that is, a $(1+1/d_min)$-approximation algorithm, where $d_min$ is a minimum demand. The algorithm is based on solving appropriate subproblems established by a decomposition of the main problem due to linear programming relaxation of the corresponding covering problem.
  4. K. Elbassioni, E. Krohn, D. Matijević, J. Mestre, D. Ševerdija, Improved Approximations for Guarding 1.5-Dimensional Terrains, Algorithmica 60/2 (2011), 451-463
    We present a 4-approximation algorithm for the problem of placing the fewest guards on a 1.5D terrain so that every point of the terrain is seen by at least one guard. This improves on the currently best approximation factor of 5. Unlike most of the previous techniques, our method is based on rounding the linear programming relaxation of the corresponding covering problem. Besides the simplicity of the analysis, which mainly relies on decomposing the constraint matrix of the LP into totally balanced matrices, our algorithm, unlike previous work, generalizes to the weighted and partial versions of the basic problem.
  5. F. Belić, Ž. Hocenski, D. Ševerdija, Naive Matrix Multiplication versus Strassen Algorithm in Multi-thread Environment, Tehnički vjesnik 18/3 (2011), 309-314
    n last few decades computational power of computers has greatly increased. Highest speeds and power are still reserved for super-computers, but high-speed computers have been available for home and amateur users for some time. Normal user most of the time uses only a small amount of computational resources available ; even in cases of high-strain, a good part of these resources stays unused. This is partly a result of poor programming. Most of programmers still use single- threaded programming although platforms for parallel programming have been widely available for long time. This article describes using one such platform (.NET Framework) to decrease time needed for multiplication of matrices. This article tries to present what results can be achieved using common equipment and easily acquirable software.


Others

  1. D. Matijević, D. Ševerdija, S. Jelić, L. Borozan, Uparena optimizacijska metoda, Math.e : hrvatski matematički elektronski časopis 30 (2016)
    U ovom članku analiziramo metode gradijentnog i zrcalnog spusta u području konveksne optimizacije s danim naglaskom na njihove brzine konvergencije. Nadalje, uparujući dvije spomenute metode dobivamo takozvanu uparenu metodu čija analiza konvergencije pokazuje ubrzanje u odnosu na gradijentnu i zrcalnu metodu, te bilo koju drugu nama poznatu metodu prvoga reda.
  2. D. Ševerdija, I. Matić, Grčko - kineski stil u teoriji brojeva, Osječki matematički list 10/1 (2010), 43-58
  3. D. Ševerdija, I. Matić, Metodički aspekti abakusa II, Matematika i škola 53 (2010), 106-111
  4. D. Matijević, D. Ševerdija, Problem vidljivosti, Osječki matematički list (2010), prihvaćen za objavljivanje
    Za dvije točke kažemo da vide jedna drugu ukoliko ne postoji prepreka koja bi presjecala segment koji ih spaja. Na temelju geometrijskog modela predstaviti ćemo klasične probleme vidljivosti kao što su problem galerije, problem utvrde i problem čuvanja terena. Iznosimo osnovne rezultate vezane uz spomenute probleme i neke od varijacija tih problema.
  5. D. Ševerdija, I. Matić, Metodički aspekti abakusa I, Matematika i škola 52 (2009), 57-62
  6. I. Matić, D. Ševerdija, S. Škorvaga, Numerička ograničenja kineskog abakusa, Osječki matematički list 9 (2009), 75-91
    We present some aspects of numerical constraints using chinese abacus in standard arithmetic operations with natural numbers.



Projects

 

 


Professional Activities

Editorial Boards

 


 

Committee Memberships

 


 

Refereeing/Reviewing

 


 

Service Activities

 


Teaching

Konzultacije (Office Hours): Srijeda (Wed) 10:00am-12:30pm, Četvrtak (Thu) 10:00am-12:30pm. Konzultacije su moguće i po dogovoru.

I017 Uvod u računalne mreže i usluge (Introduction to Computer Networks and Services)

I011 Uvod u strukture podataka i algoritme (Introduction to Data Structures and Algorithms)

I019 Složenost algoritama (Introduction to Data Structures and Algorithms)

 


Personal

Here goes the private stuff.