Research Interests

• Combinatorial optimization
• Approximation Algorithms
• Linear optimization
• Massively parallel computing

Degrees

• dr. sc., University of Zagreb, PMF – Department of Mathematics, Croatian Doctoral Study of Mathematics, Zagreb, 2015.
  • PhD thesis: Fast approximation algorithms for connected set cover problem and related problems (in Croatian)
• mag. math., University of J. J. Strossmayer, Department of mathematics, Graduate Study of Mathematics, branch: Financial and Business Mathematics, Osijek, 2009.
  • master thesis: Approximation Algorithms for Optimal Stage Illumination (in Croatian)
• univ. bacc. math., University of J. J. Strossmayer, Department of mathematics, Undergraduate Study of Mathematics, Osijek, 2007.
  • bachelor thesis: Gaussian Method for Solving of Systems of Linear Equations (in Croatian)

Publications

1. S. Jelić, D. Ševerdija, Government Formation Problem, Central European Journal of Operations Research (2017), prihvaćen za objavljivanje
   Abstract

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

   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).
3. S. Jelić, An FPTAS for the fractional group Steiner tree problem, Croatian Operational Research Review 6/2 (2015), 525-539
   Abstract

   This paper considers a linear relaxation of the cut-based integer programming formulation for the group Steiner tree problem (FGST). We combine the approach of Koufogiannakis and Young (2013) with the nearly-linear time approximation scheme for the minimum cut problem of Christiano et. al (2011) in order to develop a fully polynomial time approximation scheme for FGST problem. Our algorithm returns the solution to FGST where the objective function value is a maximum of $1+6varepsilon$ times the optimal, for $varepsiloninlangle0,1/6]$, in $tilde{O(mk(m+n^{4/3}varepsilon^{-16/3})/varepsilon^2)$ time, where $n$, $m$ and $k$ are numbers of vertices, edges and groups in the group Steiner tree instance, respectively. This algorithm has a better worst-case running time than algorithm by Garg and Khandekar (2002) where the number of groups is sufficiently large.
4. K. Elbassioni, S. Jelić, D. Matijević, The relation of Connected Set Cover and Group Steiner Tree, Theoretical Computer Science 438 (2012), 96-101
   Abstract

   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.

1. R. Čorić, M. Đumić, S. Jelić, A clustering model for time-series forecasting, 42nd International Convention - MIPRO 2019, Opatija, 2019, 1295-1299
   Abstract

   In this paper we consider a novel Integer programming approach for the cluster-based model used for time-series forecasting. There are several approaches in literature that aim to find a set of patterns which represent similar situations in the time series. In order to predict target variable, different types of fitting methods can be applied to set of data that belongs to the same pattern. We propose method that uses clustering of patterns and prediction of target value as the mean of values in the same cluster, in order to minimize total squared deviation between predicted and real values of target variable. We also propose a heuristic method that achieves good solution in practice. Our approach is applied to short-term prediction of airborne pollen concentrations. We give experimental results about comparison of our method to some common approaches.

2. R. Čorić, M. Đumić, S. Jelić, A Genetic Algorithm for Group Steiner Tree Problem, 41st International Convention - MIPRO 2018, Opatija, Hrvatska, 2018, 1113-1118
   Abstract

   In Group Steiner Tree Problem (GST) we are given a weighted undirected graph and family of subsets of vertices which are called groups. Our objective is to find a minimum-weight subgraph which contains at least one vertex from each group (groups do not have to be disjoint). GST is NP-hard combinatorial optimization problem that arises from many complex real-life problems such as finding substrate-reaction pathways in protein networks, progressive keyword search in relational databases, team formation in social networks, etc. Heuristic methods are extremely important for finding the good-enough solutions in short time. In this paper we present genetic algorithm for solving GST. We also give results of computational experiments with comparisons to optimal solutions.
3. S. Jelić, On the fractional group Steiner tree problem, SYM-OP-IS 2015: XLII International Symposium on Operations Research, Donje Gradište, 2015
4. S. Jelić, D. Matijević, The relation of Connected Set Cover and Group Steiner Tree, Conference on Applied Mathematics and Scientific Computing 2011, Trogir, 2011
   Abstract

   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.

1. D. Matijević, D. Ševerdija, S. Jelić, L. Borozan, Uparena optimizacijska metoda, Math.e : hrvatski matematički elektronski časopis 30 (2016)
   Abstract

   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. Z. Ivančević, S. Jelić, Primjena SVD rastava matrice u dohvatu informacija i kompresiji slike, Osječki matematički list (2015), prihvaćen za objavljivanje
3. S. Jelić, Primjena karakterističnih funkcija u statistici, Osječki matematički list 10/1 (2010), 85-94
   Abstract

   U ovom radu određene su funkcije distribucije aritmetičke sredine slučajnog uzorka duljine n iz standardne normalne i jedinične uniformne distribucije primjenom karakterističnih funkcija. Na primjeru geometrijske sredine uzorka iz jedinične uniformne distribucije ilustrirana je primjena teorijskih rezultata o karakterističnim funkcijama (teorem jedinstvenosti). Navedeni su i specijalni primjeri određivanja distribucija nekih statistika koje se često primjenjuju.
4. S. Jelić, D. Matijević, Stage Illumination Problem (2009)
   Abstract

   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.

Projects

• “Paralelno računanje na grafičkom čipu u problemima diskretne linearne optimizacije”, (Odjel za matematiku, Sveučilište u Osijeku – Sveučilište u Osijeku) – voditelj projekta: Domagoj Matijević