Domagoj Matijević
Josip Juraj Strossmayer University of Osijek
Research Interests
 Machine Learning
 Optimization
 Application of ML in bioinformatics
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
 D. Matijević, A Python Package for WellSeparated Pair Decomposition, Journal of Open Research Software 12/1 (2024)Wellseparated pair decomposition (WSPD) is a wellknown geometric decomposition used for encoding distances, introduced in 1995 by Paul B. Callahan and S. Rao Kosaraju in a seminal paper. We implemented this remarkable decomposition following the nontrivial algorithm for computing the partial fair split tree of a point set presented in the original article. Our implementation is done in C++. In addition to that, we made further effort to publish it as a Python package on PyPI. By doing so, we made our software easily accessible on Windows, Linux, or macOS to researchers and students worldwide.
 M. Blažević, S. Canzar, K. Elbassioni, D. Matijević, Anti Tai mapping for unordered labeled trees, Information Processing Letters 185 (2024)The wellstudied Tai mapping between two rooted labeled trees defines a onetoone mapping between nodes in the first tree and the nodes in the second tree that preserves ancestor relationship. For unordered trees the problem of finding a maximumweight Tai mapping is known to be NPcomplete. In this work, we define an anti Tai mapping as a binary relation between two unordered labeled trees such that any two violate ancestor relationship and thus cannot be part of the same Tai mapping. Finding a maximumweight anti Tai mapping arises in the cutting plane method for solving the maximumweight Tai mapping problem via integer programming. We give an efficient polynomialtime algorithm for finding a maximumweight anti Tai mapping for the case when one of the two trees is a path and further show how to extend this result in order to provide a polynomially computable lower bound on the optimal anti Tai mapping for two unordered labeled trees.
 S. Canzar, V. Hoan Do, S. Jelić, S. Laue, D. Matijević, T. Prusina, Metric multidimensional scaling for large singlecell datasets using neural networks, Algorithms for Molecular Biology 19/21 (2024)Metric multidimensional scaling is one of the classical methods for embedding data into lowdimensional Euclidean space. It creates the lowdimensional embedding by approximately preserving the pairwise distances between the input points. However, current stateoftheart approaches only scale to a few thousand data points. For larger data sets such as those occurring in singlecell RNA sequencing experiments, the running time becomes prohibitively large and thus alternative methods such as PCA are widely used instead. Here, we propose a simple neural networkbased approach for solving the metric multidimensional scaling problem that is orders of magnitude faster than previous stateoftheart approaches, and hence scales to data sets with up to a few million cells. At the same time, it provides a nonlinear mapping between high and lowdimensional space that can place previously unseen cells in the same embedding.
 L. Borozan, F. Rojas Ringeling, S. Kao, E. Nikonova, P. Monteagudo, D. Matijević, M.L. Spletter, S. Canzar, Counting pseudoalignments to novel splicing events , Bioinformatics 39/7 (2023)Motivation Alternative splicing (AS) of introns from premRNA produces diverse sets of transcripts across cell types and tissues, but is also dysregulated in many diseases. Alignmentfree computational methods have greatly accelerated the quantification of mRNA transcripts from short RNAseq reads, but they inherently rely on a catalog of known transcripts and might miss novel, diseasespecific splicing events. By contrast, alignment of reads to the genome can effectively identify novel exonic segments and introns. Eventbased methods then count how many reads align to predefined features. However, an alignment is more expensive to compute and constitutes a bottleneck in many AS analysis methods. Results Here, we propose fortuna, a method that guesses novel combinations of annotated splice sites to create transcript fragments. It then pseudoaligns reads to fragments using kallisto and efficiently derives counts of the most elementary splicing units from kallisto’s equivalence classes. These counts can be directly used for AS analysis or summarized to larger units as used by other widely applied methods. In experiments on synthetic and real data, fortuna was around 7× faster than traditional align and count approaches, and was able to analyze almost 300 million reads in just 15 min when using four threads. It mapped reads containing mismatches more accurately across novel junctions and found more reads supporting aberrant splicing events in patients with autism spectrum disorder than existing methods. We further used fortuna to identify novel, tissuespecific splicing events in Drosophila. Availability and implementation fortuna source code is available at https://github.com/canzarlab/fortuna.
 D. Ševerdija, T. Prusina, L. Borozan, D. Matijević, Efficient Sentence Representation Learning via Knowledge Distillation with Maximum Coding Rate Reduction, CIT. Journal of Computing and Information Technology 31/4 (2023)Addressing the demand for effective sentence representation in natural language inference problems, this paper explores the utility of pretrained large language models in computing such representations. Although these models generate highdimensional sentence embeddings, a noticeable performance disparity arises when they are compared to smaller models. The hardware limitations concerning space and time necessitate the use of smaller, distilled versions of large language models. In this study, we investigate the knowledge distillation of SentenceBERT, a sentence representation model, by introducing an additional projection layer trained on the novel Maximum Coding Rate Reduction (MCR2) objective designed for generalpurpose manifold clustering. Our experiments demonstrate that the distilled language model, with reduced complexity and sentence embedding size, can achieve comparable results on semantic retrieval benchmarks, providing a promising solution for practical applications.
 R. Čorić, D. Matijević, D. Marković, PollenNet  a deep learning approach to predicting airborne pollen concentrations, Croatian Operational Research Review 14/1 (2023), 113The accurate shortterm forecasting of daily airborne pollen concentrations is of great importance in public health. Various machine learning and statistical techniques have been employed to predict these concentrations. In this paper, an RNNbased method called PollenNet is introduced, which is capable of predicting the average daily pollen concentrations for three types of pollen: ragweed (Ambrosia), birch (Betula), and grass (Poaceae). Moreover, two strategies incorporating measurement errors during the training phase are introduced, making the method more robust. The data for experiments were obtained from the RealForAll project, where pollen concentrations were gathered using a Hirsttype 7day volumetric spore trap. Additionally, five types of meteorological data were utilized as input variables. The results of our study demonstrate that the proposed method outperforms standard models typically used for predicting pollen concentrations, specifically the pollen calendar method, pollen predictions based on patterns, and the naive approach.
 D. Matijević, D. Vukičević, The Connection of the Generalized Robinson–Foulds Metric with Partial Wiener Indices, Acta Biotheoretica 71/5 (2023)In this work we propose the partial Wiener index as one possible measure of branch ing in phylogenetic evolutionary trees. We establish the connection between the gen eralized Robinson–Foulds (RF) metric for measuring the similarity of phylogenetic trees and partial Wiener indices by expressing the number of conflicting pairs of edges in the generalized RF metric in terms of partial Wiener indices. To do so we compute the minimum and maximum value of the partial Wiener index W(T, r, n), where T is a binary rooted tree with root r and n leaves. Moreover, under the Yule probabilistic model, we show how to compute the expected value of W(T, r, n). As a direct consequence, we give exact formulas for the upper bound and the expected number of conflicting pairs. By doing so we provide a better theoretical understand ing of the computational complexity of the generalized RF metric.
 D. Matijević, WellSeparated Pair Decompositions for HighDimensional Datasets, Algorithms 16/5 (2023)Wellseparated pair decomposition (WSPD) is a well known geometric decomposition used for encoding distances, introduced in a seminal paper by Paul B. Callahan and S. Rao Kosaraju in 1995. WSPD compresses O(n^2) pairwise distances of n given points from R^d in O(n) space for a fixed dimension d. However, the main problem with this remarkable decomposition is the “hidden” dependence on the dimension d, which in practice does not allow for the computation of a WSPD for any dimension d>2 or d>3 at best. In this work, I will show how to compute a WSPD for points in R^d and for any dimension d. Instead of computing a WSPD directly in R^d, I propose to learn nonlinear mapping and transform the data to a lowerdimensional space R^d′, d′=2 or d′=3, since only in such lowdimensional spaces can a WSPD be efficiently computed. Furthermore, I estimate the quality of the computed WSPD in the original R^d space. My experiments show that for different synthetic and realworld datasets my approach allows that a WSPD of size O(n) can still be computed for points in R^d for dimensions d much larger than two or three in practice.
 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.
 D. Ševerdija, T. Prusina, A. Jovanović, L. Borozan, J. Maltar, D. Matijević, Compressing Sentence Representation with Maximum Coding Rate Reduction (Best paper award in AIS  Artificial Intelligence Systems track), ICT and Electronics Convention (MIPRO), 2023 46th MIPRO, Opatija, Hrvatska, 2023In most natural language inference problems, sentence representation is needed for semantic retrieval tasks. In recent years, pretrained large language models have been quite effective for computing such representations. These models produce highdimensional sentence embeddings. An evident performance gap between large and small models exists in practice. Hence, due to space and time hardware limitations, there is a need to attain comparable results when using the smaller model, which is usually a distilled version of the large language model. In this paper, we assess the model distillation of the sentence representation model SentenceBERT by augmenting the pretrained distilled model with a projection layer additionally learned on the Maximum Coding Rate Reduction (MCR2) objective, a novel approach developed for general purpose manifold clustering. We demonstrate that the new language model with reduced complexity and sentence embedding size can achieve comparable results on semantic retrieval benchmarks.
 B. Borozan, L. Borozan, D. Ševerdija, D. Matijević, S. Canzar, Fortuna Detects Novel Splicing in Drosophila scRNASeq Data, ICT and Electronics Convention (MIPRO), 2023 46th MIPRO, Opatija, Hrvatska, 2023, 410415Recent developments in singlecell RNA sequencing techniques (scRNASeq) have made large quantities of sequenced data available across numerous species and tissues. Alternative splicing (AS) of premRNA introns varies between tissues and even between celltypes and can be altered in disease. The study of novel AS, using standard RNASeq data, has been extensively studied for many years, while similar work on scRNASeq data has been scarce, despite its potential to offer a broader insight into celltype specific processes. In this paper, we propose a novel pipeline that uses fortuna, a method that efficiently classifies and quantifies novel AS events, to process scRNASeq samples. Due to its short lifespan, high number of progeny, low maintenance cost, and intricate alternative splicing patterns similar in complexity to those of mammals, Drosophila Melanogaster (fruit fly) is a species of particular interest to researchers. Therefore, we experimentally evaluate our pipeline on realworld Drosophila singlecell data samples from the Fly Cell Atlas.
 J. Maltar, D. Matijević, Optimization techniques for image representation in visual place recognition, 2022 45th Jubilee International Convention on Information, Communication and Electronic Technology (MIPRO), Opatija, 2022, 877882In visual place recognition we aim to match a given query image from a query database with the most appropriate reference image from a reference database. One of the main issues is how to represent a place. Although an ordinary RGB representation can represent a place, various, either handcrafted or learned representations such as deep convolutional neural networks achieve better quantitative results. By using optimization techniques, both convex and nonconvex, we can adapt a place representation such that it fits into the problem of visual place recognition. Therefore, in this paper we examine numerous optimization techniques and incorporate them in the context of our problem. Quantitatively, in terms of the area under a curve (AUC) measure, conducted experiments show how such optimized representation outperforms unoptimized one.
 A. Jovanović, I. Alqassem, N. Chappell, S. Canzar, D. Matijević, Predicting RNA splicing branchpoints, 2022 45th Jubilee International Convention on Information, Communication and Electronic Technology (MIPRO), Opatija, 2022, 383388RNA splicing is a process where introns are removed from premRNA, resulting in mature mRNA. It requires three main signals, a donor splice site (5’ss), an acceptor splice site (3’ss) and a branchpoint (BP). Splice site prediction is a wellstudied problem with several reliable prediction tools. However, branchpoint prediction is a harder problem, mainly due to varying nucleotide motifs in the branchpoint area and the existence of multiple branchpoints in a single intron. An RNN based approach called LaBranchoR was introduced as the stateoftheart method for predicting a single BP for each 3’ss. In this work, we explore the fact that previous research reported that 95% of introns have multiple BPs with an estimated average of 5 to 6 BPs per intron. To that end, we extend the existing encoder in the LaBranchoR network with a PointerNetwork decoder. We train our new encoderdecoder model, named RNA PtrNets, on 70nucleotidelong annotated sequences taken from three publicly available datasets. We evaluate its accuracy and demonstrate how well the predictor can generate multiple branchpoints on the given datasets.
 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
 K. Elbassioni, D. Matijević, D. Ševerdija, I. Ali, Guarding 1.5D Terrains with Demands, 26th European Workshop on Computational Geometry (EuroCG), Dortmund, 2010
 K. Elbassioni, D. Matijević, J. Mestre, D. Ševerdija, Improved approximations for guarding 1.5dimensional terrains, Symposium on Theoretical Aspects of Computer Science (STACS), Freiburg, 2009We present a 4approximation algorithm for the problem of placing a 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. 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.
 H. Bast, S. Funke, D. Matijević, TRANSIT: Ultrafast ShortestPath Queries with LinearTime Preprocessing, The Shortest Path Problem: Ninth DIMACS Implementation Challenge, Rutgers University, Piscataway, NJ , 2009, 175192We introduce the concept of transit nodes, as a means for preprocessing a road network, with given coordinates for each node and a travel time for each edge, such that pointtopoint shortestpath queries can be answered extremely fast. The transit nodes are a set of nodes, as small as possible, with the property that every shortest path that is nonlocal in the sense that it covers a certain not too small euclidean distance passes through at least on of these nodes. With such a set and precomputed distances from each node in the graph to its few, closest transit nodes, every nonlocal shortest path query becomes a simple matter of combining information from a few table lookups. For the US road network, which has about 24 million nodes and 58 million edges, we achieve a worstcase query processing time of about 10 microseconds (not milliseconds) for 99% of all queries. This improves over the best previously reported times by two orders of magnitude.
 S. Laue, D. Matijević, Approximating khop Minimum Spanning Trees in Euclidean metrics, 19th Canadian Conference on Computational Geometry (CCCG), Ottawa, 2007
 H. Bast, S. Funke, D. Matijević, P. Sanders, D. Schultes, In Transit to Constant Time ShortestPath Queries in Road Networks, 9th Workshop on Algorithm Engineering and Experimentation (ALENEX), New Orleans, 2007
 S. Funke, T. Malamatos, D. Matijević, N. Wolpert, (Approximate) Conic Nearest Neighbors and the induced Voronoi Diagram, 18th Canadian Conference on Computational Geometry (CCCG), Kingston, Ontario, 2006
 J. Maue, P. Sanders, D. Matijević, Goal Directed Shortest Path Queries Using Precomputed Cluster Distances, 5th International Workshop on Experimetal Algorithms (WEA), Menorca Island, 2006, 316327
 F. Eisenbrand, S. Funke, A. Karrenbauer, D. Matijević, EnergyAware Stage Illumination, 21st ACM Symposium on Computational Geometry (SoCG), Pisa, Italy, 2005
 S. Funke, D. Matijević, P. Sanders, Constant Time Queries for Energy Efficient Paths in MultiHop Wireless Networks, AlgorithmS for Wireless And mobile Networks (A_SWAN), Boston, 2004
 S. Funke, D. Matijević, P. Sanders, Approximating Energy Efficient Paths in Wireless MultiHop Networks, 11th Annual European Symposium on Algorithms (ESA), Budapest, 2003, 230241
 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ć, S. Poljak, Fourierov red i Fourierova transformacija, Math.e : hrvatski matematički elektronski časopis 19 (2011)U ovom radu objasniti ćemo kako svaku periodičku funkciju možemo napisati kao sumu (ne nužno konačnu) sinusa različitih amplituda, faza i frekvencija – Fourierov red. U drugom dijelu rada motivirati ćemo formulu za Fourierovu transformaciju preko Fourierova reda te objasniti formulu za diskretnu Fourierovu transformaciju.
 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.
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. 
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 Sports
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)