Domagoj Matijević

 

Associate Professor
Department of Mathematics
Josip Juraj Strossmayer University of Osijek
Trg Ljudevita Gaja 6
Osijek, HR-31000, Croatia¸
phone: +385-31-224-825
fax: +385-31-224-801
email: domagoj @ mathos.hr
office: 9 (ground floor, entrance through lobby 4)

Research Interests

Computational Geometry
Approximation Algorithms
Combinatorial Optimization

Degrees

PhD in CS, Max-Planck-Institute for Computer Science (Algorithms and Complexity Group), Saarbrücken, 2007.
MS in CS, Saarland University, Germany, 2002.
BS in Mathematics and Computer Science, Department of Mathematics, University of Osijek, Croatia, 2001.

Publications

Journal Publications

  1. 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), 840-875
    We 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) non-uniform-increment 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 step-sizes 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).
  2. S. Funke, T. Malamatos, D. Matijević, N. Wolpert, Conic nearest neighbor queries and approximate Voronoi diagrams, Computational Geometry - Theory and Applications 48/2 (2015), 76-86
    Given 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 well-separated 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.
  3. 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.
  4. 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), 419-427
    The 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 branch-and-bound 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 user-friendly web application was made and is available to the public for testing purposes.
  5. 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.
  6. K. Elbassioni, S. Jelić, D. Matijević, The relation of Connected Set Cover and Group Steiner Tree, Theoretical Computer Science 438 (2012), 96-101
    We 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.
  7. R. Beier, S. Funke, D. Matijević, P. Sanders, Energy-Efficient Paths In Radio Networks, Algorithmica 61/2 (2011), 289-319
    We 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 well-separated pair decomposition of P.
  8. 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.
  9. D. Matijević, R. Osbild, Finding the Theta-Guarded Region, Computational Geometry - Theory and Applications 43/2 (2010), 207-218
    We are given a finite set of points (emph{guards}) in the plane. A Theta-cone is a cone with apex angle Theta. We call a Theta-cone empty, if it does not contain any guards in its interior. A point p is called Theta-guarded, if every Theta-cone with apex located at p is non-empty. The set of all Theta-guarded points is called the Theta-guarded region, or the $Theta$-region for short. The rationale behind this model is that a point is well-guarded only if it is guarded from all sides. In this paper we show the bound for the complexity of the Theta-region as well as present the algorithms for computing it.
  10. 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, real-world road networks.
  11. S. Laue, D. Matijević, Approximating k-hop Minimum Spanning Trees in Euclidean metrics, Information Processing Letters 107/3-4 (2008), 96-101
    In the minimum-cost k-hop spanning tree (k-hop 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 root-leaf path in the tree has at most k edges. We present a polynomial-time approximation scheme for the plane. Our algorithm is based on Arora's et al. technique for the Euclidean k-median problem.
  12. S. Funke, D. Matijević, P. Sanders, Constant Time Queries for Energy Efficient Paths in Multi-Hop Wireless Networks, CIT. Journal of Computing and Information Technology 16/2 (2008), 119-130
    We investigate algorithms for computing energy efficient paths in ad-hoc 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.
  13. F. Eisenbrand, S. Funke, A. Karrenbauer, D. Matijević, Energy-Aware Stage Illumination, International Journal of Computational Geometry & Applications 18/1-2 (2008), 107-129
    Consider 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.


Refereed Proceedings

  1. S. Jelić, D. Matijević, The relation of Connected Set Cover and Group Steiner Tree, Conference on Applied Mathematics and Scientific Computing 2011, Trogir, 2011
    Let $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 fault-tolerant 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.
  2. 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


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. 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.
  3. 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.


Books

  1. D. Matijević, N. Truhar, Uvod u računarstvo, Odjel za matematiku, Sveučilište Josipa Jurja Strossmayera u Osijeku, Osijek, 2012.


 

 

 

Refereed Proceedings


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 and it has been assigned one TESLA C2070 GPU Computing Processor :-).

    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 matrix-matrix 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), 277-303.

     

  • 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

    Abstract:

    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:00-11:00. Konzultacije su moguće i po dogovoru.

Teme za diplomske radove (Master thesis topics): 

  • 3D printanje
  • Ugrađeni sustavi - izrada vlastitog IoT rješenja
  • Bioinformatika - teme iz NGS problematike
  • Implementacija obrade elektroničkog plaćanja u Web Shop aplikaciju: Razvit ćete „payment gateway„ za komunikaciju s PayPal Express Checkout servisom putem REST API i napraviti test na PayPal sandbox okruženju (problematika će se obrađivati u suradnji s tvrtkom Adacta). 
  • Izrada aplikacije za poslovno odlučivanje primjenom AHP metode (problematika će se obrađivati u suradanji s tvrtkom Adacta).
  • Sljedećih 5 tema usuglašene su i bit će sumentorirane od strane tvrtke UHP Digital: 
    • Reactive programming in iOS
      Unit testing in Swift
      Reactive programming in Android
      Architectural patterns for iOS
      Architectural patterns for Android


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

  1. Složenost algoritama (Algorithms Complexity)
  2. Uvod u računarstvo (Introduction to Computer Science)
  3. Uvod u programiranje (Introduction to programming)
  4. Programiranje i programsko inženjerstvo (Programming and software engineering)
  5. Ugrađeni sustavi (Embedded Systems)
  6. Klijentsko web programiranje (Client-side web programming)

I also taught:

  1. Linearna optimizacija (Linear Optimization)
  2. Izračunljiva geometrija (Computational Geometry)
  3. Algoritmi i strukture podataka (Algorithms and Data Structures)
  4. Operacijska istraživanja (Operational Research)
  5. Računalne mreže i usluge (Data networks and services)
  6. Modeliranje i dizajniranje baza podata (Modelling and designing of data-bases)