Domagoj Matijević
Associate Professor Department of Mathematics Josip Juraj Strossmayer University of Osijek Trg Ljudevita Gaja 6 Osijek, HR31000, Croatia

Research Interests
 Optimization
 Computational Geometry
 Approximation Algorithms
Degrees
 PhD in CS, MaxPlanckInstitute for Computer Science (Algorithms and Complexity), Saarbrücken, 2007.
 Geometric Optimization and Querying  Exact and Approximate (1.3MB)
Thesis for obtaining the degree of a Doctor of the Engineering Sciences (Dr.Ing.) of the naturaltechnical faculties of Saarland University
 Geometric Optimization and Querying  Exact and Approximate (1.3MB)
 MS in CS, Saarland University, Germany, 2002.
 BS in Mathematics and Computer Science, Department of Mathematics, University of Osijek, Croatia, 2001.
Publications
 S. Jelić, S. Laue, D. Matijević, P. Wijerama, A Fast Parallel Implementation of a PTAS for Fractional Packing and Covering Linear Programs, International Journal of Parallel Programming 43/5 (2015), 840875We present a parallel implementation of the randomized (1+ε) approximation algorithm for packing and covering linear programs presented by Koufogiannakis and Young (2007). Their approach builds on ideas of the sublinear time algorithm of Grigoriadis and Khachiyan’s (Oper Res Lett 18(2):53–58, 1995) and Garg and Könemann’s (SIAM J Comput 37(2):630–652, 2007) nonuniformincrement amortization scheme. With high probability it computes a feasible primal and dual solution whose costs are within a factor of 1+ε of the optimal cost. In order to make their algorithm more parallelizable we also implemented a deterministic version of the algorithm, i.e. instead of updating a single random entry at each iteration we updated deterministically many entries at once. This slowed down a single iteration of the algorithm but allowed for larger stepsizes which lead to fewer iterations. We use NVIDIA’s parallel computing architecture CUDA for the parallel environment. We report a speedup between one and two orders of magnitude over the times reported by Koufogiannakis and Young (2007).
 S. Funke, T. Malamatos, D. Matijević, N. Wolpert, Conic nearest neighbor queries and approximate Voronoi diagrams, Computational Geometry  Theory and Applications 48/2 (2015), 7686Given a cone C and a set S of n points in R^d, we want to preprocess S into a data structure so that we can find fast an approximate nearest neighbor to a query point q with respect to the points of S contained in the translation of C with apex at q. We develop an approximate conic Voronoi diagram of O˜(n/eps^d) size that supports conic nearest neighbor queries in O(log(n/eps)) time. Our preprocessing uses only the wellseparated pair decomposition and a compressed quadtree. Previous results were restricted to simplicial cones and achieved polylogarithmic or higher query times. By increasing space to O˜(n/eps^{2d}) our data structure further supports queries for any cone direction and angle.
 D. Matijević, D. Ševerdija, G. Martinović, Efficient Implementations of Guarding 1.5D Terrains, Croatian Operational Research Review 6/1 (2015), 7989In 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 NPhard 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.
 N. Čerkez, R. Čorić, M. Đumić, D. Matijević, Finding an optimal seating arrangement for employees traveling to an event, Croatian Operational Research Review 6/2 (2015), 419427The paper deals with modelling a specific problem called the Optimal Seating Arrangement (OSA) as an Integer Linear Program and demonstrated that the problem can be efficiently solved by combining branchandbound and cutting plane methods. OSA refers to a specific scenario that could possibly happen in a corporative environment, i.e. when a company endeavors to minimize travel costs when employees travel to an organized event. Each employee is free to choose the time to travel to and from an event and it depends on personal reasons. The paper differentiates between using different travel possibilities in the OSA problem, such as using company assigned or a company owned vehicles, private vehicles or using public transport, if needed. Also, a userfriendly web application was made and is available to the public for testing purposes.
 K. Elbassioni, D. Matijević, D. Ševerdija, Guarding 1.5D Terrains with Demands, International Journal of Computer Mathematics 89/16 (2012), 21432151In 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 constantfactor 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.
 K. Elbassioni, S. Jelić, D. Matijević, The relation of Connected Set Cover and Group Steiner Tree, Theoretical Computer Science 438 (2012), 96101We report that the Connected Set Cover (CSC) problem is just a special case of the Group Steiner Tree (GST) problem. Based on that we obtain the first algorithm for CSC with polylogarithmic approximation guarantee as well as the first approximation algorithms for the weighted version of the problem and the version with requirements. Moreover, we argue that the inapproximability result of GST will carry on to the weighted version of the CSC problem.
 R. Beier, S. Funke, D. Matijević, P. Sanders, EnergyEfficient Paths In Radio Networks, Algorithmica 61/2 (2011), 289319We consider a radio network consisting of n stations represented as the complete graph on a set of n points in the Euclidean plane with edge weights $omega(p, q) = pq^delta +C_p$, for some constant $delta > 1 and nonnegative offset costs $C_p$. Our goal is to find paths of minimal energy cost between any pair of points that do not use more than some given number $k$ of hops. We present an exact algorithm for the important case when $delta = 2$, which requires $O(kn log n)$ time per query pair $(p, q)$. For the case of an unrestricted number of hops we describe a family of algorithms with query time $O(n^(1+alpha))$, where $alpha > 0$ can be chosen arbitrarily. If we relax the exactness requirement, we can find an approximate $(1+eps)$ solution in constant time by querying a data structure which has linear size and which can be build in $O(n log n)$ time. One tool we employ might be of independent interest: For any pair of points $(p, q)$ we can report in constant time the cluster pair (A,B) representing $(p, q)$ in a wellseparated pair decomposition of P.
 K. Elbassioni, E. Krohn, D. Matijević, J. Mestre, D. Ševerdija, Improved Approximations for Guarding 1.5Dimensional Terrains, Algorithmica 60/2 (2011), 451463We present a 4approximation 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.
 D. Matijević, R. Osbild, Finding the ThetaGuarded Region, Computational Geometry  Theory and Applications 43/2 (2010), 207218We are given a finite set of points (emph{guards}) in the plane. A Thetacone is a cone with apex angle Theta. We call a Thetacone empty, if it does not contain any guards in its interior. A point p is called Thetaguarded, if every Thetacone with apex located at p is nonempty. The set of all Thetaguarded points is called the Thetaguarded region, or the $Theta$region for short. The rationale behind this model is that a point is wellguarded only if it is guarded from all sides. In this paper we show the bound for the complexity of the Thetaregion as well as present the algorithms for computing it.
 J. Maue, P. Sanders, D. Matijević, Goal Directed Shortest Path Queries Using Precomputed Cluster Distances, ACM Journal of Experimental Algorithmics 14/3 (2009)We demonstrate how Dijkstra's algorithm for shortest path queries can be accelerated by using precomputed shortest path distances. Our approach allows a completely flexible tradeoff between query time and space consumption for precomputed distances. In particular, sublinear space is sufficient to give the search a strong "sense of direction". We evaluate our approach experimentally using large, realworld road networks.
 S. Laue, D. Matijević, Approximating khop Minimum Spanning Trees in Euclidean metrics, Information Processing Letters 107/34 (2008), 96101In the minimumcost khop spanning tree (khop MST) problem, we are given a set of n points in a metric space, a positive small integer k and a root point r. We are interested in computing a rooted spanning tree of minimum cost such that the longest rootleaf path in the tree has at most k edges. We present a polynomialtime approximation scheme for the plane. Our algorithm is based on Arora's et al. technique for the Euclidean kmedian problem.
 S. Funke, D. Matijević, P. Sanders, Constant Time Queries for Energy Efficient Paths in MultiHop Wireless Networks, CIT. Journal of Computing and Information Technology 16/2 (2008), 119130We investigate algorithms for computing energy efficient paths in adhoc radio networks. We demonstrate how advanced data structures from computational geometry can be employed to preprocess the position of radio stations in such a way that approximately energy optimal paths can be retrieved in constant time, i.e., independent of the network size. We put particular emphasis on actual implementations which demonstrate that large constant factors hidden in the theoretical analysis are not a big problem in practice.
 F. Eisenbrand, S. Funke, A. Karrenbauer, D. Matijević, EnergyAware Stage Illumination, International Journal of Computational Geometry & Applications 18/12 (2008), 107129Consider the following illumination problem: given a stage represented by a line segment and a set of lightsources represented by a set of points in the plane, assign powers to the lightsources such that every point on the stage receives a sufficient amount, let's say one unit, of light while minimizing the overall power consumption. By assuming that the amount of light arriving from a fixed lightsource decreases rapidly with the distance from the lightsource, this becomes an interesting optimization problem. We propose to reconsider the classical illumination problems as known from computational geometry literature under this light attenuation model. This paper examines the simple problem introduced above and presents different solutions, based on convex optimization, discretization and linear programming, as well as a purely combinatorial approximation algorithm.
 V. Hoan Do, M. Blažević, P. Monteagudo, L. Borozan, K. Elbassioni, S. Laue, F. Rojas Ringeling, D. Matijević, S. Canzar, Dynamic pseudotime warping of complex singlecell trajectories, 23nd Annual International Conference on Research in Computational Molecular Biology, The George Washington University, 2019, 294297Singlecell RNA sequencing enables the construction of trajectories describing the dynamic changes in gene expression underlying biological processes such as cell differentiation and development. The comparison of singlecell trajectories under two distinct conditions can illuminate the differences and similarities between the two and can thus be a powerful tool. Recently developed methods for the comparison of trajectories rely on the concept of dynamic time warping (dtw), which was originally proposed for the comparison of two time series. Consequently, these methods are restricted to simple, linear trajectories. Here, we adopt and theoretically link arboreal matchings to dtw and propose an algorithm to compare complex trajectories that more realistically contain branching points that divert cells into different fates. We implement a suite of exact and heuristic algorithms suitable for the comparison of trajectories of different characteristics in our tool Trajan. Trajan automatically pairs similar biological processes between conditions and aligns them in a globally consistent manner. In an alignment of singlecell trajectories describing human muscle differentiation and myogenic reprogramming, Trajan identifies and aligns the core paths without prior information. From Trajan’s alignment, we are able to reproduce recently reported barriers to reprogramming. In a perturbation experiment, we demonstrate the benefits in terms of robustness and accuracy of our model which compares entire trajectories at once, as opposed to a pairwise application of dtw. Trajan is available at https://github.com/canzarlab/Trajan.
 L. Borozan, D. Matijević, S. Canzar, Properties of the generalized RobinsonFoulds metric, 42nd International Convention  MIPRO 2019, Opatija, 2019, 330335Comparing hierarchical structures is a problem with many applications in various fields of biology. In this work we address the problem of comparing phylogenetic trees and quantifying their dissimilarities. The most commonly applied measure of similarity between phylogenetic trees is the Robinson Foulds (RF) metric. The JaccardRobinsonFoulds (JRF) metric (of order k) has been recently proposed as a generalization of the RF metric that preserves its widely appreciated properties but increases its resolution and robustness. Here, we conduct thorough experimental analysis of the JRF metric and variations thereof on both real world and simulated data. Our main aim is to deepen the understanding of the properties of this generalized RF metric in comparison to the classical RF metric and other matching based distance measures. To compute the JRF distance between trees, we employ the recently proposed branchandcut solver Trajan.
 S. Jelić, D. Matijević, The relation of Connected Set Cover and Group Steiner Tree, Conference on Applied Mathematics and Scientific Computing 2011, Trogir, 2011Let $U$ be the universe of elements which have to be covered, $mathcal{S}$ family of subsets of $U$ and $G=(mathcal{S},E)$ connected graph on vertex set $mathcal{S}$. We say that subfamily $mathcal{R}subseteqmathcal{S}$ is emph{connected set cover} (CSC) if every $uin U$ is covered by at least one set from $mathcal{R}$ and subgraph $G[mathcal{R}]$ induced by $mathcal{R}$ is connected. The problem is to find connected set cover with respect to $(U,mathcal{S},G)$ with minimum number of sets (vertices). On the other hand, suppose that we are given a graph $G$ with edge weight function $w:E(G)rightarrowR^+$ and family of subsets of vertices $mathcal{G} = {g_1,g_2,ldots,g_k},quad g_isubset V$ which will be called groups. The well known and well studied emph{Group Steiner Tree} (GST) is to find a subtree $T$ that minimizes the weight function $sum_{ein E(T)}w(e)$ such that $V(T)cap g_ineqemptyset$ for all $iin{1,ldots,k}$. We showed in our work that CSC is equivalent to the variant of GST when all edge weights equal to $1$. Hence, all algorithms for GST immediately apply for CSC problem as well. As a result, we obtain an approximation algorithm for CSC problem with approximation ratio $O(log^2mloglog mlog n)$ where $n$ is the size of universe $U$ and $m$ is the size of family $mathcal{S}$. This is the first polylogarithmic approximation algorithm for CSC problem. Natural generalization of CSC problem is to associate the nonnegative weight function with sets in $mathcal{S}$. Weighted CSC problem assumes finding of connected set cover that minimizes the total weight of subfamily $mathcal{R}$. We showed that this problem can be solved by reduction to the faulttolerant version of Group Steiner problems for which $O(sqrt{m}log m)$ approximation algorithm is known. We also consider generalization of CSC problem where each element $u$ from universe has requirement $r_u$ on number of sets covering element $u$ associated. We showed the reduction of this problem to the variant of GST problem with requirements associated to the groups for which $O(log^2 mloglog mlog(Rcdot n))$ approximation algorithm is known, where $R$ dentes the largest requirement.
 D. Matijević, G. Martinović, P. Taler, DISTRIBUTER  The Distributed System for Efficient Execution of Parallel Programs, 33rd International Convention on Information and Communication Technology, Electronics and Microelectronics (MIPRO), Opatija, 2010
 L. Borozan, D. Matijević, S. Canzar, Combinatorial optimization algorithms for (pseudo)alignment in bioinformatics (2021)The field of bioinformatics is a fast growing interdisciplinary field with a strong contribution from mathematics and computer science. This thesis will deal with mathematical problems and algorithmic challenges from that field. Its first focus will be the comparison of hierarchic structures, mainly phylogenetic trees, which is used to explain various biological processes such as the evolution of the species. We will study mathematical models and algorithmic techniques which quantify the distance between such structures as means of determining the similarities or dissimilarities between them. The focus will be given to formulating the problem based on matching in the context of integer linear programming. Our goal will be to find a novel solution which respects the ancestry relations defined by those hierarchical structures and is often overlooked in the current research. Our main result will be given in a form of a software tool  Trajan, which will be tested on both the real world and simulated data. The second focus of the thesis will come from the problem of sequencing the RNA molecule. It is a combinatorial process of reconstruction of the RNA molecule from short nucleotide sequences which is used to analyze the transcriptome of a biological sample. Many recent studies consider a problem of quantification and classification of unannotated splicing events which often occur due to the mutations caused by abnormal state of the organism, e.g. cancer. We will present another software tool, called fortuna, which brings together high accuracy and fast running times to the analysis of the alternative splicing events unlike any of the well established competitor tools.
 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.
 D. Matijević, D. Ševerdija, Problem vidljivosti, Osječki matematički list (2010), prihvaćen za objavljivanjeZa 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.
 S. Jelić, D. Matijević, Stage Illumination Problem (2009)Consider the following illumination problem: given a stage represented by a horizontal line segment and a set of light sources represented by a set of points in the plane above, assign powers to the light sources such that every point on the stage receives a sufficient amount (say one unit) of light while minimizing the overall power consumption. Under the assumption that the amount of light arriving from a fixed light source decreases rapidly with the distance from the light source, this becomes an interesting optimization problem. Two approximation algorithms based on linear programming are used in this Demonstration.
 D. Matijević, N. Truhar, Uvod u računarstvo, Odjel za matematiku, Sveučilište Josipa Jurja Strossmayera u Osijeku, Osijek, 2012.
