Asisstant Professor

Slobodan Jelić

(ground floor)
School of Applied Mathematics and Informatics

Josip Juraj Strossmayer University of Osijek

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

Journal Publications

  1. S. Jelić, D. Ševerdija, Government Formation Problem, Central European Journal of Operations Research (2017), prihvaćen za objavljivanje
    In addition to the same political and ideological attitudes, members of political parties can be interconnected at private and/or professional levels. They are considered as a part of one large social network. After democratic elections, the total effectiveness and stability of a government may depend on expertness and cooperability of its members. Our main goal is not to give a mechanism for pre-elective government formation, but to propose a model that decides what can be a good subset of candidates for positions in the new government. The decision is based on expertness of candidates and their interconnections in the social network. Inspired by the team formation problem in a social network, we present a Government Formation Problem (GFP). We prove that this problem is NP-hard and give an algorithm based on integer linear programming formulation. In the experimental part, we test our algorithm on simulated data using the GUROBI MILP solver.
  2. 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).
  3. S. Jelić, An FPTAS for the fractional group Steiner tree problem, Croatian Operational Research Review 6/2 (2015), 525-539
    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
    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.


Refereed Proceedings

  1. R. Čorić, M. Đumić, S. Jelić, A clustering model for time-series forecasting, 42nd International Convention - MIPRO 2019, Opatija, 2019, 1295-1299
    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.


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ć