Refereed Proceedings
 Guarding 1.5D Terrains with Demands
K. Elbassioni, D. Matijevic, D. Severdija
26th European Workshop on Computational Geometry (EuroCG'10 ), pp. 133136, Dortmund, 2010  TRANSIT: Ultrafast ShortestPath Queries with LinearTime Preprocessing
H. Bast, S. Funke, D. Matijevic
The Shortest Path Problem: Ninth DIMACS Implementation Challenge, pp. 175???192, AMS, 2009  Improved approximations for guarding 1.5dimensional terrains
K. Elbassioni, D. Matijevic, J. Mestre, and D. Severdija
CoRR, abs/0809.0159v1, 2008. and STACS 2009.  Approximating khop Minimum Spanning Trees in Euclidean metrics
S. Laue, D. Matijevic
preliminary version in Proc. 19th Canadian Conference on Computational Geometry (CCCG), 2007, Ottawa  In Transit to Constant Time ShortestPath Queries in Road Networks
H. Bast, S. Funke, D. Matijevic, P. Sanders, D. Schultes
9th Workshop on Algorithm Engineering and Experimentation (ALENEX), 2007, New Orleans  (Approximate) Conic Nearest Neighbors and the induced Voronoi Diagram
S. Funke, T. Malamatos, D. Matijevic, N. Wolpert
18th Canadian Conference on Computational Geometry (CCCG), 2006, Kingston, Ontario  Goal Directed Shortest Path Queries Using Precomputed Cluster Distances
J. Maue, P. Sanders, D. Matijevic
5th International Workshop on Experimetal Algorithms ( WEA 2006 ), Menorca Island, Volume 4007 in LNCS, pages 316  327, Springer, 2006.  EnergyAware Stage Illumination
F. Eisenbrand, S. Funke, A. Karrenbauer, D. Matijevic
preliminary version in Proc. 21st ACM Symposium on Computational Geometry (SoCG) 2005, Pisa  Constant Time Queries for Energy Efficient Paths in MultiHop Wireless Networks
S. Funke, D. Matijevic, P. Sanders
preliminary version in Proc. AlgorithmS for Wireless And mobile Networks (A_SWAN) 2004, Boston  Approximating Energy Efficient Paths in Wireless MultiHop Networks
S. Funke, D. Matijevic, P. Sanders
11th Annual European Symposium on Algorithms (ESA 2003), Budapest, Volume 2832 in LNCS, pages 230241. Springer, 2003.
Projects

GPU based implementation for computing the solution to the Quasitriangular Matrix Equation
Project run in 2010/11 in collaboration with Prof. Ninoslav Truhar, Petar Taler and Zoran Tomljanović , Dept. of Mathematics, University of Osijek
Project was supported by NVIDIA Corporation through the Academic Partnership Program.Abstract:
The solution to the (quasi) triangular Sylvester equation (i.e. a special case of the Sylvester equation) is well known and there are many FORTRAN codes to compute matrix for such a triangular system (e.g. LAPACK’s routine xTRSYL). However, recent work on the implementation of BLAS and the major factorization routines for the solution of linear systems has demonstrated the potential of GPUs to yield high performance on dense linear algebra operations that can be cast in terms of matrixmatrix products. Hence, in this small scale project we would like to evaluate the impact of these new architectures on the quasitriangular matrix equation solver based on the algorithm proposed in paper “Direct methods for matrix Sylvester and Lyapunov equations” by Danny C. Soerensen and Yunkai Zhou, J. Appl. Math. Vol. 2003, Number 6 (2003), 277303.

Fast and Efficient Kinetic Spanners
Project leader (on Croatian side): Domagoj Matijevic, Dept. of Mathematics, University of Osijek
Project leader (on German side) : Soeren Laue, Lehrstuhl fuer Theoretische Informatik II, University of Jena
Project was funded in 2010 by the German Academic Exchange Service and Croatian Ministry of Science, Education and SportsAbstract:
Point cloud data in low dimensional Euclidean spaces (dimensions up to ten) arises in many applications either through measurements or simulations. For analysis, e.g., clustering or near neighbor search, such data often need to be organized 11into a data structure. A popular data structure to that means is a kinetic (1+epsilon)spanner. In this project we want to analyze and implement different point cloud filtrations since point cloud filtrations have been used as a key ingredient of in the construction of succinct, efficient kinetic spanners.
Teaching
Konzultacije (Office Hours): Utorak (Tue) 10:0011:00. Konzultacije su moguće i po dogovoru.
Teme za diplomske radove (Master thesis topics):
 Teme se dogovaraju izravno na konzultacijama s nastavnikom.
Matrix Calculus
Matrix calculus allows to compute derivatives of functions that are defined over matrices and vectors.
You can try out our matrix calculus tool here.
Present and past courses
I am currently teaching
 Složenost algoritama (Algorithms Complexity)
 Uvod u računarstvo (Introduction to Computer Science)
 Uvod u programiranje (Introduction to programming)
 Programiranje i programsko inženjerstvo (Programming and software engineering)
 Ugrađeni sustavi (Embedded Systems)
 Klijentsko web programiranje (Clientside web programming)
I also taught:
 Linearna optimizacija (Linear Optimization)
 Izračunljiva geometrija (Computational Geometry)
 Algoritmi i strukture podataka (Algorithms and Data Structures)
 Operacijska istraživanja (Operational Research)
 Računalne mreže i usluge (Data networks and services)
 Modeliranje i dizajniranje baza podata (Modelling and designing of databases